2005 Alabama ARML TST Problems/Problem 10

From AoPSWiki

Problem

When Jon Stewart walks up stairs he takes one or two steps at a time. His stepping sequence is not necessarily regular. He might step up one step, then two, then two again, then one, then one, and then two in order to climb up a total of 9 steps. In how many ways can Jon walk up a 14 step stairwell?

Solution

Solution 1

He can either take 14 one-steps, or 12 one-steps and 1 two-step, etc., so we have

$\begin{eqnarray*}\frac{14!}{14!}+\frac{13!}{12!\cdot 1!}+\frac{12!}{10!\cdot 2!}+\frac{11!}{8!\cdot 3!}+\frac{10!}{6!\cdot 4!...$

Solution 2

Let $a_n$ represent the number of sequences of steps that can be taken up the stairs. Clearly $a_{1} = 1, a_{2} = 2$ . Any sequence of length $n + 1$ is either composed of a sequence of length $n$ followed by another step or a sequence of length $n-1$ followed by two steps. Thus we have the recursion $a_{n + 1} = a_{n} + a_{n - 1}$ which indeed is the Fibonacci sequence, except with indexes shifted. Matching them, we have $a_n = F_{n + 1}$ , and $a_{14} = F_{15} = \boxed{610}$ .

2005 Alabama ARML TST (Problems)
Preceded by: Problem 9	Followed by: Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Personal tools

Navigation

Search

Toolbox