Solving the recurrence relation

Question

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

Answer 1

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.

Answer 2

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$

Answer 3

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.

Answer 4

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

Answer 5

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