A contest problem Starting with an empty string, we create a string by repeatedly appending one of the letters $H$, $M$, $T$ with probabilities $\frac{1}{4}$, $\frac{1}{2}$, $\frac{1}{4}$, respectively, until the letter $M$ appears twice consecutively.  What is the expected value of the length of the resulting string?
I would like if someone would tell if my different approach to solve the problem is right?
Here is the original solution from this PDF:

Let $E$ be the expected value of the resulting string. Starting from the empty string,
  
  
*
  
*We have a $\frac12$ chance of not selecting the letter $M$; from here the length of the resulting string is $1 + E$.  
  
*We have a $\frac14$ chance of selecting the letter $M$ followed by a letter other than $M$, which gives a string of length $2 + E$.  
  
*We have a $\frac14$ chance of selecting $M$ twice, for a string of length $2$.
  
  
  Thus, $E = \frac12(1 + E) + \frac14(2 + E) + \frac14(2)$. Solving gives $E = 6$.

My approach:
$$E = \frac{1}{4} \sum_{k = 1}^{\infty} \sum_{n = 1}^{{{\frac{k+1}{2}}}} k{k\choose n}\left(\frac{1}{2}\right)^n \left(\frac{1}{2}\right)^{k-n} = 6$$
Keeping the last two digits $MM$ and the rest is a combination of $M$ and $(HT)$ with probabilities half and one quarter. 
the code to run this formula:
Private Sub CommandButton1_Click()
Count = 0
For i = 1 To 100 Step 10
S = 0
For k = 1 To i
For n = 1 To WorksheetFunction.RoundDown((k + 1) / 2, 0)
Worksheets("Sheet1").Cells(1, 3) = k
Worksheets("Sheet1").Cells(1, 2) = n
S = S + k * (Worksheets("Sheet1").Cells(2, 1)) * (1 / 2) ^ n * (1 / 2) ^ (k - n)
Next n
Next k
Count = Count + 1
Worksheets("Sheet1").Cells(3, Count) = S
Next i
End Sub
Results :
$\sum_{k = 1}^{\infty} \sum_{n = 1}^{{{\frac{k+1}{2}}}} k{k\choose n}\left(\frac{1}{2}\right)^n \left(\frac{1}{2}\right)^{k-n} = 24$

 A: I don't see a simple way to modify your formula to make it correct.  
To do it by brute calculation, as you seem to intend, you need to compute $p_n$, the probability that the game ends on exactly the $n^{th}$ placement.  
As others have pointed out, the $H,T$ are red herrings.  Let's just say we had binary strings with letters $M,Q$ each with probability $\frac 12$.  We need to count the strings with no double $M's$.  Let $a_n$ be the number of such strings. 
It turns out that the $a_n$ are, essentially, the Fibonacci numbers.  To see this, let $b_n$ be the number of such strings that end in $M$, and $c_n$ the number that end in $Q$.  Then we easily see that $$a_n=b_n+c_n\;\;\&\;\;c_n=a_{n-1}\;\;\&\;\;b_n=c_{n-1}=a_{n-2}$$  It follows that $$a_n=a_{n-1}+a_{n-2}$$ which is, of course, the Fibonacci recursion.  We have $a_1=2$ and $a_2=3$ Sowith the standard enumeration of the Fibonacci numbers, with $F_0=0,\;F_1=1$ we get $a_n=F_{n+2}$  We then note that for your game to end precisely on the $n^{th}$ entry we need to get a string of type $b_{n-1}$ followed by an $M$.  From the above we see that there are $a_{n-3}=F_{n-1}$ ways to do this.  Of course any string of length $n$ occurs with probability $\frac 1{2^n}$.  Putting all this together we get $$E=\sum_{n=2}^{\infty} \frac {nF_{n-1}}{2^n}$$ Numerically, this sums to $6$, but this can be confirmed analytically via the generating function for the Fibonacci numbers.  Specifically we have $$F(z)=1+z+2z^2+3z^3+5z^4+\dots=\frac 1{1-z-z^2}\implies z\frac d{dz}\left[z^2F(z)\right]=z^2+z^3+2z^4+3z^5+\dots$$  and we compute $E$ by evaluating at $z=\frac 12$ which does indeed come to $E=6$.
A: Your formula represents a good idea, but is wrong. As mentioned in the comments, you need to replace the $1/4$ with a $1/2$ because $P(\neg M)=1/2$. Once you do that, your formula will be correct.
