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(A(x)-a_0-a_1x)/(x^2)-\frac{5(A(x)-a_0)}x+6A(x)=0`

Solve for
`A(x)`:

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

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

`A(x)=(2a_0-a_1)/(1-3x)+(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|<\frac13`, 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}`