2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Your generating function result and computations are correct, as well as the closed form result. What makes you believe it is wrong ? $\endgroup$
    – Sasha
    Oct 27 '11 at 14:47
  • $\begingroup$ @Sasha,Wolfram Alpha says different... $\endgroup$ Oct 27 '11 at 15:02
  • $\begingroup$ Yes, I tried computing it and got wrong values $\endgroup$
    – Pedro
    Oct 27 '11 at 15:03
  • $\begingroup$ You mean to $1 + n$? Still no luck $\endgroup$
    – Pedro
    Oct 27 '11 at 15:41
  • $\begingroup$ 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. $\endgroup$
    – GarouDan
    Oct 27 '11 at 15:44
3
$\begingroup$

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.

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

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$

$\endgroup$
1
  • $\begingroup$ Finish after...have to go now... $\endgroup$
    – GarouDan
    Oct 27 '11 at 15:59
0
$\begingroup$

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

$\endgroup$

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.