# How to find the general formula for this recursive problem?

I want to ask about recursive problem.

Given: $$a_0= 11, a_1= -13,$$ and $$a_n= -a_{n-1} +2a_{n-2}.$$

What is the general formula for $$a_n$$ ?

I've already tried to find the first terms of this series. From there, I got:

$$a_2 = 35, a_3= -61,$$ and $$a_4= 131.$$

From there, I think I need to use the rule from arithmetic and geometric series to find the general formula that I want to find.

But, I cannot find the certain pattern from this series, because the differences is always changing, such that -24, 48, -96, 192.

From there I think the general formula for a_n should be including (-1)ⁿ. But, how can we deal with series 24,48,96,192?

It seems the series is geometric, but how can we find the formula?

Thanks

• The standard approach is to look for solutions of the form $x^n$ for some constants $x$, and then note that a linear combination of two solutions gives yet another solution. So you should get a solution of the form $A_1x_1^n + A_2x_2^n$. – Michael Sep 8 '15 at 4:49

Linear Recurrence Equations have typical solutions $a_n=\lambda^n$. Using this, we can compute the possible values of $\lambda$ for this equation from $$\lambda^n=-\lambda^{n-1}+2\lambda^{n-2}$$ which means, assuming $\lambda\ne0$, that $$\lambda^2+\lambda-2=0$$ This is the characteristic polynomial for the recurrence $$a_n=-a_{n-2}+2a_{n-2}$$

The characteristic polynomial is $x^2+x-2$ which has roots $1$ and $-2$. Thus, the sequence is $a_n=b(1)^n+c(-2)^n$. Plugging in the values for $n=0$ and $n=1$ gives $$a_n=3+8(-2)^n$$

• how can we get the characteristic polynomial for this series? Thanks – akusaja Sep 8 '15 at 4:58
• @robjohn please explain how you got the polynomial. – user220382 Sep 8 '15 at 5:01
• @SanchayanDutta if $\lambda$ is an eigenvalue of $A$, so is $f(\lambda)$ of $f(A)$, $f$ a polynomial – Vim Sep 8 '15 at 5:10
• @Vim truly speaking i did'nt get you...i agree my knowledge is limited to high school maths...but it would be nice if you could explain or provide suitable link.. – user220382 Sep 8 '15 at 5:11
• @SanchayanDutta edited my comment – Vim Sep 8 '15 at 5:12

A useful trick here is to use a generating function.

Let $f(x)=\sum\limits_{n=0}^\infty a_nx^n$. Then we have that $f(x)=a_0+a_1x+\sum\limits_{n=2}^\infty a_nx^n=11-13x+\sum\limits_{n=2}^\infty (-a_{n-1}+2a_{n-2})x^n$. (1) Note that for this last sum: $\sum\limits_{n=2}^\infty (-a_{n-1}+2a_{n-2})x^n=-x\sum\limits_{n=2}^\infty a_{n-1}x^{n-1}+2x^2\sum\limits_{n=2}^\infty a_{n-2}x^{n-2}$. (2) Then, re-indexing the summations yields:

(2) $= -x\sum\limits_{n=1}^\infty a_nx^n+2x^2\sum\limits_{n=0}^\infty a_nx^n=-x\cdot(f(x)-a_0)+2x^2\cdot f(x)$.

Rewriting (1) and solving for $f(x)$ then yields $f(x)=\frac{11-2x}{1+x-2x^2}$. Writing out the Taylor series for this function and equating coefficients will then yield a formula for $a_n$.

• (+1) generating functions are great, though sometimes finding the general term is not easy. Here, partial fractions is useful: $\frac{11-2x}{1+x-2x^2} =\frac8{1+2x}+\frac3{1-x}$. – robjohn Sep 8 '15 at 9:22

Let me try. Putting $b_n = a_{n+1} + 2a_n$, for $n \geq 1$, one has $$b_0=9,$$ and $$b_{n-1} = b_{n-2},\ \mbox{ for } n \geq 2.$$

Then one has $b_n = b_0 = 9$, for all $n$.

So, $a_{n+1} + 2a_n = 9,$ for all $n$.

Putting $c_n = a_n - 3$, one has $c_{n+1} + 2c_n = 0$ and $c_0 = 8$.

Thus, $c_n = -2c_{n-1} = (-2)^n c_0 = 8.2^n.(-1)^n$.

We can get $a_n = 8.2^n.(-1)^n + 3$.

EDIT:

The way chooses $b_n$ is a trick. We can solve this problem as follows.

Consider the equation: $a^2+a-2=0$. It has two solutions: $a_1=1$ and $a_2=-2$. Then, $x_n = \alpha a_1^n + \beta a_2^n$. Indeed, one has

$$x_{n+2} + x_{n+1} - 2x_n = \alpha a_1^n(a_1^2+a_1-2) + \beta a_2^n(a_2^2+a_2-2) = 0.$$

Now, we find $\alpha$ and $\beta$.

We have $x_0 = \alpha + \beta = 11$, $x_1 = \alpha - 2\beta = -13$. Then, $\alpha = 3$ and $\beta = 8$. We get $$x_n = 3 + 8(-2)^n$$

• How can we choose the $$b_n$$ for this series? Thanks – akusaja Sep 8 '15 at 4:53
• if we plug in n=0 in your formula, we didn't get the same initial value. So, maybe there is mistake in your formula? Thanks – akusaja Sep 8 '15 at 5:02
• AH, yes, it is my mistake :) – GAVD Sep 8 '15 at 5:08

There are two ways:

Firstly, you could guess the answer. After a bit of investigation, you ca see that the absolute values of the differences are growing by a factor of two, so we search for a connection between powers of two. And indeed, $a_n=-(-2)^{n+3}+3$ seems to work. We can prove this by induction.

Alternatively, you could try to find all the geometric sequences, which satisfy this recurrence. So assume, $b_n$ is geometric and $b_n=-b_{n-1}+2b_{n-2}$. We can now use the fact, that $b_n=c^nb_0$ for a certain constant $c$ (it is geometric). If we plug this in, we obtain: $$b_0c^n=-b_0c^{n-1}+2b_0c^{n-2}\iff c^2=-c+2\iff (c+2)(c-1)=0$$ So either $c=-2$ or $c=1$. So we know, that every sequence of the form $p_n=p_0(-2)^n$ and $q_n=q_0(1)^n=q_0$ has the desired property. Furthermore, even the linear combinations of $p_n$ and $q_n$ have the desired property. So we have to find $p_0$ and $q_0$ such that: $$a_n=p_n+q_n\implies 11=a_0=p_0+q_0\space\text{and}\space -13=a_1=-2p_0+q_0$$ We can solve these two equations to obtain $p_0=8$ and $q_0=3$ which yields $a_n=8(-2)^n+3=-(-2)^{n+3}+3$. Note, that this approach works generally for recurrence relations of the form $a_n=\lambda a_{n-1}+\mu a_{n-2}$.