# How to solve this recurrence relation?

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)$ ?

-
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

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.

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

EDIT

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

-

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

-

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

-
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