The 20th Step

Clearly there is a $\frac{1}{2}$ probability that she will land on step 1.

And there is a $\frac{3}{4}$ probability that she will land on step 2, since 3 of the 4 possibilities for the first 2 coin flips {11, 21, and 22} result in her landing on the second step.

After that, for each step, $n+2$ , she can get there two ways, from step $n$ or from step $n+1$ , each with the same probability.

Therefore, if $P_n =$ the probability that at some point she will land on the $n$ th step, then:

• $P_1 = \frac{1}{2}$
• $P_2 = \frac{3}{4}$
• $P_{n+2} = \dfrac{P_n + P_{n+1}}{2}$ for $n >2$

So,

$P_{20} = \boxed{0.67}$

Here are the details for obtaining the closed form for $P_n$ given by @Brian Charlesworth.

We learn from @Geoff Pilling's solution that

• $P_1=\frac{1}{2}$

• $P_2=\frac{3}{4}$

• $P_{n+2}=P_{n+1}\times \dfrac{1}{2}+P_{n} \times \dfrac{1}{2}$ for $n \ge 2 \quad$ or $\quad 2P_{n+2}-P_{n+1}-P_{n}=0$

For this linear recurrence formula, let's suppose there is a solution for $P_n$ of the form $x^n$ . We would then have

$2x^{n+2}-x^{n+1}-x^n=0$ , which simplifies to $2x^{2}-x-1=0$ , with solutions $x_1=1$ and $x_2=-\dfrac{1}{2}$

Being the recurrence linear, the general solution takes the form $P_n=a\cdot 1^n+b \cdot \left(-\dfrac{1}{2}\right)^n$ .

Knowing that $P_1=\frac{1}{2}$ and $P_2=\frac{3}{4}$ , the values for the coefficients are $a=\frac{2}{3}$ and $b=\frac{1}{3}$ .

The closed form for the probability of landing at the $n$ th step is therefore $\boxed{P_n=\dfrac{2}{3}+\dfrac{1}{3} \cdot \left(-\dfrac{1}{2}\right)^n}$ , which rapidly converges to a value of $\dfrac{2}{3}$ .

The Jacobsthal Sequence mentioned by @Aaghaz Mahajan arises when we approach the solution through combinatorics. Let's consider all the different ways of landing on the $n$ th step by going up one or two steps at a time:

• $n$ "one's": only one way of doing this with a probability of $p_0=\dfrac{1}{2^n}$

• one "two" and $n-2$ "ones": $\binom{n-1}{1}$ ways, $p_1=\dfrac{1}{2^{n-1}}$ each.

• two "two's"and and $n-4$ "ones": $\binom{n-2}{2}$ ways, $p_2=\dfrac{1}{2^{n-2}}$ each.

$\quad \vdots$

• $k$ "two's"and and $n-2k$ "ones": $\binom{n-k}{k}$ ways, $p_k=\dfrac{1}{2^{n-k}}$ each.

$\quad \vdots$

There are two possible ways this sequence ends:

• $\frac{n-1}{2}$ "two's" and one "one" ( $n$ odd): $\binom{\frac{n-1}{2}}{1}$ ways, $p_{\frac{n-1}{2}}=\dfrac{1}{2^{\frac{n-1}{2}}}$ each.

• $\frac{n}{2}$ "two's" and zero "ones" ( $n$ even): $\binom{\frac{n}{2}}{0}$ ways, $p_{\frac{n}{2}}=\dfrac{1}{2^{\frac{n}{2}}}$ each.

$P_n$ is the sum of all these possible cases and it can be expressed as:

$P_n=\dfrac{1}{2^n} \displaystyle \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} 2^k \binom{n-k}{k}$

The Jacobsthal numbers are the result of the summation for the different values of $n$ :

$J_n=\displaystyle \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}2^k \binom{n-k}{k}=\frac{1}{3}(2^{n+1}-(-1)^{n+1})\quad$ ( $1,3,5,11,21,43,85,171,341,687, \ldots$ )

While the other solutions are more elegant, this can also be done with "brute force". One way to get to the twentieth step is to take zero "two steps" and 20 "one steps". The probability of this is (20 choose 0) (.5^20). You can also take one "two step", with 19 "one steps" (with probability (19 choose 1) (.5^19)). All combinations have probability of the form (20 - k choose k)*(.5^(20-k)). You can use Excel to sum all 11 terms to get the required result.

Let $p_{n}$ be the probability of not stepping on the $n$ th step. Observe that, to skip the $n$ th step, Miss Demeanor must step on the $(n-1)$ st step, and if she does that, there is a 50-50 chance of skipping the $n$ th step.
Thus, the recurrence relationship is $p_n = (1 - p_{n-1})*(1/2) = \frac{1 - p_{n-1}}{2}$ . $p_n$ converges to $\frac{1}{3}$ , and it's easy to see via direct calculation that, rounded to three digits, $p_n = 0.333$ for $n \geq 10$ .
Of course the question asks for the probability of not skipping step 20, and that would be $1-p_{20}$ , i.e. $0.667$ .