Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There's a frog who could climb either 1 stair or 3 stairs in one shot. In how many ways he could reach at 100th stair?

I came up with the solution $g(n) = g(n-3) + g(n-1)$, where $g(0)=g(1)=g(2)=1$ and $g(3)=2$. But to solve $g(100)$ is quite difficult if I use substitution method so I just want to know if there is a feasible method to solve for $g(100)$ ?

share|cite|improve this question
Small error in your initial conditions: $g(0)=1$. – Brian M. Scott Apr 8 '13 at 3:12
In the case of g(0) the frog remains at its original position only and so it should not contribute to the no. of ways to reach nth floor where n>3. – Maverick Snyder Apr 8 '13 at 3:24
But there is $1$ way for the frog to reach the original position, not $0$. Moreover, you want $g(3)=g(2)+g(0)$, and for that you need $g(0)=1$. – Brian M. Scott Apr 8 '13 at 3:25
No, I am not. I am counting the number of ways of reaching the $n$-th position. There is $1$ way to reach the starting position: do nothing. This is the standard approach to such problems. – Brian M. Scott Apr 8 '13 at 3:35
Yes my mistake you are right. – Maverick Snyder Apr 8 '13 at 3:36
up vote 3 down vote accepted

This is OEIS A000930, sometimes known as Narayana’s cows sequence. The link does give a closed form:

$$g(n)=\left\lfloor dc^n+\frac12\right\rfloor\;,$$

where $c$ is the real root of $x^3-x^2-1$, and $d$ is the real root of $31x^3-31x^2+9x-1$. It also says that $d=0.611491991950812\dots$ and


but you’ll need moderately high-precision arithmetic to get an exact value for $g(100)$ from that.

share|cite|improve this answer
Just a little something about Narayana's constant $c$. We have $$e^{\pi\sqrt{31}} \approx 2^{12}c^{24}-24.0000069\dots$$ It's not coincidence but has to do with a certain Dedekind eta quotient. :) – Tito Piezas III Feb 12 at 5:54

Essentially, you need to find the number of natural number pairs $(a,b)$ such that $$a+3b = 100$$ More importantly, you need to take into account the order in which $1$'s and $3$'s appear. For instance, $a=1, b=33$ is a solution to the above. And we can choose $1$ one step and $33$ three steps in $34$ ways. If the solution is $(100-3b,b)$, the number of ways we can have $100-3b$ one steps and $b$ three steps is $$\dfrac{(100-2b)!}{b! (100-3b)!}$$ Hence, the total number of ways is $$\sum_{b=0}^{33} \dfrac{(100-2b)!}{b! (100-3b)!}$$ In general, $$g(n) = \sum_{n=0}^{\lfloor n/3 \rfloor} \dfrac{(n-2b)!}{b! (n-3b)!}$$ From this, we get $g(100) = 24382819596721629$.


This also agrees with OEIS A000930, Narayana’s cows sequence.

share|cite|improve this answer

As a possibly computationally more efficient way of getting the answer I proffer the following (only requires integer arithmetic, and AFAICT at least asymptotically less operations than Marvis' sum of binomial coefficients). We can turn the recurrence formula into a matrix equation. Define the vector $\vec{g}(n)=(g(n),g(n+1),g(n+2))$. Then $\vec{g}(n+1)=\vec{g}(n)A$, where $A$ is the $3\times3$ matrix $$ A=\left(\begin{array}{ccc}0&0&1\\1&0&0\\0&1&1\end{array}\right). $$ An obvious induction shows that $\vec{g}(n)=A^n\vec{g}(0)$. You already calculated that $\vec{g}(0)=(1,1,1)$, so `all' we need to do is to compute $A^{100}$ (actually $A^{98}$ would suffice, but that doesn'r really matter this time). There you should use the ever useful square-and-multiply-algorithm: Repeated squaring gives you $A^2$, $A^4=(A^2)^2$, $A^8$, $\ldots$, $A^{64}$ after six matrix multiplications. Three more matrix multiplications (a total of nine) then gives you $$ A^{100}=A^{64+32+4}=A^{64}\cdot A^{32}\cdot A^4. $$

share|cite|improve this answer

The ordinary generating function for the sequence $g(n)$ is $$ G(x) = \sum_{n=0}^\infty g(n)\,x^n = 1 + x + x^2 + 2x^3 + \cdots $$

The relation $g(n) = g(n - 1) + g(n - 3)$ leads to the equation $$ G(x) - 1 - x - x^2 = x \big( G(x) - 1 - x \big) + x^3 G(x), $$ which simplifies to $$ G(x) = \frac{1}{1 - x - x^3}. $$ Using technology to expand the series to find the $100$th term, $$ g(100) = \frac{G^{(100)}(0)}{100!} = 24\,382\,819\,596\,721\,629 \approx 2.4 \times 10^{16}. $$

share|cite|improve this answer
I find that waving my hands vigorously is much more fun than "using technology". Besides, taking that 100th derivative seems to me to be much more work than just evaluating the recurrence. – marty cohen Apr 8 '13 at 4:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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