# Finding partial fraction decomposition of generating function

i would need some help for the following problem.

Consider the $M/E_r/1$ queue with arrival rate $\lambda$ and mean service time $r/\mu$. Let $P(z)$ be the generating function of the probabilities $p_n$, so

$$P(z)=\sum_{n=0}^{\infty} p_{n}z^{n},|z|\leq 1$$ with normalization equation $$\sum_{n=0}^{\infty} p_n=1$$

We are given that $P(z)=\frac{p_0\mu}{\mu-\lambda(z+\ldots+z^{r-1}+z^{r})}$ (*)

(iii) Show, by partial fraction decomposition of $P(z)$, that the probabilities $p_n$ can be written as $$p_n= \sum_{k=1}^{r} c_k (\frac{1}{z_k})^n, n=0,1,2,...$$ where $z_1,...,z_r$ are the zeroes of the denominator in (*).

This is where i have got so far but still cannot relate how i can get $p_n$ eventually:

$P(z)=\frac{p_0}{1-\frac{\lambda}{\mu}(z+\cdots+z^{r})}$, we let $c_k=\frac{p_0}{1-\frac{\lambda}{\mu}}$ and rewriting $\frac{1}{z+\cdots+z^r}=\frac{1}{(z-z_1)\cdots(z-z_k)}$

we have that \begin{align*} P(z) &=\sum_{k=1}^{r} c_k\frac{1}{(z-z_k)} &=\frac{c_1}{z-z_1}+...+\frac{c_k}{z-z_k}=\frac{1}{(z-z_1)...(z-z_k)} \end{align*}

Hence we get \begin{align*} c_1\prod\limits_{j\neq1}^k(z-z_j)+\cdots+c_k\prod\limits_{j\neq k}^k(z-z_j)=1 \end{align*}

For $z=z_1$, $c_1\prod\limits_{j\neq1}^k(z_1-z_j)=1$ so $c_1=\frac{1}{\prod\limits_{j\neq1}^k(z_1-z_j)}$, iterating n times

For $z=z_k$, $c_k\prod\limits_{j\neq1}^n(z_k-z_j)=1$ so $c_k=\frac{1}{\prod\limits_{j\neq1}^n(z_k-z_j)}$

We use the Ansatz (after arguing that all zeros have multiplicity one) \begin{align*} P(z)&=\sum_{k=1}^r\frac{\alpha_k}{(z-z_k)}\\ &=\sum_{k=1}^r\left(-\frac{\alpha_k}{z_k}\right)\frac{1}{1-\frac{z}{z_k}}\\ &=\sum_{k=1}^r\left(-\frac{\alpha_k}{z_k}\right)\sum_{n=0}^\infty\left(\frac{z}{z_k}\right)^n\\ &=\sum_{n=0}^\infty\sum_{k=1}^r\left(-\frac{\alpha_k}{z_k}\right)\left(\frac{1}{z_k}\right)^nz^n\tag{1} \end{align*} and conclude from (1) since \begin{align*} P(z)=\sum_{n=0}^\infty p_nz^n\qquad\qquad|z|\leq 1 \end{align*} that $p_n$ can be represented as \begin{align*} p_n=\sum_{k=1}^rc_k\left(\frac{1}{z_k}\right)^n\qquad\qquad n\geq 0 \end{align*} with $c_k=-\frac{\alpha_k}{z_k}, 1\leq k\leq r$.