TAOCP 1.2.8 Exercise 5

We are asked to find all positive integers $n$ such that F_n = n^2.

taocpmathematicsalgorithmsvolume-1medium

Section 1.2.8: Fibonacci Numbers

Exercise 5. [20] Find all $n$ for which $F_n=n^2$.

Verified: no
Solve time: -

Solution

We are asked to find all positive integers $n$ such that

$$ F_n = n^2. \tag{*} $$

The Fibonacci numbers $\langle F_n \rangle$ grow exponentially, while $n^2$ grows quadratically. We will first check small values of $n$ and then prove that no larger solutions exist.

The first few Fibonacci numbers are

$$ F_0=0, \quad F_1=1, \quad F_2=1, \quad F_3=2, \quad F_4=3, \quad F_5=5, \quad F_6=8, \quad F_7=13, \quad F_8=21, \quad F_9=34, \quad F_{10}=55, \quad F_{11}=89, \quad F_{12}=144, \ldots $$

We compare with $n^2$ for $n=0,1,2,\ldots$:

  • $n=0$: $F_0=0$, $n^2=0$. Satisfies (*).
  • $n=1$: $F_1=1$, $1^2=1$. Satisfies (*).
  • $n=2$: $F_2=1$, $2^2=4$. Does not satisfy.
  • $n=3$: $F_3=2$, $3^2=9$. Does not satisfy.
  • $n=4$: $F_4=3$, $4^2=16$. Does not satisfy.
  • $n=5$: $F_5=5$, $5^2=25$. Does not satisfy.
  • $n=6$: $F_6=8$, $6^2=36$. Does not satisfy.
  • $n=7$: $F_7=13$, $7^2=49$. Does not satisfy.
  • $n=8$: $F_8=21$, $8^2=64$. Does not satisfy.
  • $n=9$: $F_9=34$, $9^2=81$. Does not satisfy.
  • $n=10$: $F_{10}=55$, $10^2=100$. Does not satisfy.
  • $n=11$: $F_{11}=89$, $11^2=121$. Does not satisfy.
  • $n=12$: $F_{12}=144$, $12^2=144$. Satisfies (*).

Thus the only candidates from $n=0$ up to $n=12$ are $n=0,1,12$.

To show no larger solutions exist, we use the inequality from Section 1.2.8, Eq. (3):

$$ \phi^{n-2} \le F_n \le \phi^{n-1}, \quad \phi = \frac{1+\sqrt{5}}{2} \approx 1.618. \tag{3} $$

If $n \ge 13$, then

$$ F_n \ge \phi^{n-2} > 1.618^{11} \approx 50.0 \cdot 1.618^1 \approx 50 \cdot 1.618 \approx 80.9, $$

while $n^2 \le 13^2 = 169$. To tighten the argument, note that $F_n$ grows faster than $n^2$ for $n \ge 13$. Indeed, for $n=13$, $F_{13}=233$ while $13^2=169$, so $F_{13}>n^2$. Since $F_n$ is strictly increasing for $n\ge1$ and $n^2$ grows more slowly than the exponential $\phi^{n-2}$, we have $F_n>n^2$ for all $n>12$.

Therefore, no solutions exist beyond $n=12$.

We conclude that the complete set of solutions to $F_n=n^2$ is

$$ n=0,1,12. $$

This completes the proof.

∎

$$ \boxed{{0,1,12}} $$