<s>[INST] Suppose we roll a die repeatedly and let Tk be the number of rolls until some number appears k times in a row. Suppose we roll a die repeatedly and let Tk be the number of rolls until some number
appears k times in a row. (a) Find P(T2 = k) for each integer k ≥ 2. (b) Find E[T2].
I am thinking that P(T2=2) = (1/6)(1/6) ; P(T2=3) = (5/6)(1/6)^3 . So I was trying to develop the pattern : P(T2=k) = (5/6)^(k-2) * (1/6)^k . However, I run into the issue that I have with P(T2=4) : The first role has 5 options, the second has 4 (because it cannot be the previous OR the next number). So I cannot figure out the general formula.  
** I also originally thought that for all k>3, P(T2+k) would be zero. Is that correct or is the above reasoning better? 
Thanks!
 [/INST] We can  answer the question  for a die  with $n$ faces,  rolling until
some number appears $k$ times in row. We have for the probability that
we need $m$ rolls where $m\ge k$ from first principles
$$\mathrm{P}[T=m]
= \frac{1}{n^m} \frac{n}{n-1}
[z^m] (n-1) z^k \sum_{q\ge 0} (z+\cdots+z^{k-1})^q (n-1)^q
\\ = \frac{1}{n^m} \frac{n}{n-1}
[z^m] (n-1) z^k \sum_{q\ge 0} z^q (1+\cdots+z^{k-2})^q (n-1)^q
\\ = n \frac{1}{n^m}
[z^m] z^k \sum_{q\ge 0} z^q (1-z^{k-1})^q  (n-1)^q / (1-z)^q
\\ = n \frac{1}{n^m}
[z^m] z^k \frac{1}{1-(n-1)z(1-z^{k-1})/(1-z)}
\\ = n \frac{1}{n^m}
[z^m] z^k \frac{1-z}{1-z-(n-1)z+(n-1)z^{k}}
\\ = n \frac{1}{n^m}
[z^m] z^k \frac{1-z}{1-nz+(n-1)z^{k}}.$$
Let us verify that this is a probability distribution.
We sum the probabilities to obtain
$$n\sum_{m\ge k} \frac{1}{n^m}
[z^m] z^k \frac{1-z}{1-nz+(n-1)z^{k}}
= n \frac{1}{n^k} \frac{1-1/n}{(n-1)/n^{k}}
= \frac{n-1}{n-1} = 1$$
and the sanity check goes through.  We continue with the expectation.
$$\mathrm{E}[T] =
n\sum_{m\ge k} \frac{1}{n^m} m
[z^m] z^k \frac{1-z}{1-nz+(n-1)z^{k}}
\\ = n\sum_{m\ge k} \frac{1}{n^m}
[z^{m-1}] \left(z^k \frac{1-z}{1-nz+(n-1)z^{k}}\right)'
\\ = \sum_{m\ge k} \frac{1}{n^{m-1}}
[z^{m-1}]
\left(\frac{kz^{k-1}-(k+1)z^k}{1-nz+(n-1)z^{k}}
- \frac{(z^k-z^{k+1})((n-1)kz^{k-1}-n)}{(1-nz+(n-1)z^k)^2}
\right)
\\ = \frac{k/n^{k-1}-(k+1)/n^k}{(n-1)/n^{k}}
- \frac{(1/n^k-1/n^{k+1})((n-1)k/n^{k-1}-n)}{(n-1)^2/(n^k)^2}
\\ = \frac{nk-(k+1)}{n-1}
- \frac{(1-1/n)((n-1)k/n^{k-1}-n)}{(n-1)^2/n^k}
\\ = \frac{(n-1)k-1}{n-1}
- \frac{1}{n} \frac{((n-1)k/n^{k-1}-n)}{(n-1)/n^k}
\\ = k-\frac{1}{n-1}
- \frac{1}{n} \frac{n(n-1)k-n^{k+1}}{n-1}
= k-\frac{1}{n-1}
- \frac{(n-1)k-n^{k}}{n-1}.$$
This yields the desired answer
$$\bbox[5px,border:2px solid #00A000]{
\mathrm{E}[T] = \frac{n^k-1}{n-1}.}$$
</s>