contestada

G identify the solution of the recurrence relation an = 6an − 1 – 8an − 2 for n ≥ 2 together with the initial conditions a0 = 4, a1 = 10.

Respuesta :

LammettHash
Via the generating function method, let

[tex]G(x)=\displaystyle\sum_{n\ge0}a_nx^n[/tex]

Then take the recurrence,

[tex]a_n=6a_{n-1}-8a_{n-2}[/tex]

multiply everything by [tex]x^n[/tex] and sum over all [tex]n\ge2[/tex]:

[tex]\displaystyle\sum_{n\ge2}a_nx^n=6\sum_{n\ge2}a_{n-1}x^n-8\sum_{n\ge2}a_{n-2}x^n[/tex]

Re-index the sums or add/remove terms as needed in order to be able to express them in terms of [tex]G(x)[/tex]:

[tex]\displaystyle\sum_{n\ge2}a_nx^n=\sum_{n\ge0}a_nx^n-(a_0-a_1x)=G(x)-4-10x[/tex]

[tex]\displaystyle\sum_{n\ge2}a_{n-1}x^n=\sum_{n\ge1}a_nx^{n+1}=x\sum_{n\ge1}a_nx^n=x\left(G(x)-a_0\right)=x(G(x)-4)[/tex]

[tex]\displaystyle\sum_{n\ge2}a_{n-2}x^n=\sum_{n\ge0}a_nx^{n+2}=x^2\sum_{n\ge0}a_nx^n=x^2G(x)[/tex]

So the recurrence relation is transformed to

[tex]G(x)-4-10x=6x(G(x)-4)-8x^2G(x)[/tex]
[tex](1-6x+8x^2)G(x)=4-14x[/tex]
[tex]G(x)=\dfrac{4-14x}{1-6x+8x^2}=\dfrac{4-14x}{(1-4x)(1-2x)}=\dfrac1{1-4x}+\dfrac3{1-2x}[/tex]

For appropriate values of [tex]x[/tex], we can express the RHS in terms of geometric power series:

[tex]G(x)=\displaystyle\sum_{n\ge0}(4x)^n+3\sum_{n\ge0}(2x)^n=\sum_{n\ge0}\bigg(4^n+3\cdot2^n\bigg)x^n[/tex]

which tells us that

[tex]a_n=4^n+3\cdot2^n[/tex]

Otras preguntas