# Recurrence relation inhomogeneous relation

$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.

• solve the homogeneous equation and then try to find a special solution of the inhomogeneous one Commented Dec 12, 2016 at 12:45
• The characteristic polynomial of the homogenous recursion is $x^2-4x+4=(x-2)^2$ hence each sequence $a_n=p(n)2^n$ for some polynomial of degree $d$ is such that $a_n-4a_{n-1}+4a_{n-2}=q(n)2^n$ for some polynomial $q$ of degree $d-2$. To get $q(n)=n^2+1$, try $p(n)$ of degree $4$ with no term $n^1$ or $n^0$ since these would vanish. In other words, compute $q(n)=p(n)-2p(n-1)+p(n-2)$ for $p(n)=n^2$ (answer $2$), for $p(n)=n^3$ (answer $6n+b$) and for $p(n)=n^4$ (answer $12n^2+cn+d$) and deduce $p(n)=An^4+Bn^3+Cn^2$ solving $p(n)-2p(n-1)+p(n-2)=n^2+1$, then a particular solution is $a_n=p(n)2^n$.
– Did
Commented Dec 13, 2016 at 9:23

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.

• But how about the part B?? I have no idea how to do it Commented Dec 12, 2016 at 15:34
– mvw
Commented Dec 13, 2016 at 6:12
• Solving the recurrence using Mathematica's RSolve gives an answer for which $a_n$ is indeed of the form $p(n)2^n$ with $p(n)$ a fourth-order polynomial. (You say it for $b_n$, but of course the same is true for $a_n$.) So it doesn't seem pleasant no matter how you slice it... Commented Dec 13, 2016 at 6:50
• I also tried removing the inhomogenity by subtracting $b_{n+1} - b_{n}$. Then apply the process again. (Is this symbolic differentiation?) I end up with a homogeneous equation with characteristic polynomial $p(t) = t^5 - 5 t^4 + 10 t^3 - 10 t^2 + 10 t - 6$ or such. This features one real and four complex roots. Not sure if that would yiield a simple solution in the end.
– mvw
Commented Dec 13, 2016 at 8:36
• So the result I guessed is wrong? $a_n = (An^2 + Bn + C)2^n$ ? Commented Dec 13, 2016 at 9:12

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*}

\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*}