solve the recurrence relation $a_n = 7a_{n-1} - 16a_{n-2} +12a_{n-3} + n4^n $

Question

Solve the recurrence relation

$$a_n = 7a_{n-1} - 16a_{n-2} +12a_{n-3} + n4^n $$

With initial conditions:

$a_0 = −2$

$a_1 = 0$

$a_2 = 5$

I solve the homogenous part like that:

$$a_n - 7a_{n-1} + 16a_{n-2} -12a_{n-3} = 0 $$

$$ p(r) = r^3 -7r^2 + 16r - 12 $$

$$ p(r) = (r-2)^2(r-3) $$

But I am stucked with the non-homogenous part.

For $$ g(n) = 4^n $$ We can use $$ q(r) = A4^n $$ But for $$ g(n) = n4^n $$

What we should do?

Answer 1

$$a_n = 7a_{n-1} - 16a_{n-2} +12a_{n-3} + n4^n$$ Here $g(n)=n4^n$. Try $$a_n^p=(cn+d)4^n$$ for the particular solution. $c$ and $d$ are constants to be found.

Answer 2

It is worth noting that the generating function approach does not require such guessing. Let $A(z)=\sum_{n=0}^\infty a_n z^n$ be the ordinary generating function. Then the recurrence and initial conditions imply that \begin{align} A(z) &= a_0 z^0 + a_1 z^1 + a_2 z^2 + \sum_{n=3}^\infty \left(7a_{n-1} - 16a_{n-2} +12a_{n-3} + n4^n\right) z^n \\ &= -2 + 5z^2 + 7z \sum_{n=3}^\infty a_{n-1} z^{n-1} - 16z^2 \sum_{n=3}^\infty a_{n-2} z^{n-2} + 12z^3 \sum_{n=3}^\infty a_{n-3} z^{n-3} + \sum_{n=3}^\infty n (4z)^n \\ &= -2 + 5z^2 + 7z (A(z) - a_0 - a_1z) - 16 z^2 (A(z) - a_0) + 12 z^3 A(z) + \frac{(4z)^3(3-2(4z))}{(1-4z)^2} \\ &= -2 + 5z^2 + 7z (A(z) + 2) - 16 z^2 (A(z) + 2) + 12 z^3 A(z) + \frac{64z^3(3-8z)}{(1-4z)^2}, \end{align} So \begin{align} A(z) &= \frac{-2 + 5z^2 + 14z - 32 z^2 + \frac{64z^3(3-8z)}{(1-4z)^2}}{1-7z+16z^2-12z^3} \\ &= \frac{-2+30z-171z^2+632z^3-944z^4}{(1-2 z)^2 (1-3 z) (1-4 z)^2} \\ &= \frac{-5/2}{1-2 z} + \frac{39/2}{(1-2 z)^2}+\frac{61}{1-3 z} - \frac{96}{1-4 z} + \frac{16}{(1-4 z)^2} \\ &= \frac{-5}{2}\sum_{n=0}^\infty (2z)^n + \frac{39}{2}\sum_{n=0}^\infty \binom{n+1}{1}(2z)^n+61\sum_{n=0}^\infty (3z)^n - 96\sum_{n=0}^\infty (4z)^n + 16\sum_{n=0}^\infty \binom{n+1}{1}(4z)^n \\ &= \sum_{n=0}^\infty\left(\frac{-5}{2}\cdot 2^n + \frac{39}{2} (n+1)2^n + 61\cdot 3^n - 96\cdot 4^n + 16(n+1)4^n\right)z^n \\ &= \sum_{n=0}^\infty\left(17\cdot 2^n + \frac{39}{2} n2^n + 61\cdot 3^n - 80\cdot 4^n + 16n4^n\right)z^n, \end{align} which immediately implies that $$a_n = 17\cdot 2^n + \frac{39}{2} n2^n + 61\cdot 3^n - 80\cdot 4^n + 16n4^n.$$

Answer 3

Given

$$ a_n-7a_{n-1}+16a_{n-2}-12a_{n-3}= n^m 4^n $$

a particular solution can be obtained by assuming

$$ a^p_n = \left(\sum_{k=0}^{k=m}c_k n^k\right)4^n $$

for $m=1$ we have $c_0 = -80, c_1 = 16$

for $m=2$ we have $c_0 = 656,c_1=-160,c_2=16$

etc.