Sign up ×

In my discrete math class we were given the problem of finding an explicit formula for this recurrence relation and proving its correctness via induction. $$a_n=2a_{n-1}+a_{n-2}+1, a_1 = 1, a_2=1.$$ I feel confident that I could prove the correctness of the formula through induction but I have no idea what the formula is. What kind of strategy should I use for solving recurrence relations like this?

share|cite|improve this question
What do you mean with "solution"? Are you looking for an explicit formula for $a_n$? – user127.0.0.1 Feb 19 '14 at 1:02
Hoewever, you may take a look at this: – user127.0.0.1 Feb 19 '14 at 1:02
Have you studied any techniques for solving recurrence relations? – Mhenni Benghorbal Feb 19 '14 at 1:03
You can use this approach. – Mhenni Benghorbal Feb 19 '14 at 1:07
@MhenniBenghorbal we haven't studied any techniques but most of the recurrence relations we've looked at have had fairly obvious formulas. – Cairn O. Feb 19 '14 at 1:14

3 Answers 3

If you let $b_n=a_n+\frac 12$, the constant disappears. Then the characteristic polynomial is $r^2-2r-1=0$. Find its roots.

share|cite|improve this answer

If you've done linear algebra, there are techniques for solving linear recurrence relations. A (second order) linear recurrence is one of the form $a_{n+1}=\lambda a_n+\mu a_{n-1}$. This one isn't quite linear because of the $+1$, so let's try and remove that. The obvious way is to define:


In the hopes that its behavior will reflect that of $a_n$ in a simple way. If you look at the error $\epsilon_n=a_n-b_n$:, you'll find that it satisfies the same recurrence relation as $a_n$, except that we get to pick the initial values of $\epsilon_n$, since this amounts to picking initial values of our simplified sequence $b_n$. So what initial values of $\epsilon_n$ would lead to a simple, predictable error term? Well, how about we look for initial values that will make $\epsilon_n$ a constant sequence? If you do the algebra, you'll find $\epsilon_1=\epsilon_2=-1/2$, and so we define:

$$b_1=a_1+1/2=3/2,\space b_2=a_2+1/2=3/2$$

So that now, $b_n=a_n+1/2$ for all $n$.

Anyway, now we have a linear recurrence relation. The idea of the linear algebra technique is to write:


So that we have:


And then diagonalizing, etc.

share|cite|improve this answer

Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write your recurrence as: $$ a_{n + 2} = 2 a_{n + 1} + a_n + 1 $$ Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums: $$ \frac{A(z) - a_0 - a_1 z}{z^2} = 2 \frac{A(z) - a_0}{z} + A(z) + \frac{1}{1 - z} $$ Solve for $A(z)$: $$ A(z) = \frac{3}{4} \cdot \frac{1}{1 - (1 + \sqrt{2}) z} + \frac{3}{4} \cdot \frac{1}{1 - (1 - \sqrt{2}) z} - \frac{1}{2} \cdot \frac{1}{1 - z} $$ Everything in sight are geometric series: $$ a_n = \frac{3}{4} \cdot (1 + \sqrt{2})^n + \frac{3}{4} \cdot (1 - \sqrt{2})^n - \frac{1}{2} $$ Proof by induction is superfluous, the derivation is the proof.

share|cite|improve this answer

Your Answer


