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?


  • $\begingroup$ 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$. $\endgroup$ – 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 $$

| cite | improve this answer | |
  • $\begingroup$ how can we get the characteristic polynomial for this series? Thanks $\endgroup$ – akusaja Sep 8 '15 at 4:58
  • $\begingroup$ @robjohn please explain how you got the polynomial. $\endgroup$ – user220382 Sep 8 '15 at 5:01
  • $\begingroup$ @SanchayanDutta if $\lambda$ is an eigenvalue of $A$, so is $f(\lambda)$ of $f(A)$, $f$ a polynomial $\endgroup$ – Vim Sep 8 '15 at 5:10
  • $\begingroup$ @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.. $\endgroup$ – user220382 Sep 8 '15 at 5:11
  • $\begingroup$ @SanchayanDutta edited my comment $\endgroup$ – 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$.

| cite | improve this answer | |
  • 1
    $\begingroup$ (+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}$. $\endgroup$ – 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$.


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

| cite | improve this answer | |
  • $\begingroup$ How can we choose the $$b_n$$ for this series? Thanks $\endgroup$ – akusaja Sep 8 '15 at 4:53
  • $\begingroup$ 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 $\endgroup$ – akusaja Sep 8 '15 at 5:02
  • $\begingroup$ AH, yes, it is my mistake :) $\endgroup$ – 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}$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.