TAOCP 1.2.8 Exercise 13

Let A(z)=\sum_{n\ge0} a_n z^n be the generating function for the sequence $\langle a_n\rangle$.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.8: Fibonacci Numbers

Exercise 13. [M22] Express the following sequences in terms of the Fibonacci numbers, when $r$, $s$, and $c$ are given constants:

a) $a_0=r$, $a_1=s$; $a_{n+2}=a_{n+1}+a_n$, for $n \ge 0$.

b) $b_0=0$, $b_1=1$; $b_{n+2}=b_{n+1}+b_n+c$, for $n \ge 0$.

Verified: no
Solve time: -

Solution

(a)

Let

$$ A(z)=\sum_{n\ge0} a_n z^n $$

be the generating function for the sequence $\langle a_n\rangle$. From the recurrence relation,

$$ a_{n+2}=a_{n+1}+a_n, $$

we obtain

$$ A(z)=a_0+a_1z+\sum_{n\ge0} a_{n+2}z^{n+2}. $$

Substituting the recurrence gives

$$ A(z) = r+sz + \sum_{n\ge0}(a_{n+1}+a_n)z^{n+2}. $$

Hence

$$ A(z) = r+sz + z\sum_{n\ge0}a_{n+1}z^{n+1} + z^2\sum_{n\ge0}a_nz^n. $$

Since

$$ \sum_{n\ge0}a_{n+1}z^{n+1} = A(z)-a_0 = A(z)-r, $$

it follows that

$$ A(z) = r+sz+z(A(z)-r)+z^2A(z). $$

Therefore

$$ (1-z-z^2)A(z) = r+(s-r)z. $$

By Eq. (11),

$$ \frac{z}{1-z-z^2}=G(z) = \sum_{n\ge0}F_nz^n. $$

Also,

$$ \frac{1}{1-z-z^2} = \frac{G(z)}{z} = \sum_{n\ge0}F_{n+1}z^n, $$

because $F_0=0$. Thus

$$ A(z) = \frac{r}{1-z-z^2} + (s-r)\frac{z}{1-z-z^2} = r\sum_{n\ge0}F_{n+1}z^n + (s-r)\sum_{n\ge0}F_nz^n. $$

Comparing coefficients of $z^n$ yields

$$ a_n = rF_{n+1} + (s-r)F_n. $$

Using Eq. (6) with $m=2$,

$$ F_{n+2}=F_{n+1}+F_n, $$

so this may also be written as

$$ a_n = sF_n+rF_{n-1} \qquad (n\ge1). $$

The required expression is therefore

$$ \boxed{ a_n=rF_{n+1}+(s-r)F_n } $$

for all $n\ge0$.

(b)

Let

$$ B(z)=\sum_{n\ge0} b_n z^n. $$

From the recurrence relation,

$$ b_{n+2}=b_{n+1}+b_n+c, $$

we have

$$ B(z) = b_0+b_1z+\sum_{n\ge0}b_{n+2}z^{n+2}. $$

Since $b_0=0$ and $b_1=1$,

$$ B(z) = z + \sum_{n\ge0}(b_{n+1}+b_n+c)z^{n+2}. $$

Hence

$$ B(z) = z + z\sum_{n\ge0}b_{n+1}z^{n+1} + z^2\sum_{n\ge0}b_nz^n + c\sum_{n\ge0}z^{n+2}. $$

Because

$$ \sum_{n\ge0}b_{n+1}z^{n+1} = B(z), $$

and

$$ \sum_{n\ge0}z^{n+2} = \frac{z^2}{1-z}, $$

we obtain

$$ B(z) = z+zB(z)+z^2B(z)+\frac{cz^2}{1-z}. $$

Therefore

$$ (1-z-z^2)B(z) = z+\frac{cz^2}{1-z}. $$

Multiplying by $1-z$ gives

$$ (1-z)(1-z-z^2)B(z) = z-z^2+cz^2 = z+(c-1)z^2. $$

Hence

$$ B(z) = \frac{z+(c-1)z^2} {(1-z)(1-z-z^2)}. $$

Write this as

$$ B(z) = \frac{1}{1-z} \left( \frac{z}{1-z-z^2} + (c-1)\frac{z^2}{1-z-z^2} \right). $$

By Eq. (11),

$$ \frac{z}{1-z-z^2} = \sum_{n\ge0}F_nz^n, $$

and therefore

$$ \frac{z^2}{1-z-z^2} = \sum_{n\ge0}F_nz^{n+1}. $$

Since

$$ \frac{1}{1-z} = \sum_{m\ge0}z^m, $$

the coefficient of $z^n$ in $B(z)$ is

$$ b_n = \sum_{k=0}^nF_k + (c-1)\sum_{k=0}^{n-1}F_k. $$

By Eq. (6) with $m=n$ and $n=1$,

$$ F_{n+1}=F_n+F_{n-1}, $$

and induction gives

$$ \sum_{k=0}^nF_k = F_{n+2}-1. $$

Similarly,

$$ \sum_{k=0}^{n-1}F_k = F_{n+1}-1. $$

Substitution yields

$$ b_n = (F_{n+2}-1) + (c-1)(F_{n+1}-1). $$

Since

$$ F_{n+2}=F_{n+1}+F_n, $$

this simplifies to

$$ b_n = F_n+cF_{n+1}-c. $$

Therefore

$$ \boxed{ b_n=F_n+cF_{n+1}-c } $$

for all $n\ge0$.