3
$\begingroup$

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.

2 Answers 2

5

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

  • 0
    $(k)_i = k(k-1)\ldots (k-i+1)$, i.e. $i$ consecutiv factors, starting with $k$2012-12-29
0

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.

  • 1
    Thanks but I don' think this can be right. What do you get if you plug in $n=3$ for example.2012-12-29