# An interesting partial recurrence equation

What is the closed form solution to the following partial recurrence relation? $$f(k,n) = \sum\limits_{t=0}^{m}f(k-t, n-1),$$ where $m \geq 0$ is some fixed parameter.

The boundary values are $f(k,n)=0$ for all $k < 0, n < 1$ except $f(0,0)=1$.

I noticed that for $m \geq k$ its closed form is a binomial coefficient $f(k,n)=C_{k+n-1}^{n-1}$, $k \geq 0$, $n > 0$. Do you have any idea how to solve this equation for $m<k$? (Should be something like $f(k,n)=C_{k+n-1}^{n-1} - A(k,n)$).

-

If $m < k$ and $k > 0$, then your sum is adding zeroes together, since by applying your recurrence rule once on each term of the sum, you hit on negative parameters, for which the value of $f$ is zero.
So for $m < k$ :
• $k > 0 \implies f(k,n) = 0$
• $k = 0 \implies m < 0$ so your recurrence is undefined (or equal to $0$)