We have to Find a Probability of Getting ${2}$ consecutive Heads in ${N}$ throws Given that $N^{th}$ throw will always be Head.
For Example:- N = 3, Possible Conditions = HHH, HTH, THH, TTH = 4 possible conditions where Head will always comes last.
Favourable conditions = 1st and 3rd because in these conditions, 2 Heads comes consecutively. So answer will be $\frac{2}{4} = \frac{1}{2}$
For N = 2, Possible conditions = HH, TH = 2 Favourable conditions = HH = 1 => Probability = $\frac{1}{2}$.
I have to print answer in ${P*Q^{-1}\ modulo\ 10^{9}+7}$
So, actual answer for ${N = 3}$ is ${500000004}$ and for N = 2 is also ${500000004}$
What i have found is total number of possibel conditions is ${2^{N-1}}$ but i am not able to figure out number of favourable conditions. Please tell how to solve this questions.
We can use complementary counting here.
We know there are $2^{N-1}$ outcomes for the first $N-1$ tosses. In order to not have any consecutive heads, the $N-1$th toss must be $T$. Then we have $N-1$ tosses where our options are $T$ or $HT$ since each head must be followed immediately by a tail.
We think of $T$ is a monomino and $HT$ as a domino and are tiling $N-1$ squares with some combination of monominos and dominos. Notice we are ensuring the $N-1$th toss will be a tails.
Suppose there are $\mathcal{S}_{N-1}$ ways to tile. If the $N-1$th square is covered by a monomino. Then there are $\mathcal{S}_{N-2}$ options for the initial $N-2$ tosses. If $N-1$th and subsequently $N-2$th squares are covered by a domino then there are $\mathcal{S}_{N-3}$ ways to tile. Hence $$S_{N-1} = S_{N-2} + S_{N-3}.$$ Notice this is the recurrence relation for the Fibonacci numbers. Where $1 = F_1 = \mathcal{S}_0$ since there is $1$ way to tile no squares. And $1 = F_2 = \mathcal{S}_1$ since there is $1$ way to tile $1$ square (i.e. with a monomino). Thus, $F_N = \mathcal{S}_{N-1}$. Thus we have $F_N$ outcomes with no consecutive heads.
So the probability of consecutive heads when the $N$th toss is guaranteed heads is $$1 - \frac{F_N}{2^{N-1}} = \frac{2^{N-1}-F_N}{2^{N-1}}.$$
Example: Let $N = 4$. There are a total of $2^{N-1} = 2^3 = 8$ outcomes that end with $H$. They are $$HHHH, HHTH, HTHH, THHH, TTHH, THTH, HTTH, TTTH.$$ Of these $8$ outcomes, the ones with no consecutive heads are $$HTTH, THTH, TTTH.$$ There are $F_4 = 3$ of these so the probability of getting consecutive heads is $$\frac{8 - 3}{8} = \frac{5}{8}$$ as expected (since we wrote out the $5$ options that do).
Notice that the $3$ "bad" outcomes have $HT$ (dominos) and $T$ monominos tiling the first $N-1$ spots.