Having a hard time counting this one . A coin is tossed $12$ times . We have to find the number of ways that two heads do not occur consecutively. 
The solution which was provided in the book :
Let $a_n$ denote the number of outcomes in which two consecutive heads do not occur when coin is tossed $n$ times . So $$a_1 = 2 , a_2 = 3 $$
For $n\ge3$ if the last outcome is $T$, then we can't have two consecutive heads in the first $(n-1)$ tosses . This can happen in $a_{n-1}$ ways . If the last outcome is $H$ , we must have $T$ the $(n-1)$th toss and we can't have two consecutive heads in the first $(n-2)$ tosses . This can happen in $a_{n-2}$ ways .
$$a_n = a_{n-1}+a_{n-2} \ \ ,n\ge3$$ 
$$a_{10} = 144 , a_{11} = 233 $$
Therefore $$a_{12}=377$$
I am having two problems here : 
(a) I am not able to understand the reasoning behind this recurrence relation . It would be very helpful , if one can explain this is simple words . 
(b) Can we solve this without using recurrence . By direct methods of counting . 
Thanks in advance . 
 A: Essentially, the recurrence relation is developed by observing the end behavior of the sequence, and in particular, the consequences that the last flip has. 
Suppose your sequence ends in $T$. If this is the case, are there any restriction on the previous $n-1$ flips? Well, the only thing that we are concerned with in this case is that our sequence of $n-1$ flips follows our prescribed rules, i.e. that there two heads do not occur consecutively. Since having a $T$ at the end of our $n$ length sequence does not interfere with this at all, the number of sequences ending in $T$ following our rules is simply $a_{n-1}$, i.e. the number of sequences so that the previous $n-1$ flips don't cause any problems. 
Suppose your sequence ends in $H$. Well, now we have a small problem. In this case, the $n-1$th flip DOES affect things. If our $n-1$th flip is $H$, then the sequence cannot follow our rules, as this would be two heads in a row! In other words, having an $H$ at the end of our $n$ length sequence fixes the $n-1$th flip if the sequence is to obey our rules; in order to avoid having two consecutive $H$ flips, we need to have a $T$ be the $n-1$th flip. From here, we are just in the case we just tackled. If the $n-1$th flip is a $T$, all we need to ensure is that the $n-2$ flips coming before it follow our rules. The number of these sequences is $a_{n-2}$. 
These are the only two possibilities, as a sequence must end in heads or tails. Hence, we have determined $a_{n} = a_{n-1} + a_{n-2}$.  
A: This will be basically a very wordy repetition of your post, with all details explained. 
Call a sequence made up of the letters H and/or T that does not have two consecutive H good.
Let $a_k$ be the number of good sequences of length $k$.
Note that there is $1$ good sequence of length $0$, namely the empty sequence. And there are $2$ good sequences of length $1$, namely H and T. So $a_0=1$ and $a_1=2$.
If the case $k=0$ makes you uncomfortable, we can note that $a_1=2$ and $a_2=3$, by direct counting.
Now for $n\ge 2$ (or for $n\ge 3$ if we start with $a_1$), we will find an expression for $a_n$ in terms of earlier $a_k$.
Consider a good sequence of length $n$. There are two types of good sequences of length $n$, (i) the ones that end with a T and (ii) the ones that end with an H.
Type (i): We can obtain a good sequence of length $n$ that ends in T by appending a T to any good sequence of length $n-1$. Conversely, given any good sequence of length $n$ that ends in T, we get a good sequence of length $n-1$ by lopping off the T. Thus there are exactly as many good sequences of length $n$ that end in T as there are good sequences of length $n-1$. 
The number of Type (i) good sequences of length $n$ is therefore $a_{n-1}$.
Type (ii): We can obtain a good sequence of length $n$ that ends in H by appending an H to any good sequence of length $n-1$ that does not end in H, that is, that ends in T.  Conversely, any good sequence of length $n-1$ that ends in T can be obtained by lopping off the terminal H of a Type (ii) good sequence of length $n$.
Thus there are just as many Type (ii) good sequences of length $n$ as there are good sequences of length $n-1$ that end in T. How many of those are there? If we lop off the T, we get a good sequence of length $n-2$. Conversely, any good sequence of length $n-2$ can be obtained by lopping off the H, and then the T, from a Type (ii) good sequence of length $n$.
Thus the number of good sequences of Type (ii) is $a_{n-2}$.
It follows that the total number of good sequences of length $n$ is $a_{n-1}$ (the Type (i)'s) plus $a_{n-2}$ (the Type (ii)'s). In symbols,
$$a_n=a_{n-1}+a_{n-2}.$$
Remark: The recurrence is an efficient way to compute $a_n$ for modest values of $n$, in particular $12$. There is also a general theory of recurrences of this type, from which we can obtain a closed-form for the Fibonacci numbers $a_n$. This closed form is computationally less useful than the recurrence. 
As to your question about other ways, we can obtain an expression for the $n$-th Fibonacci number $a_n$ as a sum  of binomial coefficients. Nice, in a way, but computationally not very useful. 
A: For (b) (a "direct" method), we can split into cases based on the number of heads. Notice we must have at most 6 heads. If there are 6 heads, there are 6 tails. First consider the tails and note that there are 7 "slots" beside and in between the tails such that we can place the heads in individually. If we do that, we will not have repeating heads. The number of ways to do that will be $\begin{pmatrix} 7 \\ 6\end{pmatrix}$.
Continuing with this approach to 5 heads and so on until the last case of no heads, we will get total number of ways = $\begin{pmatrix} 7 \\ 6\end{pmatrix} + \begin{pmatrix} 8 \\ 5\end{pmatrix} + \begin{pmatrix} 9 \\ 4\end{pmatrix}+\begin{pmatrix} 10 \\ 3\end{pmatrix} +\begin{pmatrix} 11 \\ 2\end{pmatrix}+\begin{pmatrix} 12 \\ 1\end{pmatrix}+1=377$
