The Clown Climbing the Stairs

Let A(n) be the ways that the Clown can climb the n stairs. If he decides to take one step for his first move, there will be A(n-1) ways to climb the rest. If he decides to take two steps for his first move, there will be A(n-2) ways to climb the rest. Thus, A(n)=A(n-1)+A(n-2). This is the formula of the Fibonacci sequence. Hence, A(10)=F(11)=89

Let the total number of steps be $n$ . Let the number of double steps be $x$ and single steps be $y$ .

Then we have $2x+y=10$

When the number of double steps is $x$ , the corresponding value of $y$ will be $n-2x$ .

Thus, the possible number of ways of climbing up will be

${x+n-2x \choose n-2x} = {n-x \choose n-2x}$

Therefore, total number of possible ways will be sum of all the possible ways of climbing up for each each value of x, i.e., :

$= \displaystyle \sum_{x=0}^{p} {n-x \choose n-2x}$

where $p$ is the maximum value of x which is $\lfloor \frac{n}{2} \rfloor$ .

Here we have n=10, hence the number of ways:

$\displaystyle \Rightarrow \displaystyle \sum_{x=0}^{5} {10-x \choose 10-2x}$

$\displaystyle \Rightarrow \boxed{89}$

(sorry about formatting ... line breaks?)

Actually I was working on the 11 stair problem which was presented last week but didn't finish before it disappeared. I was looking for a pattern and saw the Fibonacci at times, but not always. <br> So went for a brute force method. <br> Ended up representing the paths that can be taken as a binary number where 1 represents 1 step, and 0 represents 2 steps. <br> 10 stairs

1111111111 = 1 way to take 10 single steps <br> 111111110 = 9 ways with to take 1 double and 8 single (# <= this with 8 1's ) <br>11111100 = 28 ways to take 2 double and 6 single (# <= this with 6 1's ) <br>1111000 = 35 ways to take 3 double and 4 single (# <= this with 4 1's) <br>110000 = 15 ways to take 4 double and 2 single (# <= this with 2 1's) <br>00000 = 1 way to take 5 double
<br> Total = 89 ways to traverse the stairs <br> I used a routine to count the number of occurrences of the 1 in the binaries in the range that was required to reach the maximum value represented in each grouping on the left. <br> Is there a formula to say how many ways someone can take 2 double and 6 single for example?