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.

I am considering the following recurrence:

$a_0 = 1$; $a_1 = 2$

$a_{n} = 2 (a_{n - 1} + a_{n - 2})$

Then I proceeded with the generating function:

$F(x) = \displaystyle\sum_{n = 0}^\infty a_n x^n = 1 + 2x + \displaystyle\sum_{n = 2}^\infty a_{n} x^{n} = 1 + 2x + \displaystyle\sum_{n = 2}^\infty 2x^n(a_{n - 1} + a_{n - 2})$

$F(x) = 1 + 2x + \displaystyle\sum_{n = 2}^{\infty} 2x^{n} a_{n - 1} + \displaystyle\sum_{n = 2}^{\infty} 2x^{n} a_{n - 2}$

$F(x) = 1 + 2x + (2x \displaystyle\sum_{n = 2}^{\infty} x^{n - 1} a_{n - 1}) + (2x^{2} \displaystyle\sum_{n = 2}^{\infty} x^{n - 2} a_{n - 2})$

$F(x) = 1 + 2x + 2x(F(x) - 1) + 2x^{2}F(x)$

$F(x) = \frac{1}{1 - 2x - 2x^{2}}$ Let a, b be the roots of the quadratic.

$F(x) = \frac{1}{(x - a)(x - b)} = \displaystyle\sum_{n = 0}^{\infty} \frac{x^{n}(b^{-1 - n} - a^{-1 - n})}{\sqrt{3}}$

We should then have $a_{n} = \frac{b^{-1 - n} - a^{-1 - n}}{\sqrt{3}}$, but I know that this is false. Where have I gone wrong?

share|improve this question
    
Your generating function result and computations are correct, as well as the closed form result. What makes you believe it is wrong ? –  Sasha Oct 27 '11 at 14:47
    
@Sasha,Wolfram Alpha says different... –  pedja Oct 27 '11 at 15:02
    
Yes, I tried computing it and got wrong values –  Pedro Oct 27 '11 at 15:03
    
You mean to $1 + n$? Still no luck –  Pedro Oct 27 '11 at 15:41
    
Do you want a way to find this recurrence or find why your computations are wrong? $a(n)=\frac{1}{6} \left(3 \left(1-\sqrt{3}\right)^n-\sqrt{3} \left(1-\sqrt{3}\right)^n+3 \left(1+\sqrt{3}\right)^n+\sqrt{3} \left(1+\sqrt{3}\right)^n\right)$ If you didnt get the correct result post here. –  GarouDan Oct 27 '11 at 15:44

3 Answers 3

up vote 3 down vote accepted

OK, using the recurrence equation $a_0 = 1$, $a_1=2$, $a_2 = 6$, $a_3 = 16$, $a_4 = 44$ and $a_5=120$.

Verifying this with the generating function directly: $$ \frac{1}{1-2x - 2x^2} \sim \sum_{k=0}^5 (2 x+2 x^2)^k \sim 1+ 2x + 6 x^2 + 16 x^3 + 44 x^4 + 120 x^5 + o(x^5) $$

Now using roots of the denominator $1-2x-2x^2 = -2( x - a)(x-b)$, where $a= -\frac{1}{2} - \frac{\sqrt{3}}{2}$ and $b= -\frac{1}{2} + \frac{\sqrt{3}}{2}$. Therefore $$ \frac{1}{1-2x-2x^2 } = -\frac{1}{2}\frac{1}{x-a}\frac{1}{x-b}=-\frac{1}{2(a-b)} \left( \frac{1}{x-a} - \frac{1}{x-b} \right) $$ It is readily seen that $-\frac{1}{2(a-b)} = \frac{1}{2 \sqrt{3}}$ we thus get $$ \frac{1}{1-2x-2x^2 } = \sum_{n=0}^\infty x^n \frac{1}{2 \sqrt{3}} \left( -a^{-n-1} + b^{-n-1} \right) $$ Now check with WolframAlpha again, and scroll to the alternative forms.

share|improve this answer
    
Ah, thank you. It seems my error was taking $\frac{1}{1 - 2x - 2x^{2}} = \frac{1}{x - a} \frac{1}{x - b}$ –  Pedro Oct 27 '11 at 16:12
    
@Pedro: You may want to take a look at the comments under this answer. –  joriki Oct 27 '11 at 16:35

Let be $a(n)$ a geometric progression, or $a(n)=q^n$

So,

$a(n)=2a(n-1)+2a(n-2)$ becomes

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

so $q=0$ or

$q^2=2q+2$

So, $q_1=\frac{2+\sqrt{12}}{2}=1+\sqrt{3}$ or $q_2=\frac{2-\sqrt{12}}{2}=1-\sqrt{3}$.

and

$a(n)=bq_1^n+cq_2^n$

$a(0)=1$, $b+c=1$

$a(1)=2$

share|improve this answer
    
Finish after...have to go now... –  GarouDan Oct 27 '11 at 15:59

A simpler way to handle such is to write the recurrence as: $$ a_{n + 2} = 2 (a_{n + 1} + a_n) $$ multiply by $x^n$, sum over $n \ge 0$. Recognize the sums that result: $$ \frac{A(x) - a_0 -a_1 z}{z^2} = 2 \left( \frac{A(x) - a_0}{x} + A(x) \right) $$ Plugging in $a_0 = 1$ and $a_1 = 2$, solving for $A(z)$: $$ A(z) = \frac{1}{1 - 2 z - 2 z^2} = \frac{3 + \sqrt{3}}{6} \frac{1}{1 - (1 + \sqrt{3}) x} - \frac{3 - \sqrt{3}}{6} \frac{1}{1 - (1 - \sqrt{3}) x} $$ This is just two geometric series: $$ a_n = \frac{3 + \sqrt{3}}{6} \cdot (1 + \sqrt{3})^n - \frac{3 - \sqrt{3}}{6} \cdot (1 - \sqrt{3})^n $$

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.