Question

Sal climbs stairs by taking either one, two, or three steps at a time. Determine a recursive formula for the number of different ways Sal can climb a flight of n steps. Don't forget to include the initial conditions

Answer 1

wow who knows'
lets try it
1 step, 1 way
2 steps, 2 ways
3 steps, 4 ways (i think)

Answer 2

how about 5 steps?

Answer 3

oh lets try 4

Answer 4

How did you get four ways for three steps? I got 3 one-steps, 1 two-step + 1 one-step, or 1 three-step?

Answer 5

for three steps i though
1 1 1
1 2
2 1
3

Answer 6

maybe this has something to do with partitions, i don't know the answer, just thinking out loud

Answer 7

Oh that's a very good point! I didn't think about switching the pattern.

Answer 8

4 steps
1 1 1 1
1 1 2
1 2 1
2 1 1
1 3
3 1

Answer 9

see what you can do, i will try in a minute, but unless this is some application of specific topic, i think experimentation is the way to go

Answer 10

5 steps
11111
1112
1121
1211
2111
113
131
311

Right?

Answer 11

If we're going with experimentation...

Answer 12

Oh or there's 221 to add to that taking five steps part

Answer 13

And for four stairs, you can also take 2 2, so so far, we have a pattern of
1, 2, 4, 7, 9

Answer 14

i think your five steps is missing something

Answer 15

1 2 2
2 1 2
1 2 2
2 3
3 2

Answer 16

So far I have:
11111
1112
1121
1211
2111
113
131
311
221
122

Answer 17

So 12 for taking five steps?

Answer 18

1 1 1 1 1
1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1
1 1 3
1 3 1
3 1 1
2 3
3 2

Answer 19

oh right i missed a couple also
2 2 1
2 1 2
1 2 2

Answer 20

So now our pattern so far is 1, 2, 4, 7, 12...

Answer 21

lets see what we have so far
1 gives 1
2 gives 2
3 gives 4
4 gives 7
5 gives 13

Answer 22

Can you write out what pattern you got for 5? I only have 12 for some reason...must be forgetting one?

Answer 23

1 1 1 1 1

1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1

1 2 2
2 1 2
2 2 1

1 1 3
1 3 1
3 1 1

3 2
2 3

Answer 24

let's say there are x 3-step-at-a-time, y 2-step-at-time, and z one-step.

Answer 25

yes it is time to cut to the chase, i am sure there is a snappier way to do this

Answer 26

we can permute the 3-step, 2-step, and 1-step into (x+y+z)!/z!y!z!) ways

Answer 27

oh and also we are looking for a recursion , not a direct formula in terms of \(n\) although that might be helpful

Answer 28

oh, yeah. i forgot that part. i was into counting the ways.

Answer 29

Yes...the requirement is that we find a recursive formula for the number of different ways Sal can climb a flight of n steps.

Answer 30

Do we need an initial condition?

Answer 31

in other words, when we add one more step, can we figure out how many more ways we need

Answer 32

So you want to figure out how many ways for six stairs?

Answer 33

maybe it is just \(a_n=2a_{n-1}-1\) wouldn't that be easy ?

Answer 34

i got 13 for 5 steps
lets see if we get 25 for 6 steps

Answer 35

Ha that would be crazy if the definition would be that easy :)

Answer 36

Let's see...for six steps I get:
111111

11112
11121
11211
12111
21111

1122
1221
2211
1212
2121

33

1113
1131
1311
3111

Answer 37

Is this right?

Answer 38

I think that sirm3D had a good idea by assigning the values to one-step, two-step, and three-step

Answer 39

missing
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Answer 40

Oh good catch!
So we're at 22 now

Answer 41

i think this may be a very hard problem without a gimmick
maybe we can see what happens to the list when you add 1

Answer 42

consider n = 6: (111111) = 1, (11112) = 5, (1122) = 6, (1113) = 4, (123) = 6, (222) = 1, (33)=1. Total of 24 possible ways

Answer 43

also missing 2 2 2

Answer 44

i did not. there's (222)

Answer 45

sorry i meant earlier

Answer 46

sirm3d what are your six ways of using 1122?

Answer 47

I got
1122
1221
2211
1212
2121
Which one am I missing?

Answer 48

think of it as \(\dbinom{4}{2}=6\)

Answer 49

missing 2 1 1 2

Answer 50

4!/(2!2!)

Answer 51

so much for my \(2a_{n-1}-1\) theory

Answer 52

Oh yeah..that's a very good point. Well the theory you had, satellite73 was definitely an easier one than I think we're faced with right now :/

Answer 53

maybe one more
n = 7
(1111111) =1
(111112) = 7
(11122) = 10
(1 2 2 2) = 4
(1 1 1 1 3) =5
(2 2 3) = 3
(1 1 2 3) = 8

i have no damned idea

Answer 54

(111112) = 6 only.

Answer 55

I think rather than trying to do this out by brute force, we should look at the pattern and see if a formula can't be found...?

Answer 56

i found it. ^^

Answer 57

\[\large a_1=1,\quad a_2=2, \quad a_3=4\]

Answer 58

Oh good! So those are your conditions..

Answer 59

@rachelk09 @satellite73 \[\large a_n=a_{n-1}+a_{n-2}+a_{n-3}, \quad n=4,5,6,...\]

Answer 60

Let's try using that to see if it works for the six that we did out long hand...looks right to me...

Answer 61

The first one was 1 + 2 + 4, which does equal seven. Atempting the next set now. I think you got it!!

Answer 62

n=1: 1
n=2: (11) = 1, (2) = 1
n=3: (111)=1, (12)=2, (3) = 1
n=4: (1111)=1, (112)=3, (13)=2, (22)=1
n=5: (11111)=1, (1112)=4, (122)=3, (113)=3, (23)=2
n=6: (111111)=1, (11112)=5, (1122)=6, (1113)=4, (123)=6, (222)=1, (33)=1
n=7: (1111111)=1, (111112)=6, (11122)=10, (1222)=4, (11113)=5, (1123)=12, (133)=3, (223)=3

Answer 63

Everything checks out. You did it! Thanks so so much!

Answer 64

YW. ^^