# Power series and Fibonacci sequence

## Contents

Here is a little fact about Fibonacci numbers and their relation to some power series.

Let us assume a fair coin is tossed independently until two consecutive heads are observed.^{1} The number of trials required to observe two heads follows a negative binomial distribution. We have to wait longer to observe the two heads in immediate succession. Consider the sequence $HTTHTHH$ and let $X+2$ be the number of trials required. Then in this case $X=5$. If we note $p_n=\Pr(X=n)$, enumerating the possible outcomes in the first two or three cases yields $p_0=\tfrac{1}{4}$ and $p_1=\tfrac{1}{8}$. A recursion relation can be constructed for larger values of $n$:

$$ p_n = \frac{1}{2}p_{n-1} + \frac{1}{4}p_{n-2}. $$

Using Mathematica, it is easy to verify the first terms of this recurrence:

```
RecurrenceTable[{a[n] == 0.5 a[n - 1] + 0.25 a[n - 2], a[0] == 0.25,
a[1] == 0.125}, a, {n, 50}]
```

The corresponding probability generating function can also be obtained via `GeneratingFunction`

. Note that it is also possible to use `RSolve`

instead of `RecurrenceTable`

, as shown in the following example where we generate the first terms of the Fibonacci sequence:

```
RecurrenceTable[{a[n] == a[n - 1] + a[n - 2], a[0] == 1,
a[1] == 1}, a, {n, 10}]
RSolve[{a[n] == a[n - 1] + a[n - 2], a[0] == 1, a[1] == 1}, a[n], n]
Table[a[n] /. First[%], {n, 10}]
```

Or, equivalently:

```
GeneratingFunction[
RSolve[{a[n] == a[n - 1] + a[n - 2], a[0] == 1, a[1] == 1}, a[n],
n], n, x] // FullSimplify
```

The generating function is $\frac{1}{1-x (x+1)}$ in this case.

Back to our initial power series. for which the PGF reads:

$$ \frac{1}{4} + \frac{1}{8}\theta + \frac{1}{8}\theta^2 + \frac{3}{32}\theta^3 + \frac{5}{64}\theta^4 + \mathcal{O}(\theta^5). $$

Upon inspection of the above expression, we have $p_n = 2^{-(n+2)}F_{n+1}$, where $F_k$ is the $k$-th Fibonacci number. Note that the PGF of the reciprocal of this serie is $4-2\theta-\theta^2+\mathcal{O}(\theta^5)$, hence the PGF of $X$ can be written as:

$$ A(\theta) = \mathbb{E}(\theta^X) = \frac{1}{4-2\theta-\theta^2}. $$

The more I read on discrete math and Euler problems, the more I find Fibonacci numbers hanging around all over the place

- Small, C.
*Expansions and Asymptotics for Statistics*. Chapman & Hall/CRC, 2010.^{[return]}