Spring 2017, problem 46

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.$


4 years ago

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


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