TAOCP 1.2.8 Exercise 15

Exercise 15. [M22] Let $f(n)$ and $g(n)$ be arbitrary functions, and for $n \ge 0$ let

$$ \begin{aligned} a_0&=0, & a_1&=1, & a_{n+2}&=a_{n+1}+a_n+f(n);\ b_0&=0, & b_1&=1, & b_{n+2}&=b_{n+1}+b_n+g(n);\ c_0&=0, & c_1&=1, & c_{n+2}&=c_{n+1}+c_n+xf(n)+yg(n). \end{aligned} $$

Express $c_n$ in terms of $x$, $y$, $a_n$, $b_n$, and $F_n$.

Verified: no
Solve time: -

Solution

Define

$$ d_n=c_n-xa_n-yb_n. $$

Since

$$ a_0=b_0=c_0=0,\qquad a_1=b_1=c_1=1, $$

we have

$$ d_0=0,\qquad d_1=1-x-y. $$

For $n\ge0$,

$$ \begin{aligned} d_{n+2} &=c_{n+2}-xa_{n+2}-yb_{n+2}\ &=(c_{n+1}+c_n+xf(n)+yg(n))\ &\qquad -x(a_{n+1}+a_n+f(n)) -y(b_{n+1}+b_n+g(n))\ &=(c_{n+1}-xa_{n+1}-yb_{n+1}) +(c_n-xa_n-yb_n). \end{aligned} $$

Hence

$$ d_{n+2}=d_{n+1}+d_n. $$

Thus $\langle d_n\rangle$ satisfies the Fibonacci recurrence.

Exercise 13(a) gives the general solution of

$$ u_{n+2}=u_{n+1}+u_n, $$

with initial conditions $u_0=r$, $u_1=s$, namely

$$ u_n=rF_{n-1}+sF_n. $$

Applying this with

$$ r=d_0=0,\qquad s=d_1=1-x-y, $$

yields

$$ d_n=(1-x-y)F_n. $$

Therefore

$$ c_n=xa_n+yb_n+d_n, $$

$$ c_n=xa_n+yb_n+(1-x-y)F_n. $$

Substitution verifies the initial conditions:

$$ c_0=0,\qquad c_1=x+y+(1-x-y)=1. $$

Also,

$$ \begin{aligned} c_{n+2} &=x(a_{n+2})+y(b_{n+2})+(1-x-y)F_{n+2}\ &=x(a_{n+1}+a_n+f(n)) +y(b_{n+1}+b_n+g(n))\ &\qquad +(1-x-y)(F_{n+1}+F_n)\ &=c_{n+1}+c_n+xf(n)+yg(n). \end{aligned} $$

Hence the formula satisfies the defining recurrence.

The required expression is therefore

$$ \boxed{c_n=xa_n+yb_n+(1-x-y)F_n.} $$