Given a fibonacci sequence where $f(n)=f(n-1)+f(n-2) for \space n\ge 2 $and $f(0)=0,f(1)=1$

Question

Prove that there exists four non-negative integers n for which $f(f(n))=f(n)$

I tried to solve it by:

$f(f(n-1)+f(n-2))=f(n)$ Thus $f(n-1)+f(n-2)=n$(But I am confused at this) Please give me atleast one hint to solve this problem.

For some users like @poetasis I directly post the snapshot of the original question from the book. Sorry this is not a homework assignment.It is a practice book for Math.

For curious readers and enthusiasts in Mathematics, I think I should let you know that Fibonacci was actually invented in India back in 450 BCE and was later identified and elaborated by Gopala in 11th century. Hence it is a matter of pride for me, being an Indian, to let you all know that like many other inventions, Fibonacci had its roots in India.

Answer 1

Hint

You can compute the first terms:

• $\color{blue}{f(0)=0}$
• $\color{blue}{f(1)=1}$
• $f(2)=1$
• $f(3)=2$
• $f(4)=3$
• $\color{blue}{f(5)=5}$
• $f(6)=8$

Then prove by induction that for $k \geq 6$, you have $$f(k)>k$$ so there is no others solutions.

---

To develop on the comments once you have found the three solutions to $f(k)=k$ (i.e $0,1,5$). You have to solve: $$f(n) \in \{ 0,1,5 \}$$ which have four solutions ($\color{green}{0,1,2,5}$):

• $f(\color{green}0)=\color{blue}{0}$
• $f(\color{green}1)=\color{blue}{1}$
• $f(\color{green}2)=\color{blue}{1}$
• $f(3)=2$
• $f(4)=3$
• $f(\color{green}5)=\color{blue}{5}$
• $f(6)=8$

and for $n \geq 6$ you have $f(n) \geq 6$ so $f(n) \notin \{0,1,5\}$