2
$\begingroup$

The generating function for the Fibonacci sequence is

$$F(x) =x/(1-x-x^2).$$

To work out the 20th value of the sequence I understand you somehow expand this and look at the coefficient of $x^{20}$. How exactly do you do this?

$\endgroup$
7
$\begingroup$

\begin{eqnarray*} {z\over 1-z-z^2}&=&z\sum_{k=0}^\infty (z+z^2)^k\\ &=&z\sum_{k=0}^\infty z^k(1+z)^k\\ &=&z\sum_{k=0}^\infty z^k \sum_{j=0}^k {k\choose j} z^j\\ &=&\sum_{k=0}^\infty \sum_{j=0}^k {k\choose j} z^{1+j+k} \end{eqnarray*}

From this we see that the coefficient of $z^N$ is $$\sum_{j=0}^{N-1}{N-1-j\choose j},$$ in particular the coefficient of $z^{20}$ is $${19\choose 0}+{18\choose 1}+{17\choose 2}+\cdots+{10\choose 9}.$$

$\endgroup$
  • $\begingroup$ Easily the simplest approach. Thus, 6765. $\endgroup$ – Did Feb 6 '14 at 17:50
4
$\begingroup$

You can do the following:

  1. Solve the equation $1-x-x^2=0$. The roots are $\frac{-1-\sqrt{5}}{2}$ and $\frac{-1+\sqrt{5}}{2}$.

  2. Then you have $1-x-x^2=-(x-\frac{-1-\sqrt{5}}{2})(x-\frac{-1+\sqrt{5}}{2})=-(x+\frac{1+\sqrt{5}}{2})(x+\frac{1-\sqrt{5}}{2})$

  3. $\frac{-x}{(x+\frac{1+\sqrt{5}}{2})(x+\frac{1-\sqrt{5}}{2})}=\frac{A}{(x+\frac{1+\sqrt{5}}{2})}+\frac{B}{(x+\frac{1-\sqrt{5}}{2})}$

  4. Find A and B then you can expand both fractions in geometric series.

$\frac{-x}{(x+\frac{1+\sqrt{5}}{2})(x+\frac{1-\sqrt{5}}{2})}=\frac{Ax+Bx+A\frac{1-\sqrt{5}}{2}+B+\frac{1+\sqrt{5}}{2}}{(x+\frac{1+\sqrt{5}}{2})(x+\frac{1-\sqrt{5}}{2})}=\frac{(A+B)x+A\frac{1-\sqrt{5}}{2}+B\frac{1+\sqrt{5}}{2}}{(x+\frac{1+\sqrt{5}}{2})(x+\frac{1-\sqrt{5}}{2})}$

Then $(A+B)=-1$ and $A\frac{1-\sqrt{5}}{2}+B\frac{1+\sqrt{5}}{2}=0$

This s system gives $A$ and $B$.

  1. Add the two series and you are done.
$\endgroup$
  • $\begingroup$ Could you expand step 4? I can't quite see what is going on. $\endgroup$ – marshall Feb 6 '14 at 13:08
3
$\begingroup$

If you calculate $F(0.01)$ in Windows calculator you'll get $0.010102030508132134559046368320032$. Look at pairs of digits and you'll see you get the Fibonacci sequence right up until it gets into the 3-digit range.

So a simplistic way to do it is to calcuate $F(10^{-5})$ to something like 105 digits of accuracy.

$F(10^{-5}) \approx 0.00001 00001 00002 00003 00005 00008 00013 00021 00034 00055 00089 00144 00233 00377 00610 00987 01597 02584 04181 06765 10946$

Looking at this, the twentieth 5-digit group is $06765$, which is indeed $f_{20}$.

You can also accomplish it with infinite precision integers.

$$F(10^{-a}) = \dfrac{10^{-a}}{1 - 10^{-2a} - 10^{-a}} = \dfrac{10^a}{10^{2a} - 1 - 10^a}$$

Using the fact that $f_n < 10^n$,

$$f_n = \lfloor 10^{n^2}F(10^{-n}) \rfloor \mod 10^n$$ $$ = \left\lfloor \dfrac{10^{n^2+n}}{10^{2n} - 1 - 10^n}\right\rfloor \mod 10^n$$

But who says we have to use decimals here? $f_n < 2^n$ too, and the following holds for $n > 1$.

$$f_n = \left\lfloor \dfrac{2^{n^2+n}}{2^{2n} - 1 - 2^n}\right\rfloor \mod 2^n$$

$\endgroup$
1
$\begingroup$

First, find the roots of your functions denominator $1-z-z^2$ which are $$z_\pm=-\frac{1\pm\sqrt{5}}{2}$$

Then find the partial fraction decomposition $$\frac{z}{1-z-z^2}=\frac{z}{(z-z_-)(z-z_+)}=\frac{a}{z-z_+}+\frac{b}{z-z_-}$$ which turns out to be $a=\tfrac{1}{2}(1-\tfrac{1}{\sqrt{5}})$ and $b=\tfrac{1}{2}(1+\tfrac{1}{\sqrt{5}})$

Now you can easily compute the $N$th derivative of the function which at $z=0$ tells you the coefficient $a_N$:

$$a_N=\frac{1}{N!}\partial_z ^N f(z)|_{z=0}=\frac{1}{N!}\partial_z^N\left(\frac{a}{z-z_+}+\frac{b}{z-z_-}\right)_{z=0}=-\frac{1}{2}\left( \frac{a}{z_+^{N+1}}+\frac{b}{z_-^{N+1}}\right)$$

Plugging in $a$, $b$ from above and $N=20$ tells you the result.

$\endgroup$
  • $\begingroup$ Why did you need to find the partial fraction decomposition first? $\endgroup$ – marshall Feb 6 '14 at 13:11
  • $\begingroup$ @marshall because it makes differentiation easier, if you seek a closed form in $n$ for $\partial_z^n (z-\alpha)^{-1}(z-\beta)^{-1}$ you will run into trouble, because the product rule will make the expression more complicated with each step, but in the decomposed form you can use $\partial_z^n(z-\alpha)^{-1}=(-1)^n n! (-\alpha)^{-n-1}$ which follows from simple induction. $\endgroup$ – flonk Feb 6 '14 at 14:35
  • $\begingroup$ I know this is a dim question.. but if I take the third derivative of $f(x) = x/(1-x-x^2)$ and evaluate it at $x=0$ I get $12$ which isn't right. Why is this? $\endgroup$ – marshall Feb 6 '14 at 17:12
  • 1
    $\begingroup$ @marshall I have to correct myself, multiplying the generator with $x$, i.e. $G(x)\to xG(x)$ corresponds to shifting the sequence $a_n\to a_{n+1}$, so it is still odd that you get $12$ which is not a Fibonacci number. $\endgroup$ – flonk Feb 10 '14 at 8:25
  • 1
    $\begingroup$ @marshall OK, now I resolved it, I stupidly forgot the factorial, i.e. $a_N = f^{(N)}(0)/N!$, not $f^{(N)}(0)$. In your case it gives $12/3!=2$. $\endgroup$ – flonk Feb 10 '14 at 20:58

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.