$$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?
$\endgroup$ 25 Answers
$\begingroup$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$$
$\endgroup$ $\begingroup$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$.
$\endgroup$ $\begingroup$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$...??
$\endgroup$ 4 $\begingroup$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$.
$\endgroup$ $\begingroup$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.
$\endgroup$
