Initial conditions for recurrence relation

[Mr Davis 97]

Homework Statement

If $a_n$ counts the number of ways to climb a flight of n stairs if one can take 1, 2, or 3 steps at a time, then $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. What are the three initial conditions?

Homework Equations

The Attempt at a Solution

I would say that $a_0 = 1$ since there is one way to do nothing (and that is to do nothing), $a_1=1$, since there is one way to take one step, and $a_2 = 2$, since I could either take 1 step twice, or take two steps once. However, apparently it is correct that $a_2=3$. Where am I going wrong?

 

[andrewkirk]

More information is needed about what a 'way' is. Is every stride in a trip required to encompass the same number of steps, or can one go 3,1,2,1,3 for instance? If the latter is true then a 'way' is a possibly empty sequence of elements from the set {1,2,3}, that adds to n, with the usual convention that an empty sequence adds to zero. If the former then we add the requirement that all elements in the sequence are equal.

Nevertheless, under either approach , it should be the case that $a_2=2$. Most likely the source contains an error.

 

[epenguin]

Seems to me that:

You cannot include 0 steps - after all you could take that number of steps any number of times*;

I cannot see that a _anything could be 3. Well you could have a₃ =3 if you say that the order of the steps doesn't matter. In that case the problem is identical with finding the number of ways you can get a_n by additions of 1's, 2's and 3's, order not mattering. But if that is the rule, then you don't get your recurrence relation whereas you do if order matters. To see this it suffices to look at a₁,a₂, a₃, a₄ in both cases.

* You just don't need to worry about this being "true" or not at all! Because it is always valid for this kind of problem to take whatever a's are convenient as initial values. I expect you know that this problem has a general solution.