[latexpage]
While I’m at it, I might as well write up the problem that inspired the last post. Here it is:

Flip a coin until you get consecutive heads, then stop. Let X represent the number of flips it took. Then flip another coin until you get three consecutive heads. Let Y represent the total number of flips there. Find Pr(X>Y).

We started this problem in the previous post. There we found that \(Pr(X=k)=F_{k-1}/2^k\) where \(F_k\) is the k-th Fibonacci number. From the homework problem in the last post, we can get that \(Pr(X>k)=F_{k+2}/2^k\). And the distribution of Y is fairly easy to derive along the same lines as X: it turns out to be
\[Pr(Y=k)=\frac{G_{k-2}}{2^k}\]
where \(G_k\) is the k-th Tribonacci number.

So!
\[Pr(X>Y)=\sum_{k=3}^{\infty}Pr(X>k)Pr(Y=k)=\sum_{k=3}^{\infty}\frac{F_{k+2}G_{k-2}}{2^{2k}}\]
which is approximately 0.21. Can anyone find a nice closed form solution of this? There are closed form solutions for the Fibonacci and Tribonacci numbers but they’re complicated. There are also matrix representations, which might help. Any ideas?