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.

$$a_{0} = 0$$ $$a_{1} = 1$$ $$a_{n} = a_{n-1} - a_{n-2}$$

I have to find the solution of this equation ($a_{n} = ...$, non-recursive, you know what I mean...). So let's pretend that:

$$ A(x) = \sum_{n=0}a_{n}x^{n}$$

Using this formula and the recursive equation I'm getting:

$$A(x) = xA(x) - x^{2}A(x)$$

Substituting $t = A(x)$, solving simple quadratic equation, and I'm getting two solutions:

$t = A(x) = \frac{1 - i\sqrt{3}}{2}$ or $t = A(x) = \frac{1 + i\sqrt{3}}{2}$

So actually this should be the right side of the generating function $A(x)$, it also has no variable so it already is a coefficient - the job is done.


However, the book shows different results, and they differ a lot. Let me write it:

$a_{n} = -\frac{i\sqrt{3}}{3}(\frac{1+i\sqrt{3}}{2})^{n mod6}$ or $a_{n} = \frac{i\sqrt{3}}{3}(\frac{1-i\sqrt{3}}{2})^{n mod6}$

What did I do wrong?

share|improve this question
1  
You assumed that the series converges, when it does not. –  fgrieu Apr 24 '13 at 17:57
    
How can I do this if it does not converge? –  khernik Apr 24 '13 at 18:06

5 Answers 5

up vote 1 down vote accepted

The trick is to forget about convergence. To encourage self-study, I will feature a slightly different series (the Fibonacci numbers), but the technique is the same.

$$a_n=a_{n-1}+a_{n-2} \implies a_nx^n=xa_{n-1}x^{n-1}+x^2a_{n-2}x^{n-2}\quad \text{for n}=2,3,\dots$$

Let $A(x)$ be the generating function of the sequence, $A(x):=\sum_{n=0}^{\infty}a_nx^n$.

$$A(x)-a_1x-a_0=x(A(x)-a_0)+x^2A(x)$$

Note that we subtract some terms from the sum. Next, plug in the initial conditions $a_0=0$ and $a_1=1$.

$$A(x)-1\cdot x-0=x(A(x)-0)+x^2A(x) \implies A(x)=\frac{x}{1-x-x^2}$$

Up to now, the only difference between the sequences was a sign. You should have arrived at $A(x)=\frac{x}{1-x+x^2}$.

Unfortunately, the following part is specific to the Fibonacci series. Now, we use the geometric series to obtain a closed formula.

$$\begin{align*}A(x)&=\frac{1}{\sqrt{5}\left(1-\frac{2}{\left(\sqrt{5}-1\right)}x\right)}-\frac{1}{\sqrt{5}\left(1+\frac{2}{\left(\sqrt{5}+1\right)}x\right)}=\\ &=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}\left(\frac{2}{\sqrt{5}-1}x\right)^n-\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}\left(-\frac{2}{\sqrt{5}+1}x\right)^n=\\ &=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}\left(\left(\frac{2\left(\sqrt{5}+1\right)}{4}\right)^n-\left(-\frac{2\left(\sqrt{5}-1\right)}{4}\right)^n\right)x^n\end{align*}$$

Finally, let us identify the coefficients of both expansions.

$$a_n=\frac{1}{\sqrt{5}}\left(\left(\frac{\sqrt{5}+1}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right) \implies a_n=0,1,1,2,3,5,8,13,\dots$$

share|improve this answer

The denominator of the generating function is clearly $1-x+x^2$ so given the initial values the generating function is $\dfrac{x}{1-x+x^2}$, though OEIS 128834 writes this as $\frac{x(1+x)}{1+x^3}$.

That should help you make some progress when you find the solutions of $1-x+x^2=0$, which are among the sixth roots of $1$.

share|improve this answer

You need some more thought. How can $A(x)$ satisfy $A(x) = xA(x) - x^{2}A(x)$ if the left-hand side has a term $x$ (because $a_1=1$) but the right-hand side has no term $x$...??

share|improve this answer
    
$A(x) = x + a_{2}x^{2} + a_{3}x^{3} + ...$, and now $B(x) = \sum x^{n}a_{n-1} = x^{2} + a_{2}x^{3} + ...$, so $xA(x) = B(x)$ –  khernik Apr 24 '13 at 18:34
    
Perhaps you need still more thought. –  GEdgar Apr 24 '13 at 18:35
    
Could you give me some more hints, or even a little one more? :P –  khernik Apr 24 '13 at 18:42
    
An extra hint is provided by user17762. Take that into account to adjust the equation $A(x) = xA(x) - x^{2}A(x)$ to get something that works. –  GEdgar Apr 24 '13 at 19:36

Note that $a_n = a_{n-1} - a_{n-2}$ is true only for $n \geq 2$. Hence, in the generating function, you need isolate the first two terms, i.e., the terms corresponding to $n=0$ and $n=1$.

share|improve this answer

You failed to take into account the fact that the recurrence holds only for $n\ge 2$. My preferred technique for dealing with the initial values is the one used in Graham, Knuth, & Patashnik, Concrete Mathematics. First assume that $a_n=0$ for all $n<0$. Then use Iverson brackets to add terms to the recurrence that yield the correct initial values. Here you’re starting with

$$a_n=a_{n-1}-a_{n-2}\;.$$

This actually gives the correct value $a_0=0$ on the assumption that $a_n=0$ for all $n<0$, but it incorrectly gives $a_1=0$ as well. To compensate, add a term $[n=1]$ that is $1$ when $n=1$ and $0$ otherwise:

$$a_n=a_{n-1}-a_{n-2}+[n=1]\;.$$

Now multiply through by $x^n$ and sum over $n\ge 0$ to get your generating function $A(x)$:

$$\begin{align*} A(x)&=\sum_{n\ge 0}a_nx^n\\ &=\sum_{n\ge 0}a_{n-1}x^n-\sum_{n\ge 0}a_{n-2}x^n+x\\ &=xA(x)-x^2A(x)+x\;, \end{align*}$$

so $$A(x)=\frac{x}{1-x+x^2}\;.$$

Decomposition into partial fractions then yields the desired result.

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.