Staircase Algorithm

Question

Starting at the base of a staircase consisting of n stairs, each step you make takes you either one or two stairs higher. What is the number of different ways in which you can climb the staircase? Explain how you derived your mathematical expression in words.

Is there a better way to prove/show this?

Answer 1

 ___________________________________
| Stair |   # of ways to get there  |
|-------|---------------------------|
|   1   |                        =1 |
|-------|---------------------------|
|   2   |               1+1 or 2 =2 |
|-------|---------------------------|
|   3   |    1+1+1 or 2+1 or 1+2 =3 |
|-------|---------------------------|
|   4   | 1+1+1+1 or 1+1+2 or 1+2+1 |
|       |       or 2+1+1 or 2+2 = 5 |
|-------|---------------------------|
|   5   |                etc.   = 8 |
|-------|---------------------------|
|   6   |                etc.   = 13|
|-------|---------------------------|
|   7   |                etc.   = 21|
|-----------------------------------|

This is the Fibonacci Sequence so the algorithm would be just that. $$f_n=f_{n-1}+f_{n-2}$$

Answer 2

You already go the right answer yourself. I guess, you still looking for a way to prove that your answer is correct.

Let $f_n$ denote the $n$-th Fibonacci number (i.e., $f_1 = 1$, $f_2 = 2$, $f_3 = 3$, $f_4 = 5$, and so on) and $g_n$ the number of different possibilities to reach the $n$-the step of the staircase. You can show that $g_n = f_n$ by induction on $n$.

Your example already shows that $g_k = f_k$ for all $k \leq 7$. Assume that $g_k = f_k$ for all $k \leq n - 1$. How many possibilites are there to reach the $n$-th step? The final move to reach the $n$-th step must be either from the $(n-1)$-th step or the $(n-2)$-th step. Thus, the total number of possibilities to reach the $n$-th step is \begin{align*} g_n = g_{n-1} + g_{n-2} = f_{n-1} + f_{n-2} = f_n \end{align*} where the second inequality holds due to our induction hypothesis.