TAOCP 1.2.8 Exercise 25

Exercise 25. [M21] Show that

$$ 2^nF_n = 2 \sum_{k\ \mathrm{odd}} \binom{n}{k} 5^{(k-1)/2}. $$

Verified: no
Solve time: -

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

Hence

$$ 2^nF_n = \frac{1}{\sqrt5}\bigl((2\phi)^n-(2\hat\phi)^n\bigr). $$

Since

$$ 2\phi=1+\sqrt5, \qquad 2\hat\phi=1-\sqrt5, $$

we obtain

$$ 2^nF_n = \frac{(1+\sqrt5)^n-(1-\sqrt5)^n}{\sqrt5}. $$

Applying the binomial theorem gives

$$ (1+\sqrt5)^n = \sum_{k=0}^n \binom{n}{k}(\sqrt5)^k, $$

and

$$ (1-\sqrt5)^n = \sum_{k=0}^n \binom{n}{k}(-\sqrt5)^k. $$

Therefore

$$ (1+\sqrt5)^n-(1-\sqrt5)^n = \sum_{k=0}^n \binom{n}{k} \bigl((\sqrt5)^k-(-\sqrt5)^k\bigr). $$

If $k$ is even, the term $(\sqrt5)^k-(-\sqrt5)^k$ is zero. If $k$ is odd,

$$ (\sqrt5)^k-(-\sqrt5)^k = 2(\sqrt5)^k. $$

Thus

$$ (1+\sqrt5)^n-(1-\sqrt5)^n = 2\sum_{k\ \mathrm{odd}} \binom{n}{k} (\sqrt5)^k. $$

Dividing by $\sqrt5$ yields

$$ 2^nF_n = 2\sum_{k\ \mathrm{odd}} \binom{n}{k} (\sqrt5)^{k-1}. $$

Since $k$ is odd, $k-1$ is even, so

$$ (\sqrt5)^{k-1}=5^{(k-1)/2}. $$

Consequently,

$$ 2^nF_n = 2\sum_{k\ \mathrm{odd}} \binom{n}{k} 5^{(k-1)/2}. $$

Therefore

$$ \boxed{ 2^nF_n = 2\sum_{k\ \mathrm{odd}} \binom{n}{k}5^{(k-1)/2} }. $$

This completes the proof.

∎