Solving the recurrence relation I'm interested in learning how can we solve this linear non-homogeneous recurrence relation?
$$a_z = 2a_{n-1} - 1a{n-2} + (s^2 + 1)$$
 A: Rewrite it as:
$$
a_{n + 2} = 4 a_{n + 1} - 4 a_n + (n^2 + 4 n + 5) 2^{n + 2}
$$
Define the generating function $A(z) = \sum_{n \ge 0} a_n z^n$. Multiply the recurrence by $z^n$ and sum over $n \ge 0$, noting that:
$$
z \frac{d}{dz} \sum_{n \ge 0} c_n z^n = \sum_{n \ge 0} n c_n z^n
$$
This gives:
$$
\frac{A(z) - a_0 - a_1}{z^2} = 4 \frac{A(z) - a_0}{z} - 4 A(z)
   + \left( 
       z \frac{d}{dz} \left(z \frac{d}{dz} \right)
          + 4 z \frac{d}{dz}
          + 5
    \right) \frac{4}{1 - 2 z}
$$
Compute the derivatives, work out the value of $A(z)$, split into partial fractions and expand. That gives $a_n$ explicitly. More details in Wilf's "generatingfunctionology". A computer algebra system at hand is nice.
A: Define the operator $T$ on sequences by $(T(x_n))_n = x_n- 2x_{n-1}$.  
If $x_n$ is of the form $P(n)2^n$ where $P$ is a polynomial of degree $k$, then $T(x_n)_n = (P(n)-P(n-1))2^n = Q(n)2^n$ where $Q(n) = P(n)-P(n-1)$ is of degree $k-1$.
Also, $\ker T$ is obviously the set of sequences of the form $a2^n$, so $T^{-1}(Q(n)2^n) = \{P(n)2^n / P(n)-P(n-1) = Q(n)\}$
You have $T(T(a_n))_n = b_n = (n^2+1)2^n$, and so $a_n \in T^{-1}(T^{-1}(b_n)$
First you have to find a polynomial $P_1$ such that $P_1(n)-P_1(n-1) = n^2+1$, which gives you $T^{-1}(b_n)$ up to $2^n$, then find a polynomial $P_2$ such that $P_2(n)-P_2(n-1) = P_1(n)$, which gives you the solutions up to $2^n$ and $n2^n$
A: If we do the standard thing and look for a solution of the homogeneous equation (ignoring the ($n^2+1)2^n$ part for the moment) of the form $a_n=r^n$ we find that $(r-2)^2=0$, so that $r=2$ is a double solution.
In this case the general solution for the homogeneous equation in $a_n$ becomes $a_n=(An+B)2^n$
Note that this is of the form $p(n)2^n$ which has also appeared on the right hand side, and we want a particular solution of the form $p(n)2^n$.
If we try $p(n)=cn+d$ we find that we always get zero. If $p(n)$ is quadratic, we get $E2^n$ where $E$ is constant. Because our homogeneous solution takes up two degrees (0 and 1) which we'd normally try, we have to add two to the degree to get a quadratic in $n$ on the RHS, so our particular solution uses a quartic of the form $wn^4+xn^3+yn^2$ (lower degrees just go to zero). $w, x,y$ are chosen to give $n^2+1$.
This approach can be proved in various ways, including generating functions.
A: Split the solution $a_n$ in a homogeneous piece $h_n$ and a particular piece $p_n$ such that $a_n = h_n + p_n$.  The homogeneous solution solves
$$a_n - 4 a_{n-1} + 4 a_{n-2} = 0 \implies a_n = A\, 2^n + B \, n\, 2^n$$
The particular solution should not overlap with the homogeneous solution.  Trial and error reveals that a solution of the form $C \, n^2 \, 2^n$ is not sufficient to produce the RHS.  Rather, a term $n^4 \, 2^n$ is necessary to produce the $n^2 \, 2^n$ piece on the RHS.  That said, lower-order terms are needed to produce the rest of the RHS.  Thus
$$p_n = C\,n^4 \, 2^n + D \, n^3\, 2^n + E\, n^2 \, 2^n$$
Plug this into the recurrence and determine the values of $C$, $D$, and $E$
You then need initial conditions to get $A$ and $B$.
A: $a_n=2^n\left(\frac{1}{12}n^4+\frac{1}{3}n^3+\frac{11}{12}n^2+\left(p-\frac{4}{3}\right)n+q\right)$, where $p, q$ are arbitrary constants. 
If $a_0$ and $a_1$ are known, then take $p=a_0-\frac{1}{2}a_1+\frac{8}{3}, \; q=a_0$.
