Recurrence relation inhomogeneous relation

Question

$a_n = 4a_{n-1} - 4a_{n-2} + (n^2 + 1)2^n$

a) Find the general solution of the associated homogeneous equation.

b) Find the solution of the non-homogeneous relation, $a_0 = 0, a_1 = 1$

My work:

part (a):

$a_n - 4a_{n-1} + 4a_{n-2} = (n^2 + 1)2^n$

$a_n - 4a_{n-1} + 4a_{n-2} = 0$

$n^2 - 4n + 4 = 0$

$(n - 2)^2 = 0$

$n = 2$

So, $a_n = A(2)^n + B(2)^nn$

Is my part (a) correct?

part (b):

The reasonable result of the particular solution will be $(An^2 + Bn + C)2^n$

But and then, I don't know how to continue even I have substituted the result into the equation.

Answer 1

Inserting your solution into the homogeneous equation one gets: \begin{align} 0 &= A 2^n + B n 2^n - 4(A 2^{n-1} + B (n-1) 2^{n-1}) + 4 (A 2^{n-2} + B (n-2) 2^{n-2} \\ &=A 2^n + B n 2^n - 2A 2^n- 2 B(n-1) 2^n + A 2^n + B(n-2) 2^n \\ &= (A + n B - 2A - 2 B(n-1) + A + B(n-2)) 2^n \\ &= 0 \cdot 2^n \\ &= 0 \end{align} So your a) part looks fine.

Regarding b):

The general solution will be $$ a_n = (A + B n) 2^n + b_n $$ where $b_n$ is some particular solution. The conditions require $$ 0 = a_0 = A + b_0 \\ 1 = a_1 = 2(A+B) + b_1 $$ so the asked for solution is $$ a_n = (-b_0 + ( (1-b_1)/2+b_0) n) 2^n + b_n $$ This leaves the problem of finding one particular solution $b_n$. Any will do. Assuming $$ b_n = p(n) 2^n $$ for some order $N$ polynomial $p$ seems to be a possible way. I end up with a fourth order polynomial after some lengthy calculation.

Answer 2

Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence shifted, multiply by $zn^n$ and sum over $n \ge 0$, recognize parts of the result:

$\begin{align*} a_{n + 2} &= 4 a_{n + 1} - 4 A_n + ((n + 2)^2 - 1) \cdot 2^{n + 2} \\ \sum_{n \ge 0} a_{n + 2} z^n &= 4 \sum_{n \ge 0} a_{n + 1} z^n - 4 \sum_{n \ge 0} a_n z^n + \sum_{n \ge 0} (n^2 + 4 n) \cdot 2^n z^n \\ \frac{A(z) - a_0 - a_1 z}{z^2} &= 4 \frac{A(z) - a_0}{z} - 4 A(z) + \sum_{n \ge 0} n^2 \cdot 2^n z^n + 4 \sum_{n \ge 0} n \cdot 2^n z^n \end{align*}$

To dispatch the last two sums, start with:

$\begin{align*} \frac{1}{1 - a z} &= \sum_{n \ge 0} a^n z^n \\ \sum_{n \ge 0} n a^n z^n &= z \frac{d}{d z} \sum_{n \ge 0} a^n z^n \\ &= z \frac{d}{d z} \frac{1}{1 - a z} \\ &= \frac{a z}{(1 - a z)^2} \\ \sum_{n \ge 0} n^2 a^n z^n &= z \frac{d}{d z} \frac{a z}{(1 - a z)^2} \\ &= \frac{a z(1 + 1 z)}{(1 - a z)^3} \end{align*}$

Pulling all together, and solving for $A(z)$:

$\begin{align*} A(z) &= \frac{1}{2 (1 - 2 z)^5} - \frac{3}{4 (1 - 2 z)^4} - \frac{3}{4 (1 - 2 z)^3} + \frac{9}{4 (1 - 2 z)^2} - \frac{5}{4 (1 - 2 z)} \end{align*}$

Remembering:

$\begin{align*} (1 + u)^{-m} &= \sum_{k \ge 0} \binom{-m}{k} u^k \\ &= \sum_{k \ge 0} (-1)^k \binom{k + m - 1}{m - 1} u^k \end{align*}$

we get:

$\begin{align*} a_n &= [z^n] A(z) \\ &= \frac{1}{2} \binom{k + 5 - 1}{5 - 1} \cdot 2^n - \frac{3}{4} \binom{k + 4 - 1}{4 - 1} \cdot 2^n - \frac{3}{4} \binom{k + 3 - 1}{3 - 1} \cdot 2^n + \frac{9}{4} \binom{k + 2 - 1}{2 - 1} \cdot 2^n - \frac{5}{4} \binom{k + 1 - 1}{1 - 1} \cdot 2^n \\ &= \frac{k^4 - 12 k^3 + 11 k^2 + 108 k - 60}{48} \cdot 2^n \end{align*}$