Suppose Jim climbs stairs in a parking garage for exercise H

Suppose Jim climbs stairs in a parking garage for exercise. He will sometimes take two steps at a time. Let c_n be the number of ways that Jim can climb n steps.

a) Give a recurrence relation for c_n. Be sure to include the initial conditions.

b) Use this recurrence relation to calculate in how many ways Jim can climb a flight of 12 steps.

I know the recurrence relation would be Cn = Cn -1 + Cn - 2. I have seen for example that step 6 would be c(6) = 13 and step 7 would be c(7) = 21. How did step c(6) = 13 and step 7 c(7) = 21? Could you show it in an equation on how it was derived? Thanks

Solution

Before Jim coud reach n number of steps he either attained (n-1) or (n-2) steps.
(a)
If he attained (n-1) steps then he has only one way to attain the n steps, by stepping one up. So he has here
1*C(n-1) ways.

If he attained (n-2) steps then here he has two ways to get to n steps: one big step or two small ones. But the two small ones first leads to the (n-1) steps which we counted already. So we need only to count the one big step case. Thus there are 1*C(n-2)

Thus in all, Cn = C(n-1) + C(n-2).

(b)
It is clear that he can only attain step 0 in c(0)=1 way and step 1 in c(1)=1 way.
This is called the Fibonacci Series:

000, 001, 002, 003, 004, 005, 006, 007, 008, 009 , 010 , 011, 012 ------- n      <--- there are the number of steps of the ladder

001, 001, 002, 003, 005, 008, 013, 021, 034, 055, 089, 144 233 -------- c(n)

=> C(12) = 233 ways

in fibonacci series we add the first 2 numbers to get the next term

like 1 ,1 ,

third term = 1+1 = 2

fourth term =second term + third term = 1+2 =3

fifth term = 2+3=5

sixth term = 3+5 = 8

seventh term = 5 + 8 =13

eigth term = 8+13 = 21