Number of ways to reach ground floor in $n$ steps 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?
 A: 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)$.
A: 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.
A: 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. 
