10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If it's a programming problem, then it belongs on Stackoverflow. $\endgroup$ – Arthur Jul 16 '16 at 5:28
  • 6
    $\begingroup$ @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. $\endgroup$ – Alex M. Jul 16 '16 at 7:19
  • $\begingroup$ 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. $\endgroup$ – Colonel Panic Jul 16 '16 at 10:55
12
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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);

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.