This week's puzzle is the following
Fix an integer $k\geq 2$. Denote by $X_k$ the (random) number of independent tosses with a fair coin until $k$ consecutive tails occur. Determine the probability distribution of $X_k$.
If we use $H$ for head and $T$ for tail, and for simplicy take $k=3$, then a coin toss until we hit $3$ consecutive tails might look like this
$$ TTHTHHTTHTTT $$We can decompose it into segments as this
$$ (TTH)(TH)(H)(TTH)TTT $$i.e., segements of less than 2 $T$ followed by 1 $H$, with 3 $T$ at the end.
This observation gives the following generating function
z=var('z')
w(k,z)=z^k*1/(1-z*(1-z^k)/(1-z))
show(w(k,z))
In other words, $a_{k,n}:=[z^n]w(k,z)$, the coefficient of $z^k$ in $w(k,z)$ is the number of coin flip sequence of length with $k$ consecutive T at the end and no such pattern anywhere else.
Let's expeirement a bit. The first few $a_{2,n}$ are
w(2,z).taylor(z,0,12).list()
It does not take long to see that this is the Fibonacci sequence. What about $a_{3,n}$?
w(3,z).taylor(z,0,12).list()
The pattern is also clear here.
$$ a_{3,n} = \begin{cases} 0 & (n<3)\\ 1 & (n=3) \\ a_{3,n-1}+a_{3,n-2}+a_{3,n-3} & (n > 3) \end{cases} $$The recursion is similar to that of Fibonacci, but of order $3$ instead of $2$.
A bit more experiment actually shows that
$$ a_{k,n} = \begin{cases} 0 & (n=0)\\ F_n^{(k)} & (n>0) \\ \end{cases} $$where $F_n^{(k)}$ are the $k$-nacci numbers.
To show this is true, we just need to verify the generating function $w(k,z)$ satisfies the following recursion
$$ w(k,z)-z^k = \sum_{j=1}^k z^j w(k,z) $$And we can check it is true easily.
k, j=var('k,j')
eqn=w(k,z)-z^k==sum(z^j*w(k,z), j,1,k)
bool(eqn)
In conclusion, since any fair coin toss sequence of length $n$ has probability $1/2^n$, we have the distribution of $X_k$ by $$ P(X_k = n) = a_{k,n}2^{-n} = \begin{cases} 0 & (n=0) \\ F_n^{(k)}2^{-n} & (n \ge 1) \end{cases} $$