Probability of consecutive heads We want to compute the probability of the following event :
"Getting two consecutive heads in 25 coin tosses".
What I did is the following : There are $2^{25}$ possible outcomes for the coin tosses that can be written as sequences $(a_1,\cdots,a_{25})$ with $a_i \in \{H,T\}$. The sequences that satisfy our events are the ones like $(H,H,...)$ with $2^{23}$ possibilities for the "...". We do this 24 times for forms like $(\cdots,H,H,\cdots)$. That gives us a probability of $\frac{24\cdot2^{23}}{2^{25}}=6$. I realized this is false because I counted some sequences twice or more.
How can I do it properly (would like to avoid using inclusion-exclusion principle) ?
 A: For a different approach:
Let's compute the number of toss sequences with no $HH$.  Let $a_n$ be the number of such sequences of length $n$.  Clearly $a_1=2,a_2=3$.
Now, any such sequence of length $≥2$ must end in one of $T$ or $TH$.  Hence $$a_n=a_{n-1}+a_{n-2}$$ for $n≥3$
It follows that the $a_n$ are the Fibonacci numbers,  and that $a_{20}$ is $17711$.
Note:  the $a_n$ have a different indexing than the usual Fibonacci numbers.  Indeed, $a_n=F_{n+1}$.
Thus the number of sequences of length $20$ which do contain an $HH$ is $$2^{20}-17711=1030865$$
Since all sequences have the same probability (namely $\frac 1{2^{20}}$) the answer is $$\frac {1030865}{2^{20}}\approx  .983$$
Note:  on review I see the problem asked about $25$, not $20$.  Of course the same procedure works and we get $$\frac {2^{25}-a_{25}}{2^{25}}\approx .994$$
A: This is an example where it's easier to work out the probability that the event doesn't happen.
Hint: if you don't get two heads in a row, that means every head is followed by a tail.
A: My idea would be to consider two series of numbers :
$R^T_n$ : the numbers of the n first draws that have no consecutive heads and are terminated by a tail
$R^H_n$ : the number of the n first draws that have no consecutive heads and are terminated by a head
you have $R^T_1= R^H_1 = 1$
Then the recursive equations :
$$
\left\{
    \begin{array}{l}
        R^T_{n+1}= R^H_n + R^T_n \\
        R^H_{n+1}= R^T_n
    \end{array}
\right.
$$
This is closely related to the recursive sequence of the Fibonacci sequence $F_n$. Actually, $R^T_n=F_{n+1}$ and $R^H_n=F_n$
We can use the closed-form of $F_n=\frac{(\frac{1+\sqrt{5}}{2})^{n+1}+(\frac{1-\sqrt{5}}{2})^{n+1}}{\sqrt5}$ but you can find tables on the Internet.
So $P = 1- \frac{F_{25}+F_{26}}{2^{25}} = 1- \frac{196418}{3355432}\sim 1-0.005853713$
A: Suppose we want to find the number of strings of length $25$ containing e.g. $3$ times character $H$ and $22$ times character $T$ and not containing $HH$ as substring.
We can start with a string $HTHTH$ in the understanding that then character $T$ must be added $20$ times.
This boils down to writing $20$ as a sum of $4$ nonnegative integers an applying stars and bars we find $\binom{23}3$ possibilities.
Above we did it for $n=3$ characters $H$ and $25-n=22$ characters $T$ but of course we can do that for every integer $n\in\{0,1,2,\dots,13\}$ finding $\binom{26-n}n$ possibilities.
This proves that the probability of getting no consecutive heads by $25$ coin tosses equals:
$$2^{-25}\sum_{n=0}^{13}\binom{26-n}n$$Then the probability of getting at least $2$ consecutive heads equals:$$1-2^{-25}\sum_{n=0}^{13}\binom{26-n}n$$
I vaguely suspect the summation also equals the $14$-th Fibonaccinumber so that we can write the probability as:$$1-2^{-25}F_{14}$$but now it's time to go to bed. Tomorrow I will have a second look.

Edit
Unfortunately I made a counting mistake (@#&*). The summation does not equal $F_{14}$ but $F_{26}=196418$.
The probability is:$$1-2^{-25}F_{26}=1-\frac{196418}{33554432}=\frac{33358014}{33554432}\approx0.994146$$
This answer agrees with the nice answer of @lulu.
For completeness: in my answer the Fibonacci numbers start with: $F_0=F_1=1$.
