Question

13.10. Suppose that a sequence (ao, a1, a2, ) of real numbers satisfies the recurrence relation an -5an-1+6an-20 for all n> 2. (a) What is the order of the linear recurrence relation? (b) Express the generating function of the sequence as a rational function. (c) Find a generic closed form solution for this recurrence relation. (d) Find the terms ao,a1,.. . ,a5 of this sequence when the initial conditions are given by ao 2 and a5 (e) Find the closed form solution when ao 2 and a 5.

Answer 1

a. This recurrence is of order 2.

b. We're looking for a function $A(x)$ such that

$A(x)=\displaystyle\sum_{n=0}^\infty a_nx^n$

Take the recurrence,

$\begin{cases}a_0=a_0\\a_1=a_1\\a_n-5a_{n-1}+6a_{n-2}=0&\text{for }n\ge2\end{cases}$

Multiply both sides by $x^{n-2}$ and sum over all integers $n\ge2$:

$\displaystyle\sum_{n=2}^\infty a_nx^{n-2}-5\sum_{n=2}^\infty a_{n-1}x^{n-2}+6\sum_{n=2}^\infty a_{n-2}x^{n-2}=0$

Pull out powers of $x$ so that each summand takes the form $a_kx^k$:

$\displaystyle\frac1{x^2}\sum_{n=2}^\infty a_nx^n-\frac5x\sum_{n=2}^\infty a_{n-1}x^{n-1}+6\sum_{n=2}^\infty a_{n-2}x^{n-2}=0$

Now shift the indices and add/subtract terms as needed to get everything in terms of $A(x)$:

$\displaystyle\frac1{x^2}\left(\sum_{n=0}^\infty a_nx^n-a_0-a_1x\right)-\frac5x\left(\sum_{n=0}^\infty a_nx^n-a_0\right)+6\sum_{n=0}^\infty a_nx^n=0$

$\displaystyle\frac{A(x)-a_0-a_1x}{x^2}-\frac{5(A(x)-a_0)}x+6A(x)=0$

Solve for $A(x)$:

$A(x)=\dfrac{a_0+(a_1-5a_0)x}{1-5x+6x^2}\implies\boxed{A(x)=\dfrac{a_0+(a_1-5a_0)x}{(1-3x)(1-2x)}}$

c. Splitting $A(x)$ into partial fractions gives

$A(x)=\dfrac{2a_0-a_1}{1-3x}+\dfrac{3a_0-a_1}{1-2x}$

Recall that for $|x|<1$, we have

$\displaystyle\frac1{1-x}=\sum_{n=0}^\infty x^n$

so that for $|3x|<1$ and $|2x|<1$, or simply $|x|<\dfrac13$, we have

$A(x)=\displaystyle\sum_{n=0}^\infty\bigg((2a_0-a_1)3^n+(3a_0-a_1)2^n\bigg)x^n$

which means the solution to the recurrence is

$\boxed{a_n=(2a_0-a_1)3^n+(3a_0-a_1)2^n}$

d. I guess you mean $a_0=2$ and $a_1=5$, in which case

$\boxed{\begin{cases}a_0=2\\a_1=5\\a_2=13\\a_3=35\\a_4=97\\a_5=275\end{cases}}$

e. We already know the general solution in terms of $a_0$ and $a_1$, so just plug them in:

$\boxed{a_n=2^n+3^n}$