3
$\begingroup$

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? (Should be something like $f(k,n)=C_{k+n-1}^{n-1} - A(k,n)$).

1 Answers 1

0

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