TAOCP 1.2.8 Exercise 21

Exercise 21. [M25] What is $\sum_{k=0}^{n} F_kx^k$?

Verified: no
Solve time: -

Solution

Let

$$ S_n(x)=\sum_{k=0}^{n}F_kx^k. $$

We seek a closed form for $S_n(x)$.

By the defining recurrence,

$$ F_k=F_{k-1}+F_{k-2} \qquad (k\ge2), $$

hence

$$ S_n(x) =F_0+F_1x+\sum_{k=2}^{n}(F_{k-1}+F_{k-2})x^k. $$

Since $F_0=0$ and $F_1=1$,

$$ S_n(x) =x+\sum_{k=2}^{n}F_{k-1}x^k+\sum_{k=2}^{n}F_{k-2}x^k. $$

Rewrite the sums:

$$ \sum_{k=2}^{n}F_{k-1}x^k =x\sum_{k=2}^{n}F_{k-1}x^{k-1} =x\sum_{j=1}^{n-1}F_jx^j =xS_n(x)-F_nx^{n+1}, $$

and

$$ \sum_{k=2}^{n}F_{k-2}x^k =x^2\sum_{k=2}^{n}F_{k-2}x^{k-2} =x^2\sum_{j=0}^{n-2}F_jx^j =x^2S_n(x)-F_{n-1}x^{n+1}-F_nx^{n+2}. $$

Therefore

$$ S_n(x) =x+xS_n(x)-F_nx^{n+1} +x^2S_n(x)-F_{n-1}x^{n+1}-F_nx^{n+2}. $$

Collecting terms gives

$$ (1-x-x^2)S_n(x) =x-(F_n+F_{n-1})x^{n+1}-F_nx^{n+2}. $$

Since

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

we obtain

$$ (1-x-x^2)S_n(x) =x-F_{n+1}x^{n+1}-F_nx^{n+2}. $$

Hence

$$ \sum_{k=0}^{n}F_kx^k =\frac{x-F_{n+1}x^{n+1}-F_nx^{n+2}}{1-x-x^2}. $$

Thus the required sum is

$$ \boxed{\sum_{k=0}^{n}F_kx^k =\frac{x-F_{n+1}x^{n+1}-F_nx^{n+2}}{1-x-x^2}.} $$

As a check, letting $n\to\infty$ and assuming $|x|<1/\phi$, the terms involving $x^{n+1}$ and $x^{n+2}$ vanish, leaving

$$ \sum_{k=0}^{\infty}F_kx^k =\frac{x}{1-x-x^2}, $$

which agrees with equation (11).

This completes the proof.

∎