Solving the recurrence $a_n=aa_{n-1}+ba_{n-2}$ using formal power series.

Question

I am trying to solve this quesetion from Serge Lang's Complex analysis book.

Exercise II.1.6 (Difference Equations). Given complex numbers $a_0, a_1, a, b$ define $a_n$ for $n \geq 2$ by $$ a_n=a a_{n-1}+b a_{n-2} $$ If we have a factorization $$ T^2-a T-b=(T-\alpha)\left(T-\alpha^{\prime}\right), \quad \text { and } \alpha \neq \alpha^{\prime} $$ show that the numbers $a_n$ are given by $$ a_n=A \alpha^n+B \alpha^{\prime n} $$ with suitable $A, B$. Find $A, B$ in terms of $a_0, a_1, \alpha, \alpha^{\prime}$. HINT: Consider the power series $$ F(T)=\sum_{n=0}^{\infty} a_n T^n $$ Show that it represents a rational function, and give its partial fraction decomposition.

We first use the standard method of generating functions to write

$$\sum_{n=2}^\infty a_n T^n = \sum_{n=2}^\infty aa_{n-1}T^n + \sum_{n=2}^\infty b a_{n-2}T^n.$$

Now, expanding terms, we have

$$a_2T^2+a_3T^3+a_4T^4+\dots = aa_1T^2+aa_2T^3+aa_3T^4 +\dots ba_0T^2+ba_1T^3+ba_2T^4+\dots.$$

Then, letting $F(T) = \sum_{n=0}^\infty a_nT^n$, we can rewrite this as

$$F(T)(T^2-aT-b) = -aa_0T+a_1T^3+a_0T^2$$

which gives us the form of $F$ a a rational function, namely

