1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Initial conditions for recurrence relation

  1. Nov 16, 2016 #1
    1. The problem statement, all variables and given/known data
    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?

    2. Relevant equations

    3. 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?
  2. jcsd
  3. Nov 16, 2016 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
    Last edited: Nov 16, 2016
  4. Nov 18, 2016 #3


    User Avatar
    Homework Helper
    Gold Member

    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 a3 =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 an 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 a1,a2, a3, a4 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted