Ravi Pradeep's solution uses a recurrence relation, I am new to recurrence relations but would like to understand this part of the answer.
Expected Number of Coin Tosses to Get Five Consecutive Heads
Having looked into recurrence relations I know that the methodology is to:
- Solve the homogeneous equation
- Solve the particular equation
- Find final equation using the initial conditions
but I am struggling to apply this to the problem at hand.
The recurrence relation is:
$E_n= 2E_{n-1}+2$.
The solution then proceeds as follows:
Define $f(n)=E_n+2$ with $f(0)=2$. So,
Why is $f(n)=E_n+2$ used rather than $f(n)=2E_n+2$?
\begin{align} f(n)&=2f(n-1) \\ \implies f(n)&=2^{n+1} \end{align}
How is the $f(n)=2^{n+1}$ derived?
Therefore, $E_n = 2^{n+1}-2 = 2(2^n-1)$
Where does the minus two come from in the solution above?
For $n=5$, it will give us $2(2^5-1)=62$.