How many distinct ways to climb stairs in 1 or 2 steps at a time? I came across an interesting puzzle:

You are climbing a stair case. It takes $n$ steps to reach to the top.
  Each time you can either climb $1$ or $2$ steps. In how many distinct
  ways can you climb to the top?

Is there a closed-form solution to the problem? One can compute it by creating a 'tree' of possibilities of each step. That is, I can either take 1 or 2 steps at each stage and terminate a branch once it sums to $n$. But this is would get really unwieldy very quickly since the maximum number of nodes in a binary tree is $2^{n+1}-1$, i.e., exponential. Is there an easier way to solving this puzzle?
 A: Let $F_n$ be the number of ways to climb $n$ stairs taking only $1$ or $2$ steps. We know that $F_1 = 1$ and $F_2 = 2$. Now, consider $F_n$ for $n\ge 3$. The final step will be of size $1$ or $2$, so $F_n$ = $F_{n-1} + F_{n-2}$. This is the Fibonacci recurrence.
A: The solution to this problem indeed corresponds to the Fibonacci numbers, as mentioned by @fahrbach.
Here is an illustration of what you are trying to solve for the case of $n=4$ steps (taken from this website, which also gives a combinatorial solution)

Any staircase with $n$ steps allowing paths with increments of 1 or 2 steps at a time will end up in one of two states before the last path is taken: either we've climbed $(n-1)$ steps already and have $\color{red}{one}$ more step to take, or we've climbed $(n-2)$ steps already and we have $\color{blue}{two}$ more steps to take (if we took only one step here then we'd end up in an arrangement from the first state).

Thus, to get the total number of possible ways to climb $n$ steps, we just add the number of possible ways we can climb $(n-1)$ steps and the number of possible ways we can climb $(n-2)$ steps, giving the familiar recurrence relation:
\begin{equation*}
  F_n = \left\{
    \begin{array}{l@{}l@{}l}
      1 &  n = 0,1\\
       \color{red}{F_{n-1}} + \color{blue}{F_{n-2}} &  n \ge 2
    \end{array}
  \right.
\end{equation*}
A: We can change this question into: In how many ways is possible to write a number as the ordered sum of 1s and 2s?
We can prove this using direct proof.
Hypothesis: For Fibbonaci number $F_1=1, F_2=1, F_{n}=F_{n-1}+F_{n-2}$, $Q(k)=F_{k+1}$
We say that we have constructed every order of $Q(n)$. Then, we construct $Q(n+1)$ this way:


*

*For all orders, we add $+1$ to change $n$ to $n+1$. (There are now $Q(n)$ numbers.) 
Note: all numbers that are constructed here ends in $+1$.

*For all orders that end with $+1$, we change it to $+2$. We shall prove that the amount will be $Q(n-1)$ to complete the proof.
Note: all numbers that are constructed here ends in $+2$.


It can be seen that by constructing in this way there contains all orders.
Proof of step 2: If we constructed $Q(n)$ in the way above, then all numbers ended in $+1$ will be the amount $Q(n-1)$ by step 1. above, and we are done. 
A: This is the Fibonacci numbers - One interpretation of the n-th Fibonacci number is the number of ways to compose $n$ with parts in $\{1,2\}$ (that is, the n-th fibonacci number counts the number of sequences whose values are in $\{1,2\}$ whose sums are $n$). This is often called "Golfs and Cadillacs" or something similar. 
