Problem 2.23 Easy Free 3 variations

Climbing Stairs One or Two at a Time

A rabbit stands at the bottom of a staircase with $10$ steps. At each move it hops up either $1$ or $2$ steps. Find the number of distinct sequences of hops that take the rabbit from the ground to the top step.

Work it out, then compare with the answer.

SolutionShow the worked solution

Let $f(n)$ be the number of hop sequences reaching step $n$ , with $f(0)=1$ for the empty sequence. Condition on the last hop. If it is a $1$ , the earlier hops form any sequence reaching step $n-1$ . If it is a $2$ , they form any sequence reaching step $n-2$ . These cases are disjoint and exhaustive, so

f(n)=f(n-1)+f(n-2)\qquad(n\ge 2),\qquad f(0)=f(1)=1 .

Iterating gives $1,1,2,3,5,8,13,21,34,55,89$ for $n=0,\dots,10$ . Hence $f(n)=F_{n+1}$ , where $F_1=F_2=1$ are the Fibonacci numbers, and $f(10)=F_{11}$ .

\boxed{89}

Key idea. Conditioning on the final move turns the count into the Fibonacci recursion.

Variations

The same idea with a twist. Each solution gives only the changed step.

Variation 2.23a

A rabbit stands at the bottom of a staircase with $10$ steps. At each move it hops up some number of steps strictly greater than $1$ (so a single hop of $1$ step is never allowed). Find the number of distinct sequences of hops that take the rabbit from the ground to the top step.

Work it out, then compare with the answer.

Solution

Let $h(n)$ count the hop sequences reaching step $n$ with every hop at least $2$ . Set $h(0)=1$ and $h(1)=0$ . Condition on the last hop.

If it equals $2$ , removing it leaves any valid sequence for step $n-2$ : $h(n-2)$ ways.
If it is at least $3$ , shorten it by $1$ . This gives a bijection with the valid sequences for step $n-1$ , since a last hop of at least $3$ becomes a last hop of at least $2$ : $h(n-1)$ ways.

Hence $h(n)=h(n-1)+h(n-2)$ for $n\ge 2$ . Starting from $h(0)=1$ and $h(1)=0$ , the values are $1,0,1,1,2,3,5,8,13,21,34$ . So $h(n)=F_{n-1}$ and

\boxed{34}

Variation 2.23b

A rabbit stands at the bottom of a staircase with $10$ steps. At each move it hops up an odd number of steps. Find the number of distinct sequences of hops that take the rabbit from the ground to the top step.

Work it out, then compare with the answer.

Solution

Let $o(n)$ count the sequences of odd hops reaching step $n$ . Clearly $o(1)=o(2)=1$ . For $n\ge 3$ , condition on the last hop.

If it is $1$ , the earlier hops reach step $n-1$ : $o(n-1)$ ways.
If it is at least $3$ , shorten it by $2$ . It stays odd and positive, which gives a bijection with the odd-hop sequences for step $n-2$ : $o(n-2)$ ways.

Thus $o(n)=o(n-1)+o(n-2)$ . With $o(1)=o(2)=1$ this is the Fibonacci sequence, so $o(n)=F_n$ and

\boxed{55}

Variation 2.23c

A fair coin is tossed $10$ times. Find the probability that every run of tails in the resulting sequence has length exactly $2$ (so tails only ever occur in consecutive pairs, never alone and never three or more in a row). For instance, with $4$ tosses, $TTHH$ , $TTTT$ , and $HHHH$ satisfy this, while $HTHH$ and $TTTH$ do not.

Work it out, then compare with the answer.

Solution

Interpretation. The example counts $TTTT$ as valid. So the condition means that tails come in consecutive pairs: each run of tails has even length. Equivalently, the sequence is a tiling of the $10$ tosses by blocks $H$ and $TT$ .

Count. Let $t(n)$ be the number of such strings of length $n$ . A valid string ends in $H$ or in $TT$ , and removing that block leaves a valid string of length $n-1$ or $n-2$ . Hence $t(n)=t(n-1)+t(n-2)$ with $t(1)=1$ and $t(2)=2$ . This is exactly the staircase count, so $t(n)=F_{n+1}$ and $t(10)=89$ .

Probability. All $2^{10}$ outcomes are equally likely, so the probability is

\boxed{\dfrac{89}{1024}\approx 0.087}

(If instead every run of tails must have length exactly $2$ , the $TT$ blocks may not be adjacent. Then $a(n)=a(n-1)+a(n-3)$ , giving $41/1024$ .)

Spotted an error? Email us