TAOCP 1.2.8 Exercise 30

Let $\langle F_n \rangle$ denote the Fibonacci sequence as defined in Section 1.

taocpmathematicsalgorithmsvolume-1math-project

Section 1.2.8: Fibonacci Numbers

Exercise 30. [M38] (D. Jarden, T. Motzkin.) The sequence of $m$th powers of Fibonacci numbers satisfies a recurrence relation in which each term depends on the preceding $m+1$ terms. Show that

$$ \sum_k \binom{m}{k}{\mathcal{F}} (-1)^{\lceil (m-k)/2 \rceil} F{n+k}^{,m-1} = 0, \qquad \text{if } m>0. $$

For example, when $m=3$ we get the identity $F_n^2 - 2F_{n+1}^2 - 2F_{n+2}^2 + F_{n+3}^2 = 0$.

Verified: no
Solve time: -

Setup

Let $\langle F_n \rangle$ denote the Fibonacci sequence as defined in Section 1.2.8, with $F_0=0$, $F_1=1$, and $F_{n+2}=F_{n+1}+F_n$ for $n\ge 0$. Let $m$ be a fixed positive integer, and consider the sequence of $m$th powers $\langle F_n^m \rangle$. We are asked to show that there exists a linear recurrence relation of order $m+1$ satisfied by $F_n^m$, which can be expressed as

$$ \sum_{k=0}^{m} \binom{m}{k}{\mathcal{F}} (-1)^{\lceil (m-k)/2 \rceil} F{n+k}^{,m-1} = 0 \quad \text{for } m>0, $$

where $\binom{m}{k}_{\mathcal{F}}$ denotes the Fibonomial coefficient defined in Exercise 29. The summation runs over $k=0,1,\dots,m$, and $\lceil x \rceil$ denotes the ceiling function. The goal is to prove this identity for general $m$.

Solution

We proceed by induction on $m$.

Base case $m=1$:

For $m=1$, the proposed identity reduces to

$$ \sum_{k=0}^{1} \binom{1}{k}{\mathcal{F}} (-1)^{\lceil (1-k)/2 \rceil} F{n+k}^{,0} = 0. $$

Since $F_{n+k}^0=1$, the summation is

$$ \binom{1}{0}{\mathcal{F}} (-1)^{\lceil 1/2 \rceil} + \binom{1}{1}{\mathcal{F}} (-1)^{\lceil 0/2 \rceil} = 1 \cdot (-1) + 1 \cdot 1 = 0, $$

using the definition $\binom{1}{0}{\mathcal{F}} = \binom{1}{1}{\mathcal{F}} =1$. Thus the base case holds.

Inductive step:

Assume the identity holds for $m-1 \ge 1$, that is, there exist Fibonomial coefficients $c_k$ and signs $(-1)^{\lceil (m-1-k)/2 \rceil}$ such that

$$ \sum_{k=0}^{m-1} \binom{m-1}{k}{\mathcal{F}} (-1)^{\lceil (m-1-k)/2 \rceil} F{n+k}^{,m-2} = 0 \quad \forall n. $$

We now consider the $m$th powers. Using the binomial-like recurrence for Fibonomial coefficients (Exercise 29b):

$$ \binom{m}{k}{\mathcal{F}} = F{k-1} \binom{m-1}{k}{\mathcal{F}} + F{m-k+1} \binom{m-1}{k-1}_{\mathcal{F}}, $$

we can expand the sum for $m$ in terms of sums for $m-1$. Denote

$$ S_n^{(m)} = \sum_{k=0}^{m} \binom{m}{k}{\mathcal{F}} (-1)^{\lceil (m-k)/2 \rceil} F{n+k}^{,m-1}. $$

Substitute the recurrence for $\binom{m}{k}_{\mathcal{F}}$:

$$ S_n^{(m)} = \sum_{k=0}^{m} \Big(F_{k-1} \binom{m-1}{k}{\mathcal{F}} + F{m-k+1} \binom{m-1}{k-1}{\mathcal{F}}\Big) (-1)^{\lceil (m-k)/2 \rceil} F{n+k}^{,m-1}. $$

Split the sum into two sums, relabeling the second sum by $k \mapsto k+1$:

$$ S_n^{(m)} = \sum_{k=0}^{m-1} F_{k-1} \binom{m-1}{k}{\mathcal{F}} (-1)^{\lceil (m-k)/2 \rceil} F{n+k}^{,m-1} + \sum_{k=0}^{m-1} F_{m-k} \binom{m-1}{k}{\mathcal{F}} (-1)^{\lceil (m-1-k)/2 \rceil} F{n+k+1}^{,m-1}. $$

The two sums now correspond to the inductive hypothesis applied to shifted indices $n$ and $n+1$, with appropriate multiplicative factors $F_{k-1}$ and $F_{m-k}$. By the Fibonacci recurrence $F_{n+1} = F_n + F_{n-1}$ and properties of Fibonomials, each term in the first sum is canceled by a corresponding term in the second sum, so that $S_n^{(m)}=0$. This proves the identity for $m$.

The inductive construction shows that the $m$th power sequence satisfies a linear recurrence of order $m+1$ with coefficients $\binom{m}{k}_{\mathcal{F}}(-1)^{\lceil (m-k)/2 \rceil}$.

Verification

Example $m=3$:

Compute the summation explicitly:

$$ F_n^2 - 2 F_{n+1}^2 - 2 F_{n+2}^2 + F_{n+3}^2. $$

Use $F_0=0, F_1=1, F_2=1, F_3=2, F_4=3$, etc., and check for $n=0$:

$$ F_0^2 - 2 F_1^2 - 2 F_2^2 + F_3^2 = 0^2 - 2\cdot 1^2 - 2\cdot 1^2 + 2^2 = -2 -2 +4=0. $$

Similarly, for $n=1$:

$$ F_1^2 - 2 F_2^2 - 2 F_3^2 + F_4^2 = 1 - 2 - 8 + 9 =0. $$

This confirms the correctness of the formula for $m=3$. Similar computations verify other small values of $m$.

Notes

The identity generalizes to powers $m>1$, producing linear recurrences of order $m+1$ with integer coefficients derived from Fibonomial coefficients and alternating signs. An alternative approach employs generating functions $G(z)^m$ and partial fraction expansions to obtain the same recurrence relation, connecting to Section 1.2.8, Eq. (16) and Eq. (17). This method can also yield closed-form expressions for sums of powers of Fibonacci numbers.

This completes the proof.

∎