Problem: Suppose that you flip a coin $n$ times and it turns out that no consecutive heads appear in the sequence. Let $E(n)$ be the expected number of heads that appear given this information. Find $ \lim_{n\to\infty} \frac{E(n)}{n}$. The answer is in the form of$\frac{a}{b+\sqrt{c}}$ for integers a,b,c with minimal c.
My approach: Any sequence of n coins having exactly k heads (none consecutive) will be of the form T...THT...THT...THT...T Let $x_1$ be the number of T's before the first H. Similarly define $x_i$ for i = $2,3,...,k+1$
Here, $\quad x_1$ and $x_{k+1}$ can be $0,1,... $ $\quad$ but $\quad$ $\forall$ i = $2,..,k\quad$ $ x_i = 1,2,...\quad$ (since we want no consecutive heads)
In order to use the multinomial approach, define new variables $y_i = x_i-1 $ for these $k-1$ variables.
Now, the number of ways to get such a sequence with k heads (no consecutive) = number of sol of the equation:
$x_1 + y_2+y_3+...+y_k+x_{k+1} = n - k,$ where all variables $\in 0, 1,..$
After getting the general term for the above, taking the summation over k and dividing by total number of possible outcomes and taking the limit of n.
$$\lim_{n\to\infty}\frac{E(n)}n = \frac1n \left( \frac{\sum_{k=0}^{k=(n+1)/2} k\cdot {{n-k+1} \choose {k}}}{\sum_{k=0}^{k=(n+1)/2} {{n-k+1} \choose {k}}} \right) $$
I can't seem to simplify the numerator. I've tried everything. Is this the correct approach? Is there a better one? Either way how do I find the above limit?
Let $S_n$ be a random variable modeling the number of Heads in a sequence of $n$ tosses.
You're looking for $E[S_n| \text{no }HH]$. Conditioning on the outcome of the first toss, $$ \begin{aligned} E[S_n| \text{no }HH] &= P(X_1=H|\text{no }HH)E[S_n| \text{no }HH, X_1=H] + P(X_1=T|\text{no }HH)E[S_n| \text{no }HH, X_1=T] \\&= P(X_1=H|\text{no }HH)E[S_n| \text{no }HH, X_1=H]+ P(X_1=T|\text{no }HH)E[S_{n-1}| \text{no }HH]. \end{aligned} $$ Given that $X_1=T$, the possible heads only appear at a rank $\geq 2$, hence you're essentially switching to an experiment with $n-1$ tosses instead of $n$, thus $E[S_n| \text{no }HH, X_1=T] = E[S_{n-1}| \text{no }HH]$.
Conditioning on the second toss and similar arguments yield $$E[S_n| \text{no }HH, X_1=H] = 1+E[S_{n-2}| \text{no }HH].$$
Leting $e_n=E[S_n| \text{no }HH] $ and $r_n =P(X_1=H|\text{no }HH)$, we have obtained the relation $$e_n = r_n(1+e_{n-2}) + (1-r_n) e_{n-1},$$ with initial values $e_1=\frac 12$ and $e_2=\frac 23$.
Define additionally $p_n = E[\text{no }HH|X_1=H]$ and $q_n=E[\text{no }HH|X_1=T]$. Conditioning on the second toss, we have $$p_n = \frac 12 q_{n-1}$$ and $$q_n = \frac 14 q_{n-2} +\frac 12 q_{n-1},$$ with initial values $q_1=q_2=1$. Therefore, $$q_n =\frac{2 \left(\frac{\sqrt{5}}{4}+\frac{1}{4}\right)^n}{\sqrt{5}+1}+\frac{6 \left(\frac{\sqrt{5}}{4}+\frac{1}{4}\right)^n}{\sqrt{5} \left(\sqrt{5}+1\right)}+\frac{4 \left(\frac{1}{4}-\frac{\sqrt{5}}{4}\right)^n}{\sqrt{5} \left(\sqrt{5}+1\right)}$$ and we get a closed form for $p_n$. By Bayes formula, $$r_n=\frac{p_n}{p_n+q_n}=\frac{\left(\sqrt{5}+5\right) 4^n \left(\left(\frac{1}{4} \left(\sqrt{5}+1\right)\right)^n-\left(\frac{1}{4} \left(1-\sqrt{5}\right)\right)^n\right)}{\left(\sqrt{5}-5\right) (-1)^n \left(\sqrt{5}-1\right)^n+2 \left(2 \sqrt{5}+5\right) \left(\sqrt{5}+1\right)^n}.$$
Recall that the recurrence relation is $$e_n = r_n(1+e_{n-2}) + (1-r_n) e_{n-1},$$ with initial values $e_1=\frac 12$ and $e_2=\frac 23$. It seems unlikely that it can be solved in closed form.
However, $r_n$ converges quickly to $\frac{3-\sqrt{5}}{2}$. An "approximate" recurrence relation is then $$\hat e_n = \frac{3-\sqrt{5}}{2}(1+\hat e_{n-2}) + (1-\frac{3-\sqrt{5}}{2}) \hat e_{n-1},$$ which has a closed form and we have $$\lim_n \frac{\hat e_n}{n} = \frac{5-\sqrt{5}}{10} = \frac 2{5+\sqrt 5}.$$