1

Okay, I have the following problem:

Find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one, two, or three stairs at a time?

And I basically have no idea how to do it, so I looked up the solution, which is as follows:

$a_n$ = $a_{n-1}$ + $a_{n-2}$ for n >= 2, with the initial conditions being $a_1$ = 1 and $a_0$ = 1.

The first thing I'm confused about is the fact that one of the initial conditions is $a_0$ = 1. If the only ways to climb the stairs are by climbing one, two, or three stairs at a time, in my mind it seems as there are NO ways (or 0 ways) to climb 0 stairs, which would mean $a_0$ = 0. The second thing is..when I actually try to plug in numbers, for example, n = 3:

$a_3$ = $a_{2}$ + $a_{1}$ = 2 + 1 = 3

So there are three ways to climb 3 stairs if you can only climb 1, 2, or 3 steps at a time...and I guess what i'm confused about is..how do you determine a "way" to climb a stair?

For example, I thought that the ways to climb three stairs would be as follows:

You can take it one step at a time, so 1 step, then another step, then another step, which I'll write as

3(1,1,1).

You can take 1 step and then take 2 steps, so

3(1,2)

You can take 2 steps first and then take 1 step, so

3(2,1)

or you could just take 3 steps

3(3)

It seems as though that would mean there are four ways to climb the stairs? Can somebody clear this confusion up for me?

FrostyStraw
  • 1,045
  • I think "the solution" is incorrect. I agree that $a_3 = 4$, as you reasoned. (But $a_0 = 1$: there's exactly one way to stand in one place.) – aschepler Dec 09 '13 at 00:55
  • Dammit I was looking at the wrong answer choice....this particular question only mentions climbing stairs one or two steps a time – FrostyStraw Dec 09 '13 at 01:00
  • If you really mean $1$, $2$, or $3$ at a time, the recurrence is not correct. It would be (after a while) $a_n=a_{n-1}+a_{n-2}+a_{n-3}$. – André Nicolas Dec 09 '13 at 01:00
  • http://math.stackexchange.com/a/763536 has a good description of how this problem works. – JoshuaJB Apr 06 '15 at 21:50

0 Answers0