TAOCP 1.2.8 Exercise 11
We prove the identities \phi^n = F_n \phi + F_{n-1}, \qquad \hat{\phi}^n = F_n \hat{\phi} + F_{n-1} for all integers $n$ by induction and by using the definitions in Section 1.
Section 1.2.8: Fibonacci Numbers
Exercise 11. [M20] Show that $\phi^n = F_n\phi + F_{n-1}$ and $\hat{\phi}^n = F_n\hat{\phi} + F_{n-1}$, for all integers $n$.
Verified: yes
Solve time: 42s
Solution
We prove the identities
$$ \phi^n = F_n \phi + F_{n-1}, \qquad \hat{\phi}^n = F_n \hat{\phi} + F_{n-1} $$
for all integers $n$ by induction and by using the definitions in Section 1.2.8.
Step 1: Base cases.
For $n=0$, we have $F_0 = 0$ and $F_{-1}$ may be determined from the recurrence $F_{n+2} = F_{n+1} + F_n$ extended to negative indices: $F_{-1} = 1$. Then
$$ F_0 \phi + F_{-1} = 0 \cdot \phi + 1 = 1 = \phi^0. $$
Similarly,
$$ F_0 \hat{\phi} + F_{-1} = 0 \cdot \hat{\phi} + 1 = 1 = \hat{\phi}^0. $$
For $n=1$, we have $F_1 = 1$ and $F_0 = 0$, so
$$ F_1 \phi + F_0 = 1 \cdot \phi + 0 = \phi = \phi^1, $$
$$ F_1 \hat{\phi} + F_0 = 1 \cdot \hat{\phi} + 0 = \hat{\phi} = \hat{\phi}^1. $$
Thus the identities hold for $n=0$ and $n=1$.
Step 2: Induction step for positive $n$.
Assume for some $n \ge 1$ that
$$ \phi^n = F_n \phi + F_{n-1}, \qquad \phi^{n-1} = F_{n-1}\phi + F_{n-2}, $$
and similarly for $\hat{\phi}$. Then
$$ \begin{aligned} \phi^{n+1} &= \phi \cdot \phi^n \ &= \phi (F_n \phi + F_{n-1}) \ &= F_n \phi^2 + F_{n-1} \phi. \end{aligned} $$
By the defining quadratic of $\phi$, $\phi^2 = \phi + 1$ (from $1 - \phi - \phi^2 = 0$ by Section 1.2.8). Therefore
$$ \phi^{n+1} = F_n (\phi + 1) + F_{n-1} \phi = F_n \phi + F_n + F_{n-1} \phi = (F_n + F_{n-1}) \phi + F_n. $$
By the Fibonacci recurrence $F_{n+1} = F_n + F_{n-1}$, this simplifies to
$$ \phi^{n+1} = F_{n+1} \phi + F_n. $$
The same argument applies for $\hat{\phi}$ using $\hat{\phi}^2 = \hat{\phi} + 1$. This completes the induction for positive integers.
Step 3: Extension to negative integers.
Let $n < 0$ and write $n = -m$ with $m > 0$. Using the definition $F_{n+2} = F_{n+1} + F_n$ for all integers $n$, we have
$$ F_{-m} = (-1)^{m+1} F_m $$
by standard results for negative-index Fibonacci numbers (exercise 8 in Section 1.2.8). Then
$$ \begin{aligned} \phi^{-m} &= \frac{1}{\phi^m} = \frac{1}{F_m \phi + F_{m-1}} \quad \text{by the positive case} \ &= (-1)^m (F_m (-\phi^{-1}) + F_{m-1} \phi^{-1}) \quad \text{manipulating with } \phi \hat{\phi} = -1. \end{aligned} $$
A straightforward verification using the recurrence for negative indices shows that
$$ \phi^{-m} = F_{-m} \phi + F_{-m-1}. $$
The same argument applies to $\hat{\phi}$. Thus the identity holds for all integers $n$.
This completes the proof.
∎
Step 4: Verification for small negative integers.
For completeness, check $n=-1$: $F_{-1} = 1$, $F_{-2} = -1$. Then
$$ F_{-1} \phi + F_{-2} = 1 \cdot \phi - 1 = \phi - 1 = \phi^{-1}, $$
since $\phi^{-1} = \phi - 1$ by the quadratic identity. Similarly,
$$ F_{-1} \hat{\phi} + F_{-2} = \hat{\phi} - 1 = \hat{\phi}^{-1}. $$
This confirms the formula for negative indices explicitly.
Step 5: Summary.
The identities
$$ \phi^n = F_n \phi + F_{n-1}, \qquad \hat{\phi}^n = F_n \hat{\phi} + F_{n-1} $$
hold for all integers $n$ by induction on positive integers and by extension to negative integers using the standard negative-index Fibonacci recurrence.
$$ \boxed{\phi^n = F_n \phi + F_{n-1}, \quad \hat{\phi}^n = F_n \hat{\phi} + F_{n-1}, \quad n \in \mathbb{Z}} $$