TAOCP 1.2.8 Exercise 14

Exercise 14. [M28] Let $m$ be a fixed positive integer. Find $a_n$, given that

$$ a_0 = 0, \qquad a_1 = 1, \qquad a_{n+2} = a_{n+1} + a_n + \binom{n}{m}, \quad n \ge 0. $$

Verified: yes
Solve time: 54s

Setup

We are asked to find a closed-form expression for the sequence $\langle a_n \rangle$ defined by

$$ a_0 = 0, \qquad a_1 = 1, \qquad a_{n+2} = a_{n+1} + a_n + \binom{n}{m}, \quad n \ge 0, $$

where $m$ is a fixed positive integer. The recurrence is linear with constant coefficients for the homogeneous part and an additive nonhomogeneous term $\binom{n}{m}$. The goal is to express $a_n$ explicitly in terms of the Fibonacci numbers and $m$.

By analogy with Section 1.2.8 and exercises 12 and 13, we anticipate a solution of the form

$$ a_n = F_n + \sum_{k=0}^{n-2} \binom{k}{m} F_{n-k-2}, $$

where $F_n$ is the usual Fibonacci sequence with $F_0 = 0$, $F_1 = 1$, and $F_{n+2} = F_{n+1} + F_n$.

Solution

Define the generating function

$$ A(z) = \sum_{n \ge 0} a_n z^n. $$

By the recurrence, for $n \ge 0$,

$$ a_{n+2} - a_{n+1} - a_n = \binom{n}{m}. $$

Multiplying both sides by $z^{n+2}$ and summing over $n \ge 0$, we obtain

$$ \sum_{n \ge 0} (a_{n+2} - a_{n+1} - a_n) z^{n+2} = \sum_{n \ge 0} \binom{n}{m} z^{n+2}. $$

The left-hand side expands as

$$ \sum_{n \ge 0} a_{n+2} z^{n+2} - \sum_{n \ge 0} a_{n+1} z^{n+2} - \sum_{n \ge 0} a_n z^{n+2} = A(z) - a_0 - a_1 z - z(A(z) - a_0) - z^2 A(z), $$

where we used the index shift formulas:

$$ \sum_{n \ge 0} a_{n+2} z^{n+2} = A(z) - a_0 - a_1 z, \quad \sum_{n \ge 0} a_{n+1} z^{n+2} = z(A(z) - a_0), \quad \sum_{n \ge 0} a_n z^{n+2} = z^2 A(z). $$

Substitute $a_0 = 0$ and $a_1 = 1$, giving

$$ A(z) - z - z A(z) - z^2 A(z) = z^2 \sum_{n \ge 0} \binom{n}{m} z^n. $$

Factor $A(z)$:

$$ A(z)(1 - z - z^2) - z = z^2 \sum_{n \ge 0} \binom{n}{m} z^n. $$

The generating function for $\binom{n}{m}$ is

$$ \sum_{n \ge 0} \binom{n}{m} z^n = \frac{z^m}{(1-z)^{m+1}}, $$

$$ A(z)(1 - z - z^2) - z = \frac{z^{m+2}}{(1-z)^{m+1}}. $$

Thus

$$ A(z) = \frac{z}{1 - z - z^2} + \frac{z^{m+2}}{(1-z)^{m+1} (1 - z - z^2)}. $$

The first term is the generating function of $F_n$ (by Eq. (11)), so

$$ \sum_{n \ge 0} F_n z^n = \frac{z}{1 - z - z^2}. $$

The second term represents the convolution of $F_n$ with the sequence $\binom{k}{m}$:

$$ \frac{z^{m+2}}{(1-z)^{m+1} (1 - z - z^2)} = z^2 \cdot \frac{z^m}{(1-z)^{m+1}} \cdot \frac{1}{1-z-z^2} = z^2 \sum_{k \ge 0} \binom{k}{m} z^k \sum_{j \ge 0} F_j z^j. $$

The coefficient of $z^n$ in the product is

$$ \sum_{k=0}^{n-2} \binom{k}{m} F_{n-k-2}. $$

Therefore

$$ a_n = F_n + \sum_{k=0}^{n-2} \binom{k}{m} F_{n-k-2}. $$

This gives an explicit formula for all $n \ge 0$.

Verification

Check initial values. For $n=0$:

$$ a_0 = F_0 + \sum_{k=0}^{-2} \binom{k}{m} F_{-2-k} = 0 + 0 = 0, $$

for $n=1$:

$$ a_1 = F_1 + \sum_{k=0}^{-1} \cdots = 1 + 0 = 1. $$

For $n=2$:

$$ a_2 = F_2 + \sum_{k=0}^{0} \binom{0}{m} F_0 = 1 + 0 = 1, $$

agreeing with the recurrence:

$$ a_2 = a_1 + a_0 + \binom{0}{m} = 1 + 0 + 0 = 1. $$

For general $n$, the recurrence holds:

$$ a_{n+2} = F_{n+2} + \sum_{k=0}^{n} \binom{k}{m} F_{n-k} = F_{n+1}+F_n + \sum_{k=0}^{n-2} \binom{k}{m} F_{n-k-2} + \binom{n-1}{m} F_0 + \binom{n}{m} F_{-2?}. $$

Carefully, by shifting indices:

$$ \sum_{k=0}^{n} \binom{k}{m} F_{n-k} = \sum_{k=0}^{n-2} \binom{k}{m} F_{n-k} + \binom{n-1}{m} F_1 + \binom{n}{m} F_0 = \sum_{k=0}^{n-2} \binom{k}{m} F_{n-k} + \binom{n-1}{m}. $$

Then $a_{n+2} = F_{n+2} + \sum_{k=0}^{n} \binom{k}{m} F_{n-k} = (F_{n+1}+F_n) + \sum_{k=0}^{n-2} \binom{k}{m} F_{n-k} + \binom{n-1}{m} = (F_{n+1} + \sum_{k=0}^{n-2} \binom{k}{m} F_{n-1-k}) + (F_n + \sum_{k=0}^{n-2} \binom{k}{m} F_{n-2-k} + \binom{n-1}{m}) = a_{n+1} + a_n + \binom{n}{m}$.

The recurrence is satisfied. This completes the verification.

Answer

$$ \boxed{a_n = F_n + \sum_{k=0}^{n-2} \binom{k}{m} F_{n-k-2}}. $$

Notes

An alternative approach is to solve the nonhomogeneous recurrence by the method of undetermined coefficients. For $n \ge m$, $\binom{n}{m}$ is a polynomial in $n$ of degree $m$, so one can seek a particular solution of the form $\sum_{i=0}^{m+1} c_i \binom{n-i}{m}$ convolved with the Fibonacci sequence. Generating functions, however, provide a uniform and compact derivation suitable for all $m$.