How can one show that $f(n)>n$

Question

Given a function $f\colon \Bbb N^\ast\to \Bbb N^\ast$ such that we have $f(f(n))=f(n+1)-f(n)~\forall~n\in\Bbb N^\ast$.

Show that: If $f(n+1)-f(n)>1$ then $f(n)>n$.

Since $f(n+1)>f(n)+1$ I gave it some values:

For $n=1$: $f(2)>f(1)+1$.

For $n=2$: $f(3)>f(2)+1$.

I don't know how can I start my proof. I thought about induction but I am still stuck!

Answer 1

$f(1) \in \mathbb N$. So $f(1) \ge 1$.

Suppose $f(1) = 1$. Then $1 = f(1) = f(f(1)) = f(2) - f(1)$. So $f(2) - f(1) = 1$. That goes against our assumption that $f(n + 1) - f(n) > 1$.

So $f(1) > 1$.

That was our initial step in a proof by induction.

Suppose $f(k) > k$. Then $f(k+1) - f(k) > 1$ so $f(k + 1) > f(k) + 1 > k + 1$.

That was our inductive step.

we're done. we proved it.

Answer 2

Hint: If you combine the two statements you wrote down for the small values, what do you get? And what about $f(1) > f(0) + 1$?

Answer 3

By induction you should be able to prove $f(n)>f(0)+n$. From this you can conclude $f(n)>n$.