aliquot

< a quantity that can be divided into another a whole number of time />

Power series and Fibonacci sequence

July 31, 2019

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}]

Mathematica plot

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


  1. Small, C. Expansions and Asymptotics for Statistics. Chapman & Hall/CRC, 2010. [return]
math statistics

See Also

» From Polya to Euler problem » Digit Sum » Euler Problems 1-10 » On premature optimization » Visual Statistics – Use R!