Question:
There are 8 steps to the top of the stairs. In how many ways can we get to the top if we can climb one step or two steps?
Answer:
Let 1 denotes one step and 2 denotes two steps.
Since, either he can climb one step or two steps only, we have to partition 8 steps as a combination of 1 and 2.
The possible combinations are found by choosing number of 2 steps out of all steps as follows:
1) 1, 1, 1, 1, 1, 1, 1, 1
This can be done in ​\( ^8C_0=1 \)​ ways.
2) 1, 1, 1, 1, 1, 1, 2
This can be done in ​\( ^7C_1=7 \)​ ways.
3) 1, 1, 1, 1, 2, 2
This can be done in ​\( ^6C_2=15 \)​ ways.
4) 1, 1, 2, 2, 2
This can be done in ​\( ^5C_3=10 \)​ ways.
5) 2, 2, 2, 2
This can be done in ​\( ^4C_4=1 \)​ ways.
So, the total number of ways we can get on the top is ​\( 1+7+15+10+1=34 \)​.
