Solution to Use generating functions to solve the recurrence relation an = 7an−1 − 16an−2 + 12an−3 … - Sikademy
Author Image

Archangel Macsika

Use generating functions to solve the recurrence relation an = 7an−1 − 16an−2 + 12an−3 + n4n , where a0 = −2, a1 = 0, a2 = 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

generating function:

a(x)=\sum a_nx^n

\displaystyle\sum_{n=3}^{\infin} (a_n -7a_{n−1} +16a_{n−2} - 12a_{n−3})x^n=\displaystyle\sum_{n=3}^{\infin} n4^nx^n


\displaystyle\sum_{n=3}^{\infin}a_nx^n=a(x)-a_0-a_1x-a_2x^2=a(x)+2-5x^2


\displaystyle\sum_{n=3}^{\infin}7a_{n-1}x^n=7x\displaystyle\sum_{n=3}^{\infin}a_{n-1}x^{n-1}=7x(a(x)-a_0-a_1x)=7x(a(x)+2)


\displaystyle\sum_{n=3}^{\infin}16a_{n-2}x^n=16x^2\displaystyle\sum_{n=3}^{\infin}a_{n-2}x^{n-2}=16x^2(a(x)-a_0)=16x^2(a(x)+2)


\displaystyle\sum_{n=3}^{\infin}12a_{n-3}x^n=12x^3\displaystyle\sum_{n=3}^{\infin}a_{n-3}x^{n-3}=12x^3a(x)


\displaystyle\sum_{n=3}^{\infin} (a_n -7a_{n−1} +16a_{n−2} - 12a_{n−3})x^n=


=a(x)+2-5x^2-7x(a(x)+2)+16x^2(a(x)+2)-12x^3a(x)=


=a(x)(1-7x+16x^2-12x^3)-14x+25x^2-12x^3+2


\displaystyle\sum_{n=3}^{\infin} n4^nx^n=\frac{x}{(1-4x)^2}


a(x)=\frac{x}{(1-7x+16x^2-12x^3)(1-4x)^2}+\frac{14x+25x^2-12x^3+2}{1-7x+16x^2-12x^3}


a(x)=\frac{6}{2x-1}+\frac{-1}{(2x-1)^2}+\frac{24}{4x-1}+\frac{4}{(4x-1)^2}+\frac{-27}{3x-1}+\frac{325}{2(2x-1)}+\frac{-55}{2(2x-1)^2}+\frac{647}{4x-1}+\frac{110}{(4x-1)^2}+


+\frac{-729}{3x-1}


a(x)=\frac{337}{2(2x-1)}-\frac{57}{2(2x-1)^2}+\frac{671}{4x-1}+\frac{114}{(4x-1)^2}-\frac{756}{3x-1}


a(x)=-\frac{337}{2}\displaystyle\sum_{n=0}^{\infin} 2^nx^n -671\displaystyle\sum_{n=0}^{\infin} 4^nx^n+756\displaystyle\sum_{n=0}^{\infin} 3^nx^n-\frac{57}{2}\displaystyle\sum_{n=0}^{\infin} \begin{pmatrix} n+1 \\ n \end{pmatrix}2^nx^n+


+114\displaystyle\sum_{n=0}^{\infin} \begin{pmatrix} n+1 \\ n \end{pmatrix}4^nx^n


a_n=-\frac{337}{2}2^n-671\cdot4^n+756\cdot3^n-\frac{57}{2}(n+1)2^n+114(n+1)4^n


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-684-qpid-569