Let $f: \mathbb N \to \mathbb N$ be a function such that $f(1)=1$ and
$$f(n)=n - f(f(n-1)), \quad n \geq 2.$$
Show that $f(n+f(n))=n $ for each positive integer $n.$
My answer is not elegant and rather delicate. All comments are more than welcome !
We look first at some special properties of f(n).
Property A: f(n) is either equal to f(n-1) or f(n-1)+1
Proof by induction: Suppose it is true up to an n such that f(n)= f(n-1) then using the definition of f(n+1) and replacing f(f(n)) by f(f(n-1)) gives f(n+1)=f(n)+1
Now suppose n is such that f(n) =f(n-1)+1 then f(n+1)=n+1-f(f(n-1)+1)
We note that f(n) is always smaller than n therefore induction applies to the above and f(f(n-1)+1) is either equal to f(f(n-1)) or
f(f(n-1))+1 so we get either f(n+1)=f(n) or f(n+1)=f(n)+1
Property B : we note that if f(n)=f(n-1) then f(n+1)=f(n)+1
We now look at the problem f(n+f(n))= n
We proceed by induction;Suppose it is true up to an n such that f(n+1)=f(n)
Then f(n+1+f(n+1)) =n+1+f(n)-f(f(n+f(n))=n+1+f(n)-f(n)=n+1 by induction
We note that f(n+1+f(n+1))=f(n+1+f(n))=f(n+f(n))+1=n+1
My answer is not elegant and rather delicate. All comments are more than welcome !
We look first at some special properties of f(n).
Property A: f(n) is either equal to f(n-1) or f(n-1)+1
Proof by induction: Suppose it is true up to an n such that f(n)= f(n-1) then using the definition of f(n+1) and replacing f(f(n)) by f(f(n-1)) gives f(n+1)=f(n)+1
Now suppose n is such that f(n) =f(n-1)+1 then f(n+1)=n+1-f(f(n-1)+1) We note that f(n) is always smaller than n therefore induction applies to the above and f(f(n-1)+1) is either equal to f(f(n-1)) or f(f(n-1))+1 so we get either f(n+1)=f(n) or f(n+1)=f(n)+1
Property B : we note that if f(n)=f(n-1) then f(n+1)=f(n)+1
We now look at the problem f(n+f(n))= n
We proceed by induction;Suppose it is true up to an n such that f(n+1)=f(n) Then f(n+1+f(n+1)) =n+1+f(n)-f(f(n+f(n))=n+1+f(n)-f(n)=n+1 by induction
We note that f(n+1+f(n+1))=f(n+1+f(n))=f(n+f(n))+1=n+1
We now look at f(n+2)=f(n+1)+1 from B
f(n+2+f(n+2))=n+2+f(n+2)-f(f(n+1+f(n+2))=n+3+f(n)-f(f(n+2+f(n)))
Now f(n+2+f(n)) can be either equal to f(n+f(n))+1 or f(n+f(n)))+2 from A
If we take the first case then:
f(n+2+f(n+2))=f(n+3+f(n))=n+3+f(n)-f(n+1)=n+3 but if f(n+1+f(n))=n+1 and f(n+3+f(n))=n+3 then f(n+2+f(n)) must be n+2 by A This is a contradiction
Therefore f(n+2+f(n))=n+2 and we have f(n+2+f(n+2))=n+3+f(n)-f(n+2)=n+2
This completes the induction