TAOCP 1.2.8 Exercise 18

We are asked whether the sum of the squares of consecutive Fibonacci numbers, F_n^2 + F_{n+1}^2, is itself always a Fibonacci number.

taocpmathematicsalgorithmsvolume-1medium

Section 1.2.8: Fibonacci Numbers

Exercise 18. [20] Is $F_n^2 + F_{n+1}^2$ always a Fibonacci number?

Verified: no
Solve time: -

Solution

We are asked whether the sum of the squares of consecutive Fibonacci numbers,

$$ F_n^2 + F_{n+1}^2, $$

is itself always a Fibonacci number. We analyze this question rigorously using the identities and properties of the Fibonacci sequence established in Section 1.2.8.

First, we examine small values of $n$ to check for any obvious pattern. Using $F_0=0$, $F_1=1$, $F_2=1$, $F_3=2$, $F_4=3$, $F_5=5$, $F_6=8$, $F_7=13$, we have:

  • $n=0$: $F_0^2 + F_1^2 = 0^2 + 1^2 = 1 = F_1$, a Fibonacci number.
  • $n=1$: $F_1^2 + F_2^2 = 1^2 + 1^2 = 2 = F_3$, a Fibonacci number.
  • $n=2$: $F_2^2 + F_3^2 = 1^2 + 2^2 = 1 + 4 = 5 = F_5$, a Fibonacci number.
  • $n=3$: $F_3^2 + F_4^2 = 2^2 + 3^2 = 4 + 9 = 13 = F_7$, a Fibonacci number.
  • $n=4$: $F_4^2 + F_5^2 = 3^2 + 5^2 = 9 + 25 = 34 = F_9$, a Fibonacci number.
  • $n=5$: $F_5^2 + F_6^2 = 5^2 + 8^2 = 25 + 64 = 89 = F_{11}$, a Fibonacci number.

This sequence suggests the identity

$$ F_n^2 + F_{n+1}^2 = F_{2n+1}. \tag{1} $$

We now prove Eq. (1) by induction on $n$.

Base case: $n=0$. We have $F_0^2 + F_1^2 = 0 + 1 = 1$ and $F_{2\cdot 0+1} = F_1 = 1$. The base case holds.

Induction hypothesis: Suppose that for some $n \ge 0$,

$$ F_n^2 + F_{n+1}^2 = F_{2n+1}. \tag{2} $$

Inductive step: Consider $n+1$. We have

$$ F_{n+1}^2 + F_{n+2}^2. $$

Using the Fibonacci recurrence $F_{n+2} = F_{n+1} + F_n$, we find

$$ \begin{aligned} F_{n+1}^2 + F_{n+2}^2 &= F_{n+1}^2 + (F_{n+1} + F_n)^2 \ &= F_{n+1}^2 + F_{n+1}^2 + 2 F_n F_{n+1} + F_n^2 \ &= F_n^2 + 2 F_n F_{n+1} + 2 F_{n+1}^2 \ &= (F_n^2 + F_{n+1}^2) + (F_{n+1}^2 + 2 F_n F_{n+1}) \ &= F_{2n+1} + (F_{n+1}^2 + 2 F_n F_{n+1}). \end{aligned} $$

We recognize that $F_{n+1}^2 + 2 F_n F_{n+1} = F_{n+1}(F_{n+1} + 2 F_n)$. By the recurrence formula for $F_{2n+3}$, which by Eq. (6) with $m=n+1$ reads

$$ F_{2n+3} = F_{n+1} F_{n+2} + F_n F_{n+1} = F_{n+1}(F_n + F_{n+1}) + F_n F_{n+1} = F_{n+1}^2 + 2 F_n F_{n+1} + F_n^2. $$

Comparing with the previous expression, we obtain

$$ F_{n+1}^2 + F_{n+2}^2 = F_{2n+3}. $$

This completes the inductive step. By the principle of mathematical induction, Eq. (1) holds for all $n \ge 0$.

Hence, the sum of the squares of consecutive Fibonacci numbers is itself a Fibonacci number, specifically the Fibonacci number with index $2n+1$:

$$ \boxed{F_n^2 + F_{n+1}^2 = F_{2n+1}}. $$

This completes the proof.

∎