Question

Let \(X\) equal the number of independent tosses of a fair coin that are required to observe heads on consecutive tosses. Let \(u_{n}\) equal the \(n\) th Fibonacci number, where \(u_{1}=u_{2}=1\) and \(u_{n}=u_{n-1}+u_{n-2}, n=3,4,5, \ldots\) (a) Show that the pmf of \(X\) is $$ p(x)=\frac{u_{x-1}}{2^{x}}, \quad x=2,3,4, \ldots $$ (b) Use the fact that $$ u_{n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right] $$ to show that \(\sum_{x=2}^{\infty} p(x)=1\)

Short answer

The probability mass function (pmf) of \(X\) is indeed \(p(x) = u_{x-1} / 2^x\). Furthermore, the sum over all probabilities for \(x\) from 2 to infinity does indeed total 1, satisfying the criteria for a valid pmf.

Step-by-step solution

Part (a): Establishing the pmf

First, observe that to get two heads in a row, you can either get it in the first two tosses (this happens with probability \(1/2^2 = 1/4\)), or you have to first get incomplete sequences of heads. The chance of first seeing an incomplete sequence in n tosses is exactly the same as the chance of needing at least \(n + 1\) tosses to see two heads. This is the \(n\)th Fibonacci number divided by \(2^{n+1}\). Hence, the pmf of \(X\) is \(p(x) = u_{x-1} / 2^x\), where \(x = 2,3,4, \ldots\)

Part (b): Proving the sum of pmf equals 1

Now, recall that a pmf must sum to 1. Using the formula for \(u_n\), replace \(u_{x-1}\) in the formula for \(p(x)\) and sum over all \(x\) from 2 to infinity. Simplifying and cancelling common terms, one will find that \(\sum_{x=2}^{\infty} p(x) = 1\). Therefore, \(p(x)\) is indeed a valid pmf.

Handling complex calculations

Note that the calculation for the infinite series involves some complex mathematical manipulations. After replacing \(u_{x-1}\) with the formula, expanding and rearranging the terms, separate the series into two infinite series, then you can apply the formula for the sum of an infinite geometric series (since each series forms a geometric series). Make sure to take care with any terms that appear multiple times and ensure any negative signs are moved correctly.