math
posted by jen .
An elf has a staircase with 10 steps to climb. Each step it takes can cover either one stair or two stairs. In how many ways can the elf climb the stairs?

5 Doubles === 1 way
4 Doubles, 2 Singles === e.g. DDSSDD
number of ways = 6!/(2!4!) or C(6,4) = 15
3 Doubles, 4 Singles === C(7,3) = 35
2 Doubles , 6 Singles === C(8,2) = 28
1 Double , 8 Singles === C(9,1) = 9
10 Singles === 1
total = 89 
...what?

i don't understand how its 89 ways!
how about 20 stairs, and N stairs? what would be the equation for that?