Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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 at 1:02
    
Hoewever, you may take a look at this: oeis.org/A033539 –  user127.0.0.1 Feb 19 at 1:02
    
Have you studied any techniques for solving recurrence relations? –  Mhenni Benghorbal Feb 19 at 1:03
    
You can use this approach. –  Mhenni Benghorbal Feb 19 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 at 1:14

3 Answers 3

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:

$$b_{n+1}=2b_n+b_{n-1}$$

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:

$$B_n=\begin{pmatrix}b_{n+1}\\b_n\end{pmatrix}$$

So that we have:

$$B_n=\begin{pmatrix}2&1\\1&0\end{pmatrix}^{n-1}\begin{pmatrix}b_2\\b_1\end{pmatrix}$$

And then diagonalizing, etc.

share|improve this answer

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|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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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