# Counting: how many ways of climbing a stair?

You are climbing a staircase. At each step, you can either make $1$ step climb, or make $2$ steps climb. Say a staircase of height of $3$. You can climb in $3$ ways $(1-1-1,\ 1-2,\ 2-1)$.

Say a staircase of height of $4$, You can climb in $5$ ways.

Given a staircase of height of $n$, can you figure out how many ways you can climb?

Attempt:

This is actually a programming problem, I have already written the C++ code in recursion, but I just don't know how to verify my program using mathematical skills. I feel this is not a complicate math problem, but yet I couldn't solve it. So I am asking for your help.

• If it's a programming problem, then it belongs on Stackoverflow. – Arthur Jul 16 '16 at 5:28
• @Arthur: Implementing the recursion in some programming language would be a programming problem, indeed. Finding the recursion itself, though, is a very mathematical one, and allows the question to be asked here. – Alex M. Jul 16 '16 at 7:19
• Hint: Let f(n) count the number of ways of climbing n steps. Write down a recurrence relation for f. A journey starts with a single step. – Colonel Panic Jul 16 '16 at 10:55

Sure, that code looks fine. When I run my own version of the code, I get the Fibbonaci sequence— do you?

$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ \cdots$$

This makes sense: suppose $F_n$ represents the number of ways of climbing $n$ steps. If we must climb $n$ steps, we have two choices: we can take 1 step first, then we will have $F_{n-1}$ choices. Or we can take 2 steps first, then we will have $F_{n-2}$ choices. In other words, $F_{n+1} = F_{n} + F_{n-1}$ total choices.

As a special base case, we have that $F_0 = 1$ (the base case in your program), and $F_1 = 1$.

This is a typical example of Fibonacci sequence.

To reach up to, say $N^{th}$ step, you need to get to either $(N-1)^{th}$ or $(N-2)^{th}$ step. It is true for all values of $N$ where $N$ is ${1,2,3...}$.
This is thus a recursion, as is evident from your code:

if (numStairs-BIG>=0) return CountWays(numStairs-SMALL)+CountWays(numStairs-BIG); else return CountWays(numStairs-SMALL);