Show recursion in closed form

Question

I've got following sequence formula: $ a_{n}=2a_{n-1}-a_{n-2}+2^{n}+4$

where $ a_{0}=a_{1}=0$

I know what to do when I deal with sequence in form like this:

$ a_{n}=2a_{n-1}-a_{n-2}$ - when there's no other terms but previous terms of the sequence. Can You tell me how to deal with this type of problems? What's the general algorithm behind solving those?

Answer 1

Write: $$\begin{align}a_n &=2a_{n-1}-a_{n-2}+2^n+4\\ &=2(2a_{n-2}-a_{n-3}+2^{n-1}+4)-a_{n-2}+2^n+4\\ &=3a_{n-2}-2a_{n-3}+4\cdot2^{n-1}+4(1+2)\\ &=3(2a_{n-3}-a_{n-4}+2^{n-2}+4)-2a_{n-3}+8\cdot2^{n-2}+4(1+2)\\ &=4a_{n-3}-3a_{n-4}+11\cdot2^{n-2}+4(1+2+3)\end{align}$$

You can see a few patterns emerging.

• The coefficient of $a_{n-k}$ is $k+1$
• The coefficient of $a_{n-k-1}$ is $-k$.
• You end up with an additional term of $4(1+2+...+k)$.

What about the coefficient of $2^{n-k+1}$? This is $1,4,11,26,57,...$, where at each point, we double and add $k$ to the previous coefficient. This can be written as a separate relation: $$b_n=2b_{n-1}+n,\,\,\,\,\, b_1=1$$ which can be solved just as this one to give $$b_n=2^{n+1}-n-2$$

Substituting this in, we get $$a_n=(n+2)a_1-(n+1)a_0+[2^n-n-1]2^2+4\cdot\frac12 n(n-1)\\\implies a_n=2^{2+n}+2n^2-6n-4$$ after incorporating the initial conditions $a_0=a_1=0$.

Answer 2

One approach that works to get to the final form is to take the formal power series $$f(x) = \sum_{n=0}^{\infty} a_n x^n$$ and try and rewrite it in terms of itself. Applying the initial conditions where necessary: \begin{align} f(x) &= \sum_{n=0}^{\infty} a_n x^n\\ &= a_0 + a_1 x +\sum_{n=2}^{\infty} \left(2a_{n-1}-a_{n-2} + 2^n + 4\right) x^n\\ % &= 2\sum_{n=2}^{\infty}a_{n-1}x^n - \sum_{n=2}^{\infty}a_{n-2}x^n + \sum_{n=2}^{\infty}2^nx^n + 4\sum_{n=2}^{\infty}x^n\\ % &= 2\sum_{n=1}^{\infty}a_nx^{n+1} - \sum_{n=0}^{\infty}a_n x^{n+2} + \sum_{n=0}^{\infty}(2x)^{n+2} + 4\sum_{n=0}^{\infty}x^{n+2}\\ % &= 2x\left(\sum_{n=0}^{\infty}a_nx^n - a_0\right) - x^2\sum_{n=0}^{\infty}a_n x^n + 4x^2\sum_{n=0}^{\infty}(2x)^n + 4x^2\sum_{n=0}^{\infty}x^n\\ % &= 2xf(x) - x^2f(x) + 4x^2 \frac{1}{1-2x} + 4x^2 \frac{1}{1-x}\\ % &= (2x-x^2)f(x) + 4x^2\frac{(1-x)+(1-2x)}{(1-2x)(1-x)}\\ % &= (2x-x^2)f(x) + \frac{4x^2(2-3x)}{(1-2x)(1-x)} \end{align}

Solving for $f(x)$: $$f(x) = \frac{4x^2(2-3x)}{(1-2x)(1-x)(1-2x+x^2)} = \frac{4x^2(2-3x)}{(1-2x)(1-x)^3}$$

Applying partial fraction expansion and using the well-known result that $$\sum_{n=0}^{\infty} (n+1)(n+2)\dotsb(n+m)x^n = \frac{d^m}{dx^m}\left(\frac{1}{1-x}\right) = \frac{m!}{(1-x)^{m+1}}$$ we get

\begin{align} \sum_{n=0}^{\infty} a_n x^n &= \frac{4x^2(2-3x)}{(1-2x)(1-x)^3}\\ &= \frac{4}{1-2x} + \frac{4}{1-x} - \frac{12}{(1-x)^2} + \frac{4}{(1-x)^3}\\ &= 4\frac{1}{1-2x} + 4\frac{1}{1-x} - 12\frac{1!}{(1-x)^{1+1}} + 2 \frac{2!}{(1-x)^{2+1}}\\ &= 4 \sum_{n=0}^{\infty} (2x)^n + 4 \sum_{n=0}^{\infty} x^n - 12 \sum_{n=0}^{\infty} (n+1) x^n + 2 \sum_{n=0}^{\infty} (n+1)(n+2) x^n\\ &= \sum_{n=0}^{\infty} \left(4\cdot 2^n + 4 - 12(n+1) + 2(n+1)(n+2)\right)x^n\\ &= \sum_{n=0}^{\infty} \left(2^{n+2} + 2n^2 - 6n -4\right)x^n \end{align}

Equating coefficients, we find

$$a_n = 2^{n+2} + 2n^2 - 6n -4$$

Answer 3

Let $Sa_n=a_{n+1}$ be the shift operator on sequences. Then your equation becomes $$ \left(1-S^{-1}\right)^2a_n=2^n+4\tag1 $$ where $1-S^{-1}$ is the backward difference operator.

As with integration, we have a set of basic forms that can be validated by repeated backward difference: $$ \left(1-S^{-1}\right)^2n^2=2\tag2 $$ $$ \left(1-S^{-1}\right)^22^n=2^{n-2}\tag3 $$ $$ \left(1-S^{-1}\right)^2a_n=0\implies a_n=C_1n+C_2\tag4 $$ looking at $(2)$, $(3)$, and $(4)$, we see that $$ a_n=2^{n+2}+2n^2+C_1n+C_2\tag5 $$ Plugging in the conditions that $a_0=a_1=0$, we get $$ a_n=2^{n+2}+2n^2-6n-4\tag6 $$

Answer 4

$$\begin{align} a_{n+2} - 2a_{n+1} + a_{n} &= 4 \cdot 2^{n} + 4 \\ a_{n+1} - 2a_{n} + a_{n-1} &= 2 \cdot 2^{n} + 4 \\ a_{n} - 2a_{n-1} + a_{n-2} &= 1 \cdot 2^{n} + 4 \\ \end{align}$$

$$ \begin{bmatrix} 1 & -2 & 1 & 0 & 0 \\ 0 & 1 & -2 & 1 & 0 \\ 0 & 0 & 1 & -2 & 1 \\ \end{bmatrix} \begin{bmatrix} a_{n + 2} \\ a_{n + 1} \\ a_{n} \\ a_{n - 1} \\ a_{n - 2} \end{bmatrix} = \begin{bmatrix} 4 & 1 \\ 2 & 1 \\ 1 & 1 \\ \end{bmatrix} \begin{bmatrix} 2^n \\ 4 \end{bmatrix}$$

$$ \begin{bmatrix} 1 & -3 & 2 \end{bmatrix} \begin{bmatrix} 1 & -2 & 1 & 0 & 0 \\ 0 & 1 & -2 & 1 & 0 \\ 0 & 0 & 1 & -2 & 1 \\ \end{bmatrix} \begin{bmatrix} a_{n + 2} \\ a_{n + 1} \\ a_{n} \\ a_{n - 1} \\ a_{n - 2} \end{bmatrix} = \begin{bmatrix} 1 & -3 & 2 \end{bmatrix} \begin{bmatrix} 4 & 1 \\ 2 & 1 \\ 1 & 1 \\ \end{bmatrix} \begin{bmatrix} 2^n \\ 4 \end{bmatrix}$$

$$ \begin{bmatrix} 1 & -3 & 2 \end{bmatrix} \begin{bmatrix} 1 & -2 & 1 & 0 & 0 \\ 0 & 1 & -2 & 1 & 0 \\ 0 & 0 & 1 & -2 & 1 \\ \end{bmatrix} \begin{bmatrix} a_{n + 2} \\ a_{n + 1} \\ a_{n} \\ a_{n - 1} \\ a_{n - 2} \end{bmatrix} = \begin{bmatrix} 0 \end{bmatrix}$$

So the characteristic equation of the linear recursion is

$$(x^2 - 3x + 2)(x^2 - 2x + 1)$$

with roots $[2, 1, 1, 1]$, so the general solution is

$$a_n = C_0 2^n + (C_1 + C_2n + C_3n^2)1^n$$

where the coefficients $C$ can be determined form the initial conditions.