# How can you solve this recurrence?

How can I solve this recurrence?

$$B_{k}=1+\frac{n-k-1}{n} B_{k+1} + \frac{kx}{n},\qquad x>0$$

This is defined for $1 \leq k \leq n-1$ and $n \geq 2$. When $k=n-1$ then we can see that $B_{n-1} = 1+ \dfrac{(n-1)x}{n}$ so this is effectively the base case.

-

First I would rewrite the recursion using

$C_k = B_{n-1-k}$

s.t. $C_0$ is the base case and we get the recursion

$C_k = 1 + \frac{k}{n}C_{k-1} + \frac{n-k-1}{n}x, \qquad k>0.$

Next one can split $C_k = \frac{D_k}{n^k} + x\frac{E_k}{n^{k+1}}$ into a term with $x$ and a term without $x$, where the denominators $n^k, n^{k+1}$ are for convenience. This gives the recursions

$D_k = kD_{k-1} + n^k, \quad k>0, \quad D_0 = 1$

and

$E_k = k E_{k-1} + (n-k-1)n^k, \quad k>0, \quad E_0=n-1.$

Both recursions can be expanded into simple sums. Thus we get

$$C_k = \frac1{n^k}\sum_{i=0}^k (k)_i n^{k-i} + \frac{x}{n^{k+1}}\sum_0^k \mbox{something similar}$$

where $(k)_i = k(k-1)\ldots (k-i+1)$.

(I hope I got all the indices and exponents right in my quick writing; but the principle should definitely work.)

-
Thanks. What is $(k)_i$? Also, just to check, what do you get for $B_1$? –  user54551 Dec 29 '12 at 6:58
It seems $D_k = e^n \Gamma(k+1, n)$. –  user54551 Dec 29 '12 at 7:17
And $E_k = n^{1+k} - e^n \Gamma(k+1,n)$. –  user54551 Dec 29 '12 at 7:18
$(k)_i = k(k-1)\ldots (k-i+1)$, i.e. $i$ consecutiv factors, starting with $k$ –  coproc Dec 29 '12 at 9:42

Here is a solution computed by Maple

$${\frac { \left( -1 \right) ^{k}{n}^{k} \left( B \left( 0 \right) \Gamma \left( -n+1 \right) -\sum _{{\it m}=0}^{k-1} \left( n+{\it m }\,x \right) {n}^{-{\it m}-1}\Gamma \left( -n+{\it m}+1 \right) \left( -1 \right) ^{{\it m}} \right) }{\Gamma \left(-n+k+1 \right) }},$$

where $\Gamma(s)$ is the Gamma function.

-
Thanks but I don' think this can be right. What do you get if you plug in $n=3$ for example. –  user54551 Dec 29 '12 at 6:57