Solving recursive sequence using generating functions

Question

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

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

score 1 · Answer 1 · answered Apr 24 '13 at 18:17

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

score 1 · Answer 2 · answered Apr 24 '13 at 18:27

1

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

answered Apr 24 '13 at 18:27

GEdgar

111,679

$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

score 1 · Answer 3 · answered Apr 24 '13 at 18:38

1

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

answered Apr 24 '13 at 18:38

Librecoin · Accepted Answer · 2013-04-24T20:31:14.447

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

score 0 · Answer 5 · answered Apr 24 '13 at 21:00

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.

Solving recursive sequence using generating functions

5 Answers5

Linked