Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
show 1 more comment

4 Answers

up vote 2 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

$$c=\frac23\cos\left(\frac13\arccos\left(\frac{29}2\right)\right)+\frac13=1.46557123187676\dots\;,$$

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

share|improve this answer
add comment

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

EDIT

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

share|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
2  
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
add comment

Your Answer

 
discard

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.