MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How do you solve this recurrence (or multivariate recurrences in general)? Note that $p\in[0,1]$ and $n\in\mathbb{N}$ are given constants, where $np\leq 1$.

$$f:(\mathbb{N}\cup\{0\})\times(\mathbb{N}\cup\{0\})\rightarrow[0,1]$$ Base case: $f(0,b)=(1-np)^b$ $\forall$ $b\geq 0$.

$f(a,b)=f(a-1,b-1)[n-(a-1)]p+f(a,b-1)[1-(n-a)p]$, if $a\leq \min{(n,b)}$.

$f(a,b)=0$, otherwise.

Note: The recursive definition could just be applied for $a\leq b$. The function values for $n< a\leq b$ (if $n < b$) can be set to $0$ afterwards.

I have attempted using a multivariate generating function, but it doesn't yield a good simplification. Also looked into somehow manipulating the formula for multivariate taylor series, but to no avail.

share|cite|improve this question
The constraint $a \leq \min(n,b)$ can be replaced by simply $a \leq b$ (values $f(a,b)$ for $a>n$ can be set to zero later). The reason is that if the first argument of $f(,)$ in the l.h.s. of the recurrent formula is $\leq n$, then so are the first arguments of $f(,)$ in the r.h.s. – Max Alekseyev Nov 29 '12 at 5:05
What is $f(0,b)$ for $b>0$ ? – Max Alekseyev Nov 29 '12 at 5:17
Oops, $f(0,b)$ for $b>0$ is now specified in the question. I suppose I will also modify the constraint to make working with it simpler. You're right, those values can be fixed to $0$ later. – user29495 Nov 29 '12 at 6:36
up vote 4 down vote accepted

I get $$f(a,b) = \frac{ (1-np)^b n!}{(n-a)!} \sum_{j=0}^b \binom{b}{j} \left\{ j \atop a \right\} \left(\frac{p}{1-np}\right)^j,$$ where $\left\{ j \atop a \right\}$ is a Stirling number of the second kind. I tested the formula in Mathematica against your recurrence for different values of $n$ and $p$, and they agree. Unfortunately I'm having trouble pasting the Mathematica input and output that verifies that agreement on this site without it turning into gobbledygook.

To get the formula I used Theorem 6 (which is actually due to Neuwirth) in my paper "On Solutions to a General Combinatorial Recurrence," Journal of Integer Sequences 14 (9): Article 11.9.7, 2011. The paper is about solution techniques for solving certain multivariate recurrences. Your recurrence happens to be in one of the forms for which the techniques work.

There might be a way to simplify the summation involving binomial coefficients and Stirling numbers, but I don't see it right now.

Added: The formula I used is the following.

Theorem. Suppose $R(n,k)$ satisfies the recurrence $$(\alpha(n-1) + \beta k + \gamma)R(n-1),k) + (\beta' + \gamma')R(n-1,k-1) + [n=k=0].$$ Then $$ R(n,k) = \left(\prod_{i=1}^k (\beta' i + \gamma') \right) \sum_{i=0}^n \sum_{j=0}^n \left[ n \atop i \right] \binom{i}{j} \left\{ j \atop k \right\} \alpha^{n-i} \beta^{j-k} \gamma^{i-j}.$$ (Here, $0^0$ is taken to be $1$.)

For the OP's recurrence, we have $\alpha = 0, \beta = p, \gamma = 1-np, \beta' = -p,$ and $\gamma' = (n+1)p$.

share|cite|improve this answer

Read Bender and Orszag (Advanced Mathematical Methods for Scientists and Engineers), and you will be enlightened.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.