# Finding a closed-form formula for a sequence that is defined recursively

$$a_0 = 0, a_1 = 1 \quad \text{ and } \quad a_n = a_{n-1} + 2a_{n-2}\quad \text{ for }n\geq 2$$

a) Find $a_2,a_3,a_4,a_5$

b) Find a closed form-formula for $a_n$

I found the value to be $(a_n)_{n\in \Bbb N} = \{0, 1, 1, 3 , 5, 11, ...\}$

I have not the slightest clue how to find a closed form formula, so if anyone could help me out with this I would be greatly appreciated.

I've seen similar questions with answers talking about finding a geometric series, but I can assure that this question should not require knowledge of such since we have not done anything of the sort in class.

Is it just trial and error to find such a formula? Or is there a set method to follow? I noticed that the formula is very similar to the Fibonacci sequence: $$F(n) = F(n-1) + F(n-2)$$

Thanks.

• Have you learned about using the auxiliary equation to solve homogeneous second-order recurrences with constant coefficients? – Brian M. Scott Dec 14 '14 at 23:22
• @BrianM.Scott No. Never heard of such. – Riptyde4 Dec 14 '14 at 23:22
• I admit to being a bit mystified how you would be expected to solve such a problem if you don't know how it relates to geometric sequences. Have you at least been shown a proof of the closed-form formula for the $n$th Fibonacci number? – David K Dec 14 '14 at 23:25
• @Riptyde4: Okay; I’ll write up a more elementary approach. – Brian M. Scott Dec 14 '14 at 23:27
• @DavidK I have no idea, it was on our first test and I left it blank. I've never seen the closed-form formula for the fibonacci numbers – Riptyde4 Dec 14 '14 at 23:27

Without any of the usual theoretical tools, you’ll need to do a bit of pattern-recognition. Notice the following pattern:

\begin{align*} a_0=0&\\ a_1=1&=2\cdot0+1\\ a_2=1&=2\cdot1-1\\ a_3=3&=2\cdot1+1\\ a_4=5&=2\cdot3-1\\ a_5=11&=2\cdot5+1\\ a_6=21&=2\cdot11-1 \end{align*}

This suggests the first-order recurrence $a_n=2a_{n-1}+(-1)^{n-1}$. You can prove by induction that it follows from your second-order recurrence and initial conditions, but let’s hold off on that: it looks like a pretty solid guess, so let’s see what we can do with it. Specifically, we’ll try ‘unwinding’ it:

\begin{align*} a_n&=2a_{n-1}+(-1)^{n-1}\\ &=2\left(2a_{n-2}+(-1)^{n-2}\right)+(-1)^{n-1}\\ &=2^2a_{n-2}+2(-1)^{n-2}+(-1)^{n-1}\\ &=2^2\left(2a_{n-3}+(-1)^{n-3}\right)+2(-1)^{n-2}+(-1)^{n-1}\\ &=2^3a_{n-3}+2^2(-1)^{n-3}+2(-1)^{n-2}+(-1)^{n-1}\\ &\;\vdots\\ &=2^ka_{n-k}+\sum_{i=1}^k2^{i-1}(-1)^i\\ &\;\vdots\\ &=2^na_0+\sum_{i=1}^n2^{i-1}(-1)^i\\ &=\sum_{i=1}^n2^{i-1}(-1)^i\;, \end{align*}

since $a_0=0$. Finally,

$$\sum_{i=1}^n2^{i-1}(-1)^i=\sum_{i=0}^{n-1}2^i(-1)^{i+1}=-\sum_{i=0}^{n-1}(-2)^i\;,$$

which is just a geometric series, for which you should know a closed form. Once you have that, you should prove by induction that it actually does satisfy your original recurrence.

This ‘unwinding’ technique works surprisingly often with simple first-order recurrences.

• Nice solution. I would use the recursion relation to prove it by induction- which you have mentioned, but this works great as well. – voldemort Dec 14 '14 at 23:38
• Thanks, this helps a lot. But I noticed earlier you asked if I had heard of an "auxiliary equation to solve homogeneous second-order recurrences with constant coefficients." What is the difference between a first and second order recurrence relation? – Riptyde4 Dec 14 '14 at 23:45
• @Riptyde4: You’re welcome. The original recurrence is second-order: $a_n$ depends on $a_{n-2}$ as well as on $a_{n-1}$. In a first-order recurrence $a_n$ depends only on $a_{n-1}$ (and possibly some function of $n$). With a $k$-th order recurrence $a_n$ depends on the $k$ previous values (and possibly some function of $n$). – Brian M. Scott Dec 14 '14 at 23:47

