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)$ ?
On
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.
On
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}. $$
On
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. $$
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.