1
$\begingroup$

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!

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thanks. But I don't understand why I have to add $\frac{V}{x-1}$ to the decomposition. Doesn't $\frac{W}{(x-1)^2}$ already cover that? $\endgroup$
    – machro
    Commented Dec 14, 2014 at 18:22
  • 1
    $\begingroup$ No it doesn't. If we had $(1-x)^3$ in the denominator, our decomposition would need three distinct fractions with denominators $(1-x), (1-x)^2, (1-x)^3$. $\endgroup$
    – amWhy
    Commented Dec 14, 2014 at 18:27
  • $\begingroup$ Scroll down this page until you see bold-faced "Illustration" which helps explain this procedure, when we have a factor raised to a power. $\endgroup$
    – amWhy
    Commented Dec 14, 2014 at 18:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .