Staircase Algorithm 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?**

___________________________________
| 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}$$