Let $P_{n}$ be the probability that with $n$ flips of a fair coin, there are no consecutive heads. Now let $F_{n}$ be a modified version of the Fibonacci sequence such that $F_{0}=1, F_{2}=2, F_{3}=3$, and so on. We know that $$P_{n}=\frac{F_{n}}{2^n}.$$
My goal is to write an expression for $P_{n}$ in terms of $P_{n-1}$ and $P_{n-2}$ for $n \geq 2.$
Let $A$ be the event there are no consecutive heads, $T$ be the event a tail shows, and $H$ be the event a head shows. Then $$ P_{n} = \mathbb{P}(A \mid T)\mathbb{P}(T)+\mathbb{P}(A \mid H)\mathbb{P}(H).$$ I think that this expression can be written as $$\frac{P_{n-1}}{2^n}+\frac{P_{n-2}}{2^n}.$$ The reason I say this is because, given a tail shows up, the probability no consecutive heads occur is simply $\frac{P_{n-1}}{2^n}.$. However, if a head occurs, then the next flip $\textbf{cannot}$ be a head. Therefore the probability becomes $\frac{P_{n-2}}{2^n}.$
I understand similar questions have been posted on this site, but I could not find this exact proof.
Can anyone tell me if I am headed in the right direction and how to continue?
Thanks in advance!
I'd let $U_n$ be the number of sequences of $n$ tosses without consecutive heads, and prove that the number of such sequences ending in a tail is $U_{n-1}$ and the number ending in a head is $U_{n-2}$ (at least for $n\ge2$).