$$F(T) = \frac{a_1T^3+a_0T^2-aa_0T}{(T^2-aT-b)} =\frac{a_1T^3+a_0T^2-aa_0T}{(T-\alpha)(T-\alpha')}.$$

Now, the question says to expand in partial fractions. The numerator is greater than the denominator, so we must perform polynomial long division. Doing this yields,

$$F(t) = (a_0+aa_1)+a_1T + \frac{(a_1b-a^2a)T + (a_0b+aa_1b)}{(T-\alpha)(T-\alpha')}.$$ Now, I am stuck. This is too messy to get anything useful from with partial fractions decomposition, and I can't figure out how to relate this back to obtain the form of the $a_n$. What can be done from here?

Answer 1

Hint.

From

$$ a_n x^n-a a_{n-1}x^n-b a_{n-2}x^n=0 $$

we have

$$ T(x) = \frac{\phi(x)}{1-ax-bx^2} = \frac{\phi(x)}{b}\left(\frac{A}{x-x_1}+\frac{B}{x-x_2}\right) $$

where $x_1,x_2$ are the roots from $1-ax-bx^2=0$ and $\phi(x)$ is the initial conditions polynomial. Here $T(x) = \sum a_k x^k$

Answer 2

Just for the heck of it, I am posting here my derivation of the power series for the general linear recurrence and the expansion in terms of the roots of the characteristic polynomial assuming that the roots are all simple.

This is a totally non-original working out of the general homogeneous linear recurrence.

If $a_n =\sum_{k=1}^m c_k a_{n-k} $ for $n \ge m$, find the generating function $A(x) =\sum_{n=0}^{\infty} a_n x^n $ in terms of $a_{0..m-1}$ and $c_{1..m}$.

(This is undoubtedly a duplicate, but I just wanted to work this out from scratch. The algebra and rearrangements of summations is complicated enough so that, as usual, I am hoping that someone might have a simpler derivation.)

Given the linear recurrence

$a_n =\sum_{k=1}^m c_k a_{n-k} $ for $n \ge m$.

Find the generating function $A(x) =\sum_{n=0}^{\infty} a_n x^n $ in terms of $a_{0..m-1}$ and $c_{1..m}$.

My answer is

$A(x) =\dfrac{\sum_{r=0}^{m-1} x^r(a_r-\sum_{k=1}^{r} c_{k} a_{r-k})}{1-\sum_{k=1}^m c_k x^k} $.

My derivation (and this is a derivation, not a verification).

Let $A_j(x) =\sum_{n=0}^{j} a_n x^n $ for $j = 0$ to $m-1$.

$\begin{array}\\ A(x) &=\sum_{n=0}^{\infty} a_n x^n\\ &=\sum_{n=0}^{m-1} a_n x^n+\sum_{n=m}^{\infty} a_n x^n\\ &=A_{m-1}(x)+\sum_{n=m}^{\infty} x^n\sum_{k=1}^m c_k a_{n-k}\\ &=A_{m-1}(x)+\sum_{k=1}^m c_k\sum_{n=m}^{\infty} x^n a_{n-k}\\ &=A_{m-1}(x)+\sum_{k=1}^m c_k x^k\sum_{n=m}^{\infty} x^{n-k} a_{n-k}\\ &=A_{m-1}(x)+\sum_{k=1}^m c_k x^k\sum_{n=m-k}^{\infty} x^{n} a_{n}\\ &=A_{m-1}(x)+\sum_{k=1}^m c_k x^k(\sum_{n=0}^{\infty} x^{n} a_{n}-\sum_{n=0}^{m-k-1} x^{n} a_{n})\\ &=A_{m-1}(x)+\sum_{k=1}^m c_k x^k(A(x)-A_{m-k-1}(x))\\ &=A_{m-1}(x)+A(x)\sum_{k=1}^m c_k x^k-\sum_{k=1}^m c_k x^kA_{m-k-1}(x)\\ \end{array} $

so $\begin{array}\\ A(x)(1-\sum_{k=1}^m c_k x^k) &=A_{m-1}(x)-\sum_{k=1}^m c_k x^kA_{m-k-1}(x)\\ &=A_{m-1}(x)-\sum_{k=0}^{m-1} c_{m-k} x^{m-k}A_{k-1}(x) \qquad k \to m-k\\ &=A_{m-1}(x)-\sum_{k=0}^{m-1} c_{m-k} x^{m-k}\sum_{n=0}^{k-1} a_n x^n\\ &=A_{m-1}(x)-\sum_{n=0}^{m-2}\sum_{k=n+1}^{m-1} c_{m-k} x^{m-k} a_n x^n\\ &=A_{m-1}(x)-\sum_{n=0}^{m-2}\sum_{k=n+1}^{m-1} c_{m-k} a_n x^{n+m-k}\\ &=A_{m-1}(x)-\sum_{n=0}^{m-2}\sum_{r=n+m-m+1}^{n+m-n-1} c_{m-n-m+r} a_n x^{r} \qquad r = n+m-k, k = n+m-r\\ &=A_{m-1}(x)-\sum_{n=0}^{m-2}\sum_{r=n+1}^{m-1} c_{r-n} a_n x^{r}\\ &=A_{m-1}(x)-\sum_{r=1}^{m-1}\sum_{n=0}^{r-1} c_{r-n} a_n x^{r}\\ &=\sum_{r=0}^{m-1} a_r x^r-\sum_{r=1}^{m-1}x^r\sum_{n=0}^{r-1} c_{r-n} a_n\\ &=a_0+\sum_{r=1}^{m-1} x^r(a_r-\sum_{n=0}^{r-1} c_{r-n} a_n)\\ &=\sum_{r=0}^{m-1} x^r(a_r-\sum_{n=0}^{r-1} c_{r-n} a_n)\\ &=\sum_{r=0}^{m-1} x^r(a_r-\sum_{n=1}^{r} c_{n} a_{r-n})\\ &=\sum_{r=0}^{m-1} x^r(a_r-\sum_{k=1}^{r} c_{k} a_{r-k})\\ &=\sum_{r=0}^{m-1} x^rb_r \qquad b_r=a_r-\sum_{k=1}^{r} c_{k} a_{r-k}\\ \end{array} $

Therefore

$A(x) =\dfrac{\sum_{r=0}^{m-1} x^rb_r}{1-\sum_{k=1}^m c_k x^k} =\dfrac{\sum_{r=0}^{m-1} x^r(a_r-\sum_{k=1}^{r} c_{k} a_{r-k})}{1-\sum_{k=1}^m c_k x^k} $.

Explicit values of the first few $b_r$.

$b_0 =a_0\\ b_1 = a_1-c_1a_0\\ b_2 = a_2-c_1a_1-c_2a_0\\ b_3 = a_3-c_1a_2-c_2a_1-c_3a_0\\ $

For $m=1$, when $a_n =c_1a_{n-1} $ for $n \ge 1 $, and the initial term is $a_0$, $$A(x) =\dfrac{a_0 }{1-c_1x} $$

For $m=2$, when $a_n =c_1a_{n-1}+c_2a_{n-2} $ for $n \ge 2 $, and the initial terms are $a_0$ and $a_1$, $$A(x) =\dfrac{a_0 +x(a_1-c_1a_{0})}{1-c_1x-c_2x^2} =\dfrac{a_0 +b_1x}{1-c_1x-c_2x^2} $$

---

Suppose $C(x) =1-\sum_{k=1}^m c_k x^k =\prod_{k=1}^m (1-d_kx) $ where all the $d_k$ are distinct and non-zero. We want to find the partial function expansion $e_{1..m}$ so that $\dfrac1{C(x)} =\dfrac1{1-\sum_{k=1}^m c_k x^k} =\sum_{j=1}^m \dfrac{e_j}{1-d_jx} $.

$\begin{array}\\ \dfrac1{C(x)} &=\sum_{j=1}^m \dfrac{e_j}{1-d_jx}\\ \text{so}\\ 1 &=\sum_{j=1}^m \dfrac{e_jC(x)}{1-d_jx}\\ &=\sum_{j=1}^m \dfrac{e_j\prod_{k=1}^m (1-d_kx)}{1-d_jx}\\ &=\sum_{j=1}^m e_j\prod_{k=1, k\ne j}^m (1-d_kx)\\ \end{array} $

Letting $x = \dfrac1{d_j}$, $1 =e_j\prod_{k=1, k\ne j}^m (1-\frac{d_k}{d_j}) =e_j\prod_{k=1, k\ne j}^m (\frac{d_j-d_k}{d_j}) $ so $e_j =\prod_{k=1, k\ne j}^m (\frac{d_j}{d_j-d_k}) $.

So

$\begin{array}\\ A(x) &=\dfrac{\sum_{r=0}^{m-1} x^rb_r}{1-\sum_{k=1}^m c_k x^k}\\ &=\sum_{r=0}^{m-1} x^rb_r\sum_{j=1}^m \dfrac{e_j}{1-d_jx}\\ &=\sum_{r=0}^{m-1} x^rb_r\sum_{j=1}^m e_j\sum_{i=0}^{\infty}(d_jx)^i\\ &=\sum_{j=1}^me_j\sum_{r=0}^{m-1} x^rb_r\sum_{i=0}^{\infty}d_j^ix^i\\ &=\sum_{j=1}^me_j\sum_{r=0}^{m-1} b_r\sum_{i=0}^{\infty}d_j^ix^{i+r}\\ &=\sum_{j=1}^me_j\sum_{r=0}^{m-1} b_r\sum_{i=r}^{\infty}d_j^{i-r}x^{i}\\ &=\sum_{j=1}^me_j\sum_{i=0}^{\infty}x^{i}\sum_{r=0}^{\min(m-1, i)} b_rd_j^{i-r}\\ &=\sum_{i=0}^{\infty}x^{i}\sum_{j=1}^me_j\sum_{r=0}^{\min(m-1, i)} b_rd_j^{i-r}\\ &=\sum_{i=0}^{m-1}x^{i}\sum_{j=1}^me_j\sum_{r=0}^{\min(m-1, i)} b_rd_j^{i-r}+\sum_{i=m}^{\infty}x^{i}\sum_{j=1}^me_j\sum_{r=0}^{\min(m-1, i)} b_rd_j^{i-r}\\ &=\sum_{i=0}^{m-1}x^{i}\sum_{j=1}^me_j\sum_{r=0}^{i} b_rd_j^{i-r}+\sum_{i=m}^{\infty}x^{i}\sum_{j=1}^me_j\sum_{r=0}^{m-1} b_rd_j^{i-r}\\ \end{array} $

For $n \ge m$,

$\begin{array}\\ a_n= &\sum_{j=1}^me_j\sum_{r=0}^{m-1} b_rd_j^{n-r}\\ &\sum_{j=1}^me_jd_j^n\sum_{r=0}^{m-1} b_rd_j^{-r}\\ &\sum_{j=1}^me_jf_jd_j^n \qquad f_j=\sum_{r=0}^{m-1} b_rd_j^{-r}\\ \end{array} $

Therefore if $$ a_n =\sum_{k=1}^m c_k a_{n-k} \text{ for } n \ge m\\ $$ where

$$ 1-\sum_{k=1}^m c_k x^k =\prod_{k=1}^m (1-d_kx) \text{ with all the } d_k \text{ distinct} $$ then $$a_n= \sum_{j=1}^me_jf_jd_j^n \text{ for } n \ge m\\ $$

where

$$b_r=a_r-\sum_{k=1}^{r} c_{k} a_{r-k} \text{ for }0 \le r \le m-1 $$ $$e_j =\prod_{k=1, k\ne j}^m (\frac{d_j}{d_j-d_k}) $$ $$f_j =\sum_{r=0}^{m-1} b_rd_j^{-r} $$

Note that for $n \ge m$,

$a_n =\sum_{j=1}^me_jf_jd_j^n $

so that, if $h$ is the index of the largest $d_j$, then

$a_n \approx e_hf_hd_h^n $

which is the well-known exponential growth.