TAOCP 1.2.8 Exercise 4

Exercise 4. [14] Find all $n$ for which $F_n=n$.

Verified: yes
Solve time: 38s

Solution

By Eq. (14),

$$ F_n=\frac{1}{\sqrt5}(\phi^n-\hat\phi^n), $$

where

$$ \phi=\frac{1+\sqrt5}{2}, \qquad \hat\phi=\frac{1-\sqrt5}{2}. $$

The values

$$ F_0=0,\qquad F_1=1,\qquad F_5=5 $$

show that

$$ n=0,;1,;5 $$

are solutions of the equation $F_n=n$.

It remains to prove that no other solutions exist.

For $n\ge 6$, Section 1.2.1 gives

$$ F_n\ge \phi^{,n-2}. $$

Since

$$ \phi^4=\phi^3+\phi^2 =(2\phi+1)+(\phi+1) =3\phi+2

6, $$

we have

$$ F_6\ge \phi^4>6. $$

Also,

$$ F_{n+1}=F_n+F_{n-1}>F_n $$

for all $n\ge1$, because $F_{n-1}>0$. Hence the sequence is strictly increasing for $n\ge1$. Therefore

$$ F_n\ge F_6>6 $$

for every $n\ge6$.

Define

$$ D_n=F_n-n. $$

For $n\ge6$,

$$ D_6=F_6-6=8-6=2>0, $$

and

$$ D_{n+1}-D_n =(F_{n+1}-F_n)-1 =F_{n-1}-1. $$

Since $n\ge6$ implies $n-1\ge5$ and $F_5=5$, the monotonicity of the Fibonacci sequence yields

$$ F_{n-1}-1\ge4>0. $$

Thus $D_{n+1}>D_n$ for all $n\ge6$. Because $D_6>0$, it follows that

$$ D_n>0 $$

for every $n\ge6$. Hence

$$ F_n>n \qquad (n\ge6). $$

The remaining cases are $n=2,3,4$:

$$ F_2=1\ne2,\qquad F_3=2\ne3,\qquad F_4=3\ne4. $$

Therefore the only integers $n$ satisfying $F_n=n$ are

$$ \boxed{n=0,;1,;5}. $$

This completes the proof.

∎