Recurrence relation stuck on partial fraction decomposition

373 Views Asked by At

I am stuck in trying to solve the following recurrence relation: $$S_n = rS_{n-1} + nrB$$ where $r$ and $B$ are constants. To solve this I made the following generating function: $$f(x) = \frac{rBx}{(1-rx)(1-x)^2}$$ But every time I try to use partial fraction decomposition I get stuck. This is how I am doing: $$\frac{rBx}{(1-rx)(1-x)^2} = \frac{V}{1-rx}\frac{W}{x^2-2x+1} = \frac{V(x^2-2x+1) + W(1 - rx)}{(1-rx)(1-x)^2}$$ which gives $Vx^2 - 2Vx + V + W - rWx = rBx$ and for some reason I only can find $W = V = 0$, which obviously is wrong. I am pretty sure the generating function is correct, so I think there is something wrong in the last part.

Thanks for your help!

1

There are 1 best solutions below

3
On BEST ANSWER

Your decomposition is incorrect.

$$\begin{align} \frac{rBx}{(1-rx)(1-x)^2} & = \dfrac {U}{1-rx} + \dfrac V{x-1} + \dfrac W{(x-1)^2}\\ \\ &= \frac{U(x^2-2x+1)+ V(1 - rx)(x-1) + W(1-rx)}{(1-rx)(1-x)^2}\end{align}$$

Now try and solve for $U, V, W$.