Finding the closed form of the following recurrence.

Question

I have the recurrence relation

$a_n = a_{n-1} - 6a_{n-2} + 2^n$.

How do I find the closed form of that solution?

Answer 1

• solve the characteristic equation $x^2-x+6=0$
• it has two roots $r_1$ and $r_2$
• the solutions of homegeneous equation $h_n-h_{n-1}+6h_{n-2}=0$ are $h_n=\alpha(r_1)^n+\beta(r_2)^n$
• but since they are conjugate complexes a more suitable representation is $h_n=r^n(\alpha\cos(n\theta)+\beta\sin(n\theta))$
• find a particular solution of $p_n-p_{n-1}+6p_{n-2}=2^n$. Since $r_i\neq 2$ then you can search it under the form $p_n=\gamma\times2^n$
• the equation being linear then the general solution is $a_n=h_n+p_n$
• enventually determine $\alpha,\beta$ from initial values $a_0,a_1$ (not available for this problem).

Your problem is not the simpler one to begin with because it doesn't have nice coefficients.

To get familiarized with the method, have a look first at the examples provided on this website: Solving Recurrence Relations

Answer 2

$$ a_n=a_{n-1}-6a_{n-2}+2^n\tag1 $$ is equivalent to $$ \underbrace{\left(a_n-\frac12\cdot2^n\right)}_{\large b_n}=\underbrace{\left(a_{n-1}-\frac12\cdot2^{n-1}\right)}_{\large b_{n-1}}-6\underbrace{\left(a_{n-2}-\frac12\cdot2^{n-2}\right)}_{\large b_{n-2}}\tag2 $$ To solve $$ b_n=b_{n-1}-6b_{n-2}\tag3 $$ we can use the roots of $r^2-r+6=0$, i.e. $r=\frac{1\pm i\sqrt{23}}2$, to get solutions in the form $$ a_n=\frac12\cdot2^n+c_1\left(\frac{1+i\sqrt{23}}2\right)^n+c_2\left(\frac{1-i\sqrt{23}}2\right)^n\tag4 $$ Computing $c_1$ and $c_2$ requires a couple of values of $a_n$.

$(4)$ can be written in terms of trigonometric functions: $$ \begin{align} a_n &=\frac12\cdot2^n+6^{n/2}\,(c_1+c_2)\cos(n\theta)+6^{n/2}\,(c_1-c_2)\,i\sin(n\theta)\\ &=\frac12\cdot2^n+c_1^\prime6^{n/2}\cos(n\theta)+c_2^\prime6^{n/2}\sin(n\theta)\tag5 \end{align} $$ where $\theta=\cos^{-1}\left(\frac1{2\sqrt6}\right)$.

Answer 3

After robjohn's answer, let us consider the more general case of $$a_n = a_{n-1} - k\,a_{n-2} + 2^n$$ Let $$a_n=b_n +\frac{2^{n+2}}{k+2}\implies b_n=b_{n-1}-k\,b_{n-2}$$ So, the characteristic equation is $$r^2=r-k\implies r_{1,2}=\frac{1\pm\sqrt{1-4 k}}{2} $$ You could even let $b_n=2^{-n}\,c_n $ and get $$c_n=2c_{n-1}-4k \,c_{n-2}$$ leading to $$r^2=2r-4k\implies r_{1,2}=1 \pm\sqrt{1-4 k} $$