Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.