TAOCP 1.2.8 Exercise 12
Let \mathcal{G}(z)=\sum_{n\ge0}\mathcal{F}_n z^n be the generating function for the second order Fibonacci sequence.
Section 1.2.8: Fibonacci Numbers
Exercise 12. [M26] The "second order" Fibonacci sequence is defined by the rule
$$ \mathcal{F}0 = 0, \qquad \mathcal{F}1 = 1, \qquad \mathcal{F}{n+2} = \mathcal{F}{n+1} + \mathcal{F}_n + F_n. $$
Express $\mathcal{F}n$ in terms of $F_n$ and $F{n+1}$. [Hint: Use generating functions.]
Verified: no
Solve time: -
Setup
Let
$$ \mathcal{G}(z)=\sum_{n\ge0}\mathcal{F}_n z^n $$
be the generating function for the second order Fibonacci sequence. By definition,
$$ \mathcal{F}0=0,\qquad \mathcal{F}1=1, \qquad \mathcal{F}{n+2} = \mathcal{F}{n+1} + \mathcal{F}_n + F_n. $$
We seek an expression for $\mathcal{F}n$ in terms of $F_n$ and $F{n+1}$.
Let
$$ G(z)=\sum_{n\ge0}F_n z^n $$
be the Fibonacci generating function of Eq. (10). By Eq. (11),
$$ G(z)=\frac{z}{1-z-z^2}. $$
Solution
From the recurrence relation,
$$ \mathcal{F}{n+2} - \mathcal{F}{n+1} - \mathcal{F}_n = F_n. $$
Multiply by $z^{n+2}$ and sum over all $n\ge0$:
$$ \sum_{n\ge0}\mathcal{F}{n+2}z^{n+2} - \sum{n\ge0}\mathcal{F}{n+1}z^{n+2} - \sum{n\ge0}\mathcal{F}nz^{n+2} = \sum{n\ge0}F_n z^{n+2}. $$
Each sum may be rewritten in terms of $\mathcal{G}(z)$ and $G(z)$:
$$ \sum_{n\ge0}\mathcal{F}_{n+2}z^{n+2} = \mathcal{G}(z)-\mathcal{F}_0-\mathcal{F}_1z = \mathcal{G}(z)-z, $$
since $\mathcal{F}_0=0$ and $\mathcal{F}_1=1$;
$$ \sum_{n\ge0}\mathcal{F}_{n+1}z^{n+2} = z\bigl(\mathcal{G}(z)-\mathcal{F}_0\bigr) = z\mathcal{G}(z); $$
$$ \sum_{n\ge0}\mathcal{F}_nz^{n+2} = z^2\mathcal{G}(z); $$
and
$$ \sum_{n\ge0}F_n z^{n+2} = z^2G(z). $$
Hence
$$ \mathcal{G}(z)-z-z\mathcal{G}(z)-z^2\mathcal{G}(z) = z^2G(z). $$
Substituting Eq. (11),
$$ (1-z-z^2)\mathcal{G}(z)-z = z^2\frac{z}{1-z-z^2}. $$
Therefore
$$ (1-z-z^2)\mathcal{G}(z) = z+\frac{z^3}{1-z-z^2}, $$
and multiplication by $1-z-z^2$ gives
$$ (1-z-z^2)^2\mathcal{G}(z) = z(1-z-z^2)+z^3 = z-z^2. $$
Thus
$$ \mathcal{G}(z) = \frac{z-z^2}{(1-z-z^2)^2}. $$
Since
$$ G(z)=\frac{z}{1-z-z^2}, $$
we obtain
$$ \mathcal{G}(z) = \frac{1-z}{1-z-z^2}G(z). $$
Now
$$ \frac{1-z}{1-z-z^2} = 1+\frac{z^2}{1-z-z^2} = 1+zG(z), $$
by Eq. (11). Hence
$$ \mathcal{G}(z) = G(z)+zG(z)^2. $$
The coefficient of $z^n$ in $G(z)$ is $F_n$, and the coefficient of $z^n$ in $zG(z)^2$ equals
$$ \sum_{k=0}^{n-1}F_kF_{n-1-k}. $$
By Eq. (17), with $n$ replaced by $n-1$,
$$ \sum_{k=0}^{n-1}F_kF_{n-1-k} = \frac{1}{5}(n-2)F_{n-1} + \frac{2}{5}(n-1)F_{n-2}. $$
Therefore
$$ \mathcal{F}n = F_n + \frac{1}{5}(n-2)F{n-1} + \frac{2}{5}(n-1)F_{n-2}. $$
To express this in terms of $F_n$ and $F_{n+1}$ alone, use
$$ F_{n-1}=F_{n+1}-F_n, \qquad F_{n-2}=2F_n-F_{n+1}. $$
Substitution yields
$$ \mathcal{F}n = F_n + \frac{1}{5}(n-2)(F{n+1}-F_n) + \frac{2}{5}(n-1)(2F_n-F_{n+1}). $$
Collecting coefficients,
$$ \mathcal{F}n = \frac{1}{5}(n+4)F_n - \frac{1}{5}nF{n+1}. $$
Hence
$$ \boxed{ \mathcal{F}n = \frac{(n+4)F_n-nF{n+1}}{5} } $$
for all $n\ge0$.
Verification
The formula gives
$$ \mathcal{F}_0 = \frac{4F_0}{5} = 0, $$
and
$$ \mathcal{F}_1 = \frac{5F_1-F_2}{5} = 1. $$
For $n=2$,
$$ \mathcal{F}_2 = \frac{6F_2-2F_3}{5} = \frac{6-4}{5} = 1, $$
which agrees with
$$ \mathcal{F}_2 = \mathcal{F}_1+\mathcal{F}_0+F_0 = 1. $$
Assume the formula holds for $n$ and $n+1$. Then
$$ \begin{aligned} \mathcal{F}{n+2} &= \mathcal{F}{n+1} + \mathcal{F}n + F_n \[4pt] &= \frac{(n+5)F{n+1}-(n+1)F_{n+2}}{5} + \frac{(n+4)F_n-nF_{n+1}}{5} + F_n. \end{aligned} $$
Using $F_{n+2}=F_{n+1}+F_n$ and simplifying,
$$ \mathcal{F}{n+2} = \frac{(n+6)F{n+2}-(n+2)F_{n+3}}{5}, $$
which is the same formula with $n$ replaced by $n+2$. Thus the expression satisfies the defining recurrence.
Notes
The denominator of $\mathcal{G}(z)$ is $(1-z-z^2)^2$, a repeated version of the Fibonacci denominator. This indicates that $\mathcal{F}_n$ should be a linear polynomial in $n$ multiplied by Fibonacci terms, which explains the appearance of the coefficients involving $n$.