I didn't do a lot of maths in my career, and we asked me to solve the following recurrence relation:
$$a_{n} = 11a_{n-1} - 40a_{n-2} + 48a_{n-3} + n2^n$$
with
$a_0 = 2$, $a_1 = 3$ and $a_2 = 1$
What is the procedure to solve such relation? So far, I just know that $a_n$ could be split into two difference recurrence relations (homogeneous and non-homogeneous) as $a_n = b_n + c_n$, where
$$b_n = 11b_{n-1} - 40b_{n-2} + 48b_{n-3}$$ and $$c_n = n2^n$$
Hint: let $a_n=2^{n}x_n\,$, then the recurrence becomes:
$$ 2^{n}x_{n} = 11 \cdot 2^{n-1}x_{n-1} - 40 \cdot 2^{n-2}x_{n-2} + 48 \cdot 2^{n-3}x_{n-3} + n\cdot 2^n \\ \iff\quad 2 x_n = 11 x_{n-1}-20 x_{n-2}+12 x_{n-3}+2n $$
Let $y_n=x_n-x_{n-1}\,$, then subtracting two consecutive relations in $x_n$ gives:
$$ 2y_n = 11 y_{n-1} -20y_{n-2}+12y_{n-3}+2 $$
The latter is a standard linear recurrence with constant coefficients and "nice" roots for the characteristic polynomial. Solve for $y_n$, then calculate $x_n$, then $a_n$.
$$ \begin{cases} \begin{align} 2 x_n &= 11 x_{n-1}-20 x_{n-2}+12 x_{n-3}+2n \ 2 x_{n-1} &= 11 x_{n-2}-20 x_{n-3}+12 x_{n-4}+2(n-1) \end{align} \end{cases} $$
Subtract:
$$\require{cancel} 2 (x_n-x_{n-1}) = 11 (x_{n-1}-x_{n-2})-20 (x_{n-2}-x_{n-3})+12 (x_{n-3}-x_{n-4})+ \cancel{2n} - \cancel{2n} +2 \ \iff\quad 2y_n = 11 y_{n-1}-20y_{n-2}+12 y_{n-3}+2 $$
– dxiv Jul 30 '17 at 19:58Just to offer another approach, generating functions can be used as well:
$\begin{align} G(x) &= \sum_{n=0}^{\infty} a_n x^n \\ G(x) &= 2x^0 + 3x^1 + x^2 + \sum_{n=3}^{\infty}(11a_{n-1} - 40a_{n-2} + 48a_{n-3} + n2^n)x^n \\ G(x) &= 2 + 3x + x^2 + 11\sum_{n=3}^{\infty}a_{n-1}x^n - 40\sum_{n=3}^{\infty}a_{n-2}x^n + 48\sum_{n=3}^{\infty}a_{n-3}x^n + \sum_{n=3}^{\infty}n2^nx^n \\ G(x) &= 2 + 3x + x^2 + 11x\sum_{n=2}^{\infty}a_{n}x^{n} - 40x^2\sum_{n=1}^{\infty}a_{n}x^{n} + 48x^3\sum_{n=0}^{\infty}a_{n}x^{n} + \sum_{n=3}^{\infty}n2^nx^n \\ G(x) &= 2 + 3x + x^2 + 11x(-a_{0}x^{0} - a_{1}x^{1} + \sum_{n=0}^{\infty}a_{n}x^{n}) - 40x^2(-a_{0}x^{0} + \sum_{n=0}^{\infty}a_{n}x^{n}) + 48x^3\sum_{n=0}^{\infty}a_{n}x^{n} + (- 2x -2 \cdot 2^2x^2 + \sum_{n=0}^{\infty}n2^nx^n) \\ G(x) &= 2 + 3x + x^2 + 11x(-2 - 3x + G(x)) - 40x^2(-2 + G(x)) + 48x^3G(x) + (- 2x -2 \cdot 2^2x^2 + (2 x)/(2 x - 1)^2) \end{align}$
Solve for $G(x)$:
$$G(x) = \frac{-160 x^4 + 244 x^3 - 132 x^2 + 27 x - 2}{(3 x - 1) (8 x^2 - 6 x + 1)^2}$$
Apply partial fraction decomposition:
$$G(x) = 49 \cdot \frac{1}{1 -3 x} - 38 \cdot \frac{1}{1 - 4 x} + 5 \cdot \frac{1}{(1 - 4 x)^2} - 12 \cdot \frac{1}{1 - 2 x} - 2 \cdot \frac{1}{(1 - 2 x)^2}$$
Take the $n$th coefficient of the resulting generating function, which will bring us to the final result:
$$a_n = 49 \cdot 3^n - 38 \cdot 4^n + 5 \cdot 4^n(n+1) - 12 \cdot 2^n - 2 \cdot 2^n (n+1)$$
You can try to find coefficients $k_{1}$ and $k_{2}$ so that taking $b_{n}=a_{n}-k_{1}a_{n-1}+k_{2}a_{n-2}$, we might have an equation of the form $b_{n}-\alpha b_{n-1}=n2^{n}$, for some $\alpha$. You can work it out and one possibility is $\alpha=4$, $b_{n}=a_{n}-7a_{n-1}+12a_{n-2}$(The root of the equation $x^{3}-11x^{2}+40x-48=0$ being 3,4,4). So you need to solve $b_{n}-4b_{n-1}=n.2^{n}$. You can find $b_{n}$ through telescoping.
After this, knowing $b_{n}$, taking $d_{n}=a_{n}-3a_{n-1}$, we get $d_{n}-4d_{n-1}=b_{n}$, and then you get $ d_{n}$ (knowing $b_{n}$) through telescoping, and then you finally get $a_{n}$ (now knowing $d_{n}$) again through telescoping.
The general way of solving this kind of problem is to define relation $G(n)$ as
$$G(n) = (a_n - 11a_{n - 1} + 40a_{n - 2} - 48a_{n - 3} = n2^n)$$
Then write out:
$$\begin{array} {rrl} G(n) = &(a_n + \dots &= n2^n) \\ G(n + 1) = &(a_{n + 1} + \dots &= 2n2^n + 2 \cdot 2^n) \\ G(n + 2) = &(a_{n + 2} + \dots &= 4 n 2^n + 8 \cdot 2^n) \\ \end{array}$$
until you have more equations than nonlinear terms per equation. Then let variables replace the nonlinear terms, $u = n2^n$ and $v = 2^n$ to get:
$$\begin{align} a_n + \dots &= u \\ a_{n + 1} + \dots &= 2u + 2v \\ a_{n + 2} + \dots &= 4u + 8v \\ \end{align}$$
2 variables, 3 equations, so you can eliminate $u$ and $v$ and you get:
$$a_{n+2} - 15 a_{n+1} + 88 a_{n} - 252 a_{n-1} + 352 a_{n-2} - 192 a_{n-3}=0 \tag{T}$$
And that is just a regular linear recursion. Note that if the characteristic polynomial of the linear part of $G(n)$ is $g'$, and the characteristic polynomial of (T) is $t'$, then $g'$ is polynomial factor of $t'$. So 3 roots of $t'$ are known and you only need to find the remaining $2$ if you wish to continue in the standard fashion.
In this case, the roots of $g'$ are $\{4, 4, 3\}$ so the roots of $t'$ are $\{4, 4, 3, 2, 2\}$, so the final equation is $a_n = (An + B)4^n + (Cn + D)2^n + E3^n$ based on whatever the initial conditions are.
