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.

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$.