# Show recursion in closed form

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?

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

• @JohnDoe I added those details. – adfriedman Nov 18 '17 at 23:32
• (+1) Great, good to see two different methods. – John Doe Nov 18 '17 at 23:38

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

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{a_{n} = 2a_{n - 1} - a_{n - 2} + 2^{n} + 4\,,\qquad a_{0} = a_{1} = 0:\ {\large ?}}$.

Note that $\ds{a_{n} - a_{n - 1} = a_{n - 1} - a_{n - 2} + \pars{2^{n} + 4}}$. Then, \begin{align} \underbrace{\sum_{k = 2}^{n}\pars{a_{k} - a_{k - 1}}} _{\ds{a_{n} - a_{1} = a_{n}}}\ &\ =\ \underbrace{\sum_{k = 2}^{n}\pars{a_{k - 1} - a_{k - 2}}} _{\ds{a_{n - 1} - a_{0} = a_{n - 1}}}\ +\ \underbrace{\sum_{k = 2}^{n}\pars{2^{k} + 4}}_{\ds{2^{n + 1} + 4n - 8}} \\[5mm] \implies a_{n} - a_{n - 1} & = 2^{n + 1} + 4n - 8 \end{align}

Similarly, \begin{align} \overbrace{\sum_{k = 2}^{n}\pars{a_{k} - a_{k - 1}}}^{\ds{a_{n} - a_{1} = a_{n}}}\ & \ =\ \sum_{k = 2}^{n}\pars{2^{k + 1} + 4k - 8} = \sum_{k = 1}^{n - 1}\pars{2^{k + 2} + 4k - 4} \\[5mm] & = 2^{3}\,{2^{n - 1} - 1 \over 2 - 1} + 4\,{\pars{n - 1}n \over 2} - 4\pars{n - 1} \end{align}
$$\bbx{a_{n} = 2^{n + 2} + 2n^{2} - 6n - 4\,,\qquad n = 0,1,2,\ldots}$$

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

• But in this case $i=0$ and $j=0$ – Igor Nov 18 '17 at 22:29
• @Igor yes, in this particular example, if you ignore the $2^n$ and $4$ as you wrote, and wanted to solve a problem like $$a_n=2a_{n-1}-a_{n-2}$$ in general, then this is how you would approach it. – John Doe Nov 18 '17 at 22:31
• John - well, I know how to deal with this type of equations. What I actually meant was how to solve the upper like ones – Igor Nov 18 '17 at 22:36
• @Igor I have edited my answer to give this solution. It is a similar method - iterate the $a_{n-1}$ inside the formula for $a_n$ and look for a pattern. – John Doe Nov 18 '17 at 23:23

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