If you toss a coin $n$ times, there are $2^n$ possible sequences of heads and tails. Let $E_n$ be the set of sequences which do NOT contain two consecutive heads and $e_n$, the number of sequences in $E_n$.
Thus $E_3$ $=$ $\{$ $TTT$, $TTH$, $THT$, $HTT$, $HTH$ $\}$ and $e_3$ $=$ $3$.
How many elements of $E_n$ have $T$ as the first toss?
Please can anyone help me out here?
Well, let's say we have some sequence $TXXXX...$ in $E_n$. Now, take the $T$ off so that we just have $XXXX...$. Since $TXXXX...$ must have no consecutive heads, it must also have no consecutive heads without the $T$. Therefore, $XXXX...$ is an element of $E_{n-1}$. Furthermore, if we have some sequence $YYYY...$ in $E_{n-1}$, then by adding a $T$ to it, there's no way we're adding any consecutive heads to the sequence since $T$ does not have any heads to it, so $TYYYY...$ is in $E_n$. Thus, every sequence that starts with $T$ in $E_n$ can be mapped to a unique sequence in $E_{n-1}$ and vice versa, so the number of sequences that start with $T$ in $E_n$ is $\lvert E_{n-1}\rvert$.
Well, now we need to figure out what $E_{n-1}$ is. To do this, let's look at the question how many sequences in $E_n$ start with $H$. Let's say we have some sequence $HXXXX...$ in $E_n$. Then, if the second letter is $H$, then we have consecutive heads, which can't be since sequences in $E_n$ don't have consecutive heads. Thus, the second letter is a $T$, so the sequence is $HTXXX...$. Now, take the $HT$ off and we're left with $XXX...$. This sequence does not have any consecutive heads since the original sequence did not have any consecutive heads, so $XXX...$ is in $E_{n-2}$. Furthermore, let's take a sequence $YYY...$ in $E_{n-2}$. Now, let's add $HT$ to it. There's no way $HTYYY...$ has any consecutive heads because even if the first letter of $YYY...$ is an $H$, then we just get $HTH$ which has no consecutive heads. Thus, $HTYYY...$ is an element of $E_n$. Thus, every sequence that starts with $H$ in $E_n$ can be mapped to a unique sequence in $E_{n-2}$ and vice versa, so the number of sequences that start with $H$ in $E_n$ is $\lvert E_{n-2}\rvert$.
Now, any sequence in $E_n$ either starts with $H$ or $T$. That means any sequence in $E_n$ is either in the group of $\lvert E_{n-1}\rvert$ sequences beginning with $T$ or in the group of $\lvert E_{n-2}\rvert$ sequences beginning with $H$. Since $E_n$ is made up solely of these two groups, the total number of sequences must be $\lvert E_{n-1}\rvert+\lvert E_{n-2}\rvert$, giving us: $$\lvert E_n \rvert=\lvert E_{n-1}\rvert+\lvert E_{n-2}\rvert$$ This is the Fibonacci sequence recurrence. Now, we need to find the initial elements, which is $n=1$ and $n=2$. Both $T$ and $H$ are in $E_1$, so $\lvert E_1\rvert=2$ while $TH$, $TT$, and $HT$ are in $E_2$, so $\lvert E_2\rvert=3$. Thus, this is the Fibonacci sequence shifted over 2 elements (since $F_3=2$ and $F_4=3$), so we find that: $$\lvert E_n\rvert=F_{n+2}$$ Finally, we wanted the number of sequences that start with $T$, which we found to be $\lvert E_{n-1}\rvert$, which is $F_{n+1}$.
This type of combinatorics problem is best approached by trying to build up some recurrence relations among several related values, then solving that recurrence relation. (This type of problem shows up on here frequently - for example, see this problem and also this one)
So let's define:
$e_n$ as you have it - the number of sequences of $n$ coin tosses without consecutive heads
$f_n$ the number of sequences of $n$ coin tosses without consecutive heads that do not begin with $H$
Similarly to what you defined in the problem statement, let $F_n$ be the actual sequences of $n$ coin tosses without consecutive heads that do not begin with $H$. Note that $F_n \subset E_n$.
Note that $f_n$ is what we want, but I defined it the way I did so that we can have $e_0 = f_0 = 1$.
Now, the relation between these series is straightforward: a sequence in $E_n$ is either $T$ followed by one of the elements of $E_{n-1}$, or $H$ followed by one of the elements of $F_{n-1}$.
So:
\begin{align} e_0 &= 1 \\ f_0 &= 1 \\ e_n &= e_{n-1} + f_{n-1} \\ f_n &= e_{n-1} \end{align}
Therefore, if we look at a few values of $e_n$ we get: (starting with $e_0$)
$$ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... $$
So in fact the sequence $e_n$ is the Fibonacci sequence, and $f_n$ - what we wished to find - is just $e_{n-1}$. (Depending on how your book defines where the Fibonacci sequence starts, $f_n$ is exactly the Fibonacci sequence and $e_n$ is the Fibonacci sequence shifted by one)
Note that this implies that as $n \to \infty$, the proportion of $E_n$ that begin with $T$ approaches $(\sqrt{5} - 1)/2 \approx 0.618$