One way to do this is to use generating functions.

Let $G(x)=\sum_{n=0}^{\infty}a_nx^n$.

We have the relation : $a_n=a_{n-1}+2a_{n-2}$.

Multiply both sides by $x^n$ and summing from $n=2$ to $\infty$ we get:

$G(x)-a_0-a_1x=x(G(x)-a_0)+2x^2G(x)$.

Then we get: $G(x)(1-x-2x^2)=a_0-a_0x+a_1x=x$ (since $a_0=0,a_1=1$).

So

\begin{align} G(x)&=\frac{x}{1-x-2x^2} \\ &=\frac{1}{3(1 - 2 z)} - \dfrac{1}{3 (1 + x)} \end{align}.

We can read off the coeficients of two geometric series:

\begin{align} a_n &= \frac{1}{3} \cdot 2^n - \frac{1}{3} (-1)^n \\ &= \frac{2^n - (-1)^n}{3} \end{align}

• You're missing a factor of 1/3 somewhere. – Math1000 Dec 14 '14 at 23:50
• @user38584: That cou;d be true. I might have made a mistake while doing the partial fraction. – voldemort Dec 14 '14 at 23:51
• Fixed the derivation (I hope...) – vonbrand Jul 27 '15 at 23:17
• It seems that the factors of 1/3 should not be there in the expression for G(x). – MadPhysicist Nov 2 '16 at 20:39
• Also, simple verification shows that this closed form does not produce correct items of the sequence. Am I missing something? – MadPhysicist Nov 2 '16 at 20:48

$a_n = a_{n-1} + 2a_{n-2} \to x^2 - x - 2 = 0 \to (x-2)(x+1) = 0 \to x = 2, -1 \to a_n = A2^n + B(-1)^n$. $a_0 = 0, a_1 = 1\to A+B=0, 2A-B=1 \to A = \dfrac{1}{3}, B = -\dfrac{1}{3} \to a_n = \dfrac{2^n -(-1)^n}{3}$.

Thus: $a_2 = \dfrac{2^2 - (-1)^2}{3} = 1, a_3 = 3, a_4 = 5, a_5 = 11$.

• Can you elaborate on your steps? I have no idea whats going on here. How did you get from the a(n) definition to x^2 - x - 2 = 0 – Riptyde4 Dec 14 '14 at 23:21
• $a_{n-2} \iff 1, a_{n-1} \iff x, a_{n} \iff x^2$ – DeepSea Dec 14 '14 at 23:25
• how are those related to one another – Riptyde4 Dec 14 '14 at 23:29
• Then you translate: $a_n-a_{n-1}-2a_{n-2} = 0 \to 1x^2-1x-2\cdot 1 = 0$ – DeepSea Dec 14 '14 at 23:31

Linear recurrence relations with constant coefficients produce exponentially growing terms in the sequence. Hence, we can assume the closed form solution to $$a_n$$ is some type of exponential function in $$n$$. Simply, let

$$a_n = r^n$$

for some constant $$r$$ to be determined. For the recurrence relation you provided, we can make a substitution:

$$r^n = r^{n-1} + 2r^{n-2}$$

Dividing both sides of the equation by $$r^{n-2}$$, knowing that $$r^{n-2}$$ is not zero for $$n>2$$, yields

$$r^2 = r + 2$$

Now the solution to $$r$$ is easier to find. This is known as the auxiliary equation or characteristic equation. So, we get $$r = -1$$ or $$r = 2$$. This makes it look like there are two solutions for $$a_n$$, one with $$r=-1$$ and the other with $$r=2$$, but really $$a_n = r^n$$ is some linear combination of the powers of each root (-1 and 2), which means

$$a_n = c_0 (-1)^n + c_1 (2)^n$$

where $$c_0$$ and $$c_1$$ are the linear coefficients. Make the substitutions $$a_0=0$$ and $$a_1=1$$ to get the following system of two equations:

$$0 = c_0 + c_1$$ $$1 = -c_0 + 2c_1$$

The solution for $$c_0$$ and $$c_1$$ gets plugged back into the expression for $$a_n$$ to get the final answer:

$$a_n = -\frac{1}{3}(-1)^n + \frac{1}{3}2^n$$

The method I just described here only works when there are two distinct characteristic roots (in this case, we had -1 and 2, which are different numbers, so this works). Otherwise, a minor change is needed to make it all work.