A frog from k lilypad either jumps to k+1 or k+2 lilypad. Find the probability that it reaches pad 7 if it is initially at pad 1. Lilypads numbered $1,2,3,\cdots$ lie in a row in a pond. A frog is initially on pad $1$. From any pad $k$, the frog will jump to either pad number $k+1$ or $k+2$ with equal probability of ${1\over 2}$. The probability that the frog visits pad $7$ is ${m\over n}$ where ($m,n$) = $1$, Evaluate $n-m$.
Well I wanted to know as to how to attack this problem. I mean Probability = Number of favorable outcomes / Total Outcomes. What is the total outcomes here ?? What are the favorable outcomes ?? How to count them ??
 A: I might be wrong. It's happened before (once).
$P($ reaches pad $7)$ = $1 - P(6 \to 8 \ | $ reaches pad $6)$
$\color{red}{= 1 - \frac12P(\text{ reaches pad 6 })}$ [because assuming it reaches pad $6,$ it has $\frac12$ chance of landing on $8$.]
$= 1 - \frac12(\ 1 - P(5\to7\ |$ reaches pad $5)\ )$
$\color{red}{ = 1 - \frac12(\ 1 - \frac12 P( \text{reaches pad } 5)\ )}$
$= 1 - \frac12(\ 1 - \frac12(\ 1 - P(4 \to 6|$ reaches pad $4\ )\ )\ )$
$\color{red}{= 1 - \frac12(\ 1 - \frac12(\ 1 - \frac12P(\text{reaches pad 4})\ )\ )}$
$ = ...$
$ \color{red}{= 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12P\left(\text{reaches pad 1}\ \right)\ \right)\ \right)\ \right)\ \right)\ \right)}$
$ = 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12 \times 1\ \right)\ \right)\ \right)\ \right)\ \right) $
$ = \frac{43}{64}$.
Since $(n,m) = (64,43) = 1,\ n - m = 64 - 43 = 21.$
A: We can enumerate the number of pads the frog leaps over to get to pad 7:
Case 1$$1+1+1+1+1+1$$
1 permutation, $p=(\frac{1}{2})^6$
Case 2
$$1+1+1+1+2$$
5 permutations, $p=5\times(\frac{1}{2})^5$
Case 3
$$1+1+2+2$$
6 permutations, $p=6\times(\frac{1}{2})^4$
Case 4
$$2+2+2$$
1 permutations, $p=(\frac{1}{2})^3$
Total $=\frac{43}{64}$
A: It might help to model the process as a Markov Chain (though this isn't necessary).
Let $p_n$ be the probability that the frog hits lilypad $n$. Then $p_n=\frac{1}{2}\left(p_{n-1}+p_{n-2}\right)$, and $p_1=1$, $p_2=\frac{1}{2}$. At this point, you can either pump the recursion for $n=7$, or solve the relation to get $p_n=\frac{2}{3}+\frac{1}{3}\left(-\frac{1}{2}\right)^{n-1}$. Either way, you get $p_7=\frac{43}{64}$.
