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]$, 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$laterafterwards. 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. 4 added 156 characters in body 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. $$f:(\mathbb{N}\cup\{0\})\times(\mathbb{N}\cup\{0\})\rightarrow[0,1]$$ Base case:$f(0,b)=(1-np)^b\forallb\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 b$.\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$ later.

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.

3 added 17 characters in body

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.

$$f:(\mathbb{N}\cup\{0\})\times(\mathbb{N}\cup\{0\})\rightarrow[0,1]$$ Base case: $f(0,0)=1$.f(0,b)=(1-np)^b\forallb\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)}$.b$.

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

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.

2 edited tags
1