1

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.

enter image description here

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.

Saradamani
  • 1,579
  • Please understand I cannot understand how to even approach this problem. Give me some answer/hint whatsoever please. – Saradamani Apr 17 '18 at 17:07
  • For large values of $n$, $f(f(n))$ is going to be much larger than $f(n)$, so just check small values of $n$ until you have found them all. For example, does $n=0$ work? How about $n=1$? etc – Mike Earnest Apr 17 '18 at 17:07
  • @MikeEarnest I already did that but I get only 3 non-negative integers. The previous question was to prove $f(n)<f(n+1)$. Which I have proved. – Saradamani Apr 17 '18 at 17:10

1 Answers1

4

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\}$

Delta-u
  • 6,038
  • I have done that already. But I get only three numbers, the questions demands 4 non-negative integers. – Saradamani Apr 17 '18 at 17:09
  • 2
    @Saradamani The question is mistaken. – saulspatz Apr 17 '18 at 17:09
  • I’m not sure what you mean by ‘solving’ but what the statement is saying is, for example, 5+3=8 where f(n)=8, f(n-1)=5, and f(n-2)=3. That’s what defines the fibonacci series: that each number is sum of the two numbers before it.

    0,1,1,2,3,5,8,13,21,34,55,89,144… Is this an assignment? If so, what does the assignment demand?

     – poetasis Apr 17 '18 at 17:16
  • The question is not mistaken, @Saradamani is mistaken. There do exist four numbers $n$ for which $f(f(n)) = f(n)$. – Mike Earnest Apr 17 '18 at 17:18
  • No @poetasis it is a question asked in Indian Statistical Institute entrance test for either BMath/BStat. It is in the book called Test of Mathematics at The 10+2 level. – Saradamani Apr 17 '18 at 17:22
  • @Delta-u I still did not get by how you say "four solutions". Can you work it out please? – Saradamani Apr 17 '18 at 17:28
  • 1
    The idea is to work in to step:
    • if $f(f(n))=f(n)$ then $k=f(n)$ is a solution of $f(k)=k$. Let $K={k, f(k)=k}$.
    • then you have to solve $f(n) \in K$.
     – Delta-u Apr 17 '18 at 17:32
  • @Delta-u Can this be passed on as a proof. I mean its existential but how to generalize this? Because they asked for a proof.(By they I mean the book. Please see my OP for some users I have directly taken a snapshot of that page) – Saradamani Apr 17 '18 at 17:35
  • Yes, the main point to carefully write out is that there is no solution for $n \geq 6$. – Delta-u Apr 17 '18 at 17:36