Solution to 2. Use generating functions to solve the recurrence relation an = 4an−1 − 4an−2 + … - Sikademy
Author Image

Archangel Macsika

2. Use generating functions to solve the recurrence relation an = 4an−1 − 4an−2 + n2, where a0 = 2, a1 = 5.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question




\displaystyle\sum_{n=2}^{\infin}a_nx^n-4\displaystyle\sum_{n=2}^{\infin}a_{n-1}x^{n}+4\displaystyle\sum_{n=2}^{\infin}a_{n-2}x^{n}=\displaystyle\sum_{n=2}^nn^2x^n

From the table

\displaystyle\sum_{n=0}^nn^2x^n=0+x+2^2x^2+3^2x^3+...=\dfrac{x(x+1)}{(1-x)^3}

G(x)-2-5x-4x(G(x)-2)+4x^2G(x)

=\dfrac{x(x+1)}{(1-x)^3}-x

G(x)(1-4x+4x^2)=\dfrac{x(x+1)}{(1-x)^3}-4x+2

G(x)=\dfrac{x^2+x}{(1-x)^3(1-2x)^2}+\dfrac{2}{1-2x}

\dfrac{x^2+x}{(1-x)^3(1-2x)^2}=\dfrac{A}{(1-x)^3}+\dfrac{B}{(1-x)^2}+\dfrac{C}{1-x}

+\dfrac{D}{(1-2x)^2}+\dfrac{E}{1-2x}



A(1-2x)^2+B(1-x)(1-2x)^2

+C(1-x)^2(1-2x)^2+D(1-x)^3

+E(1-x)^3(1-2x)=\dfrac{x^2+x}{(1-x)^3(1-2x)^2}

x=0:A+B+C+D+E=0

x=-1:9A+18B+36C+8D+24E=0

x=1:A=2

x=1/2:D=6

x=2:9A-9B+9C-D+3E=6



A=2, B=-3, C=-3, D=6, E=-2



G(x)=\dfrac{2}{(1-x)^3}-\dfrac{3}{(1-x)^2}-\dfrac{3}{1-x}

+\dfrac{6}{(1-2x)^2}-\dfrac{2}{1-2x}+\dfrac{2}{1-2x}

\def\arraystretch{1.5} \begin{array}{c:c} \dfrac{2}{(1-x)^3} & 2\dbinom{n+2}{2} \\ \\ -\dfrac{3}{(1-x)^2} & -3(n+1)\\ \\ -\dfrac{3}{1-x} & -3 \\ \\ \dfrac{6}{(1-2x)^2} & 6(n+1)(2^n) \end{array}


a_n=2\dbinom{n+2}{2}-3(n+1)-3+6(2^n)(n+1)

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-696-qpid-581