Number of ways to reach ground floor in $n$ steps

Question

Given an integer $n$ which is the number of steps from first floor to ground floor in a building. We can either move $1$ step down, or $2$ step down, or $3$ step down. However, we may move $3$ steps down at most once. In other words, a $3$ step move can be done any time but only once. We have to find the number of ways to reach the ground floor.

I thought the solution is simply:

$f[n] = f[n-1]+f[n-2]+f[n-3]$

However, I am not getting the right answer. What could be possibly wrong?

Answer 1

Let $f(n,k)$ denote the number of ways you can get to ground floor from the $n$-th step, going three steps at once exactly $k$ times.

Then the recurrence you get is $$f(n,k) = f(n-1,k) + f(n-2,k) + f(n-3,k-1)$$

with appropiate initial values, and the answer you're looking for is $f(10,0) + f(10,1)$.

Answer 2

The problem can be attacked using generating functions (e.g. here).

---

We can take $3$ steps move after the $k$-th step. I.e. split the entire walk into first $k$ steps, one $3$ steps move and $n-k-3$ steps. Then, for the first part, the number of integer solutions of $$x_1+2x_2=k, x_1\geq0,x_2\geq0 \tag{1}$$ is the number of ways to traverse those $k$ steps with $1$ or $2$ steps moves. For the last - the number of integer solutions of $$x_3+2x_4=n-k-3, x_3\geq0,x_4\geq0 \tag{2}$$ is the number of ways to traverse the last $n-k-3$ steps with $1$ or $2$ steps moves.

All these for $k=0$ to $n-3$.

---

Generally, the number of integer solutions for $$x_1+2x_2=k, x_1\geq0,x_2\geq0 \tag{3}$$ is the coefficient of $x^k$ of the generating function $$(1+x+x^2+...)(1+x^2+x^4+...+x^{2n}+...)=\frac{1}{1-x}\cdot \frac{1}{1-x^2}=\\ \frac{1}{2(1-x)^2} + \frac{1}{4(1-x)} + \frac{1}{4(1+x)}=...$$ which is $$...=\frac{1}{2}\left(\sum\limits_{n=0}(n+1)x^n\right)+ \frac{1}{4}\left(\sum\limits_{n=0}x^n\right)+ \frac{1}{4}\left(\sum\limits_{n=0}(-1)^nx^n\right)=\\ \sum\limits_{n=0}\left(\frac{n+1}{2}+\frac{1+(-1)^n}{4}\right)x^n$$ and the coefficient is $$\frac{k+1}{2}+\frac{1+(-1)^k}{4} \tag{4}$$

---

Back to $(1)$ and $(2)$ we have $$\frac{k+1}{2}+\frac{1+(-1)^k}{4} \text{ and } \frac{n-k-3+1}{2}+\frac{1+(-1)^{n-k-3}}{4}$$ or $$\frac{k+1}{2}+\frac{1+(-1)^k}{4}+\frac{n-k-3+1}{2}+\frac{1+(-1)^{n-k-3}}{4}=\\ \frac{n-1}{2}+\frac{2+(-1)^k+(-1)^{n-k-3}}{4}=\\ \frac{n}{2}+\frac{(-1)^k+(-1)^{n-k-3}}{4}$$ and finally $$\sum\limits_{k=0}^{n-3}\left(\frac{n}{2}+\frac{(-1)^k+(-1)^{n-k-3}}{4}\right)=\\ \frac{n(n-2)}{2}+\sum\limits_{k=0}^{n-3}\left(\frac{(-1)^k+(-1)^{n-k-3}}{4}\right)=\\ \frac{n(n-2)}{2}+\frac{1}{2}\left(\sum\limits_{k=0}^{n-3}(-1)^k\right) \tag{5}$$ See if you can simplify it any further.

Answer 3

I would start by computing the number of ways to go down $n$ steps, moving only one or two steps at a time. We have $$\begin{align} a_0,&=1\\ a_1,&=1\\ a_2,&=2\\ a_n&=a_{n-1}+a_{n-2},\,n\geq2 \end{align}$$ so that the $a_n$ are the Fibonacci numbers, $F_n.$

Now let $b_n$ be the number of ways to go down $n$ steps, as described in the problem. We may either not make any $3$-step moves at all, or we may move down $k$ steps, then make a $3$-step move, then move the remaining $n-k-3$ steps. Thus,

$$b_n=F_n+\sum_{k=0}^{n-k-3}F_kF_{n-k-3}$$

I don't know if the sum can be simplified.