Showing a queueing system is a Markov Chain I generally understand how to do this but I'm having trouble with a formal proof.
"Consider an $M/M/1/m+1$ queue with exponential arrivals rate $\lambda$, exponential service rate $\mu$, and finite waiting room capacity $m$. 
Let $X_{n}$ be the number of customers in the system just after the $n$th departure. Show that $\{X_n; \: n \geq 0\}$ is a Markov Chain with state space $E = \{0,...,m\}$ and derive it's transition matrix $P$.
I understand the definition of a Markov Chain says that $$P\{X_n = x_{n} | X_{n-1} = x_{n-1}, .... X_{0} = x_{0}\} = P\{X_{n} = x_{n} | X_{n-1} = x_{n-1}\}$$ or that given the present, the future is independent of the past. 
How can that be shown for this particular queue though? As far as showing the state space $E = \{0,...,m\}$ I can reason it out that there are only $m$ states that this chain can be in since there are only $m$ spots in the waiting room and therefore anyone else must leave, but again not sure how to formally prove it. 
My thoughts are that since this is a birth-death process, the system can only increase by one, decrease by one, or remain the same. And the transition matrix would have rows with 
$\mu_{i} - (\lambda_{i}+\mu_{i})  \lambda_i$ (besides the first and last rows)
Is this the correct way to proceed, or is this a different scenario since we are considering the number of customers in the system "just after the $n$th departure."
 A: Given the state space $E=\{0,\ldots,m\}$ we need to find the transition probabilities and prove the Markov property.
For any state $i\geq 1$, consider how we can get to any other state $j$ in one step. If $j <= i-2$ then it's obviously impossible because with the first departure the step is complete.
Next, if $j=i-1$ then transition occurs if the next system event is a departure. And generally, for $i-1\leq j\leq m-1$, transition to $j$ occurs if the next $j-i+1$ events are arrivals followed by a departure, and this occurs with probability $\;\left(\dfrac{\lambda}{\lambda+\mu}\right)^{j-i+1}\dfrac{\mu}{\lambda+\mu}$.
If $j=m$, transition occurs if the next $m-i+1$ events are arrivals. Any further arrivals before the next departure are ignored (the waiting room is full). Thus, the probability of this transition is $\;\left(\dfrac{\lambda}{\lambda+\mu}\right)^{m-i+1}$.
For state $i=0$, the first system event can only be an arrival, giving us the same situation as when $i=1$. So the transition probabilities for $i=0$ are the same as for $i=1$.
For the Markov property, there is almost nothing to prove. The above transition probabilities depend only on the current state $i$ and not any previous state because of the assumed independence of the customer arrival and departure waiting times.
The transition probability matrix is, letting $\gamma = \lambda+\mu$:
$$
    P=  \begin{bmatrix}
        \dfrac{\mu}{\gamma} & \dfrac{\lambda\mu}{\gamma^2} & \dfrac{\lambda^2\mu}{\gamma^3} & \dfrac{\lambda^3\mu}{\gamma^4} & \cdots & \dfrac{\lambda^{m}}{\gamma^{m}} \\
        \dfrac{\mu}{\gamma} & \dfrac{\lambda\mu}{\gamma^2} & \dfrac{\lambda^2\mu}{\gamma^3} & \dfrac{\lambda^3\mu}{\gamma^4} & \cdots & \dfrac{\lambda^{m}}{\gamma^{m}} \\
        0 & \dfrac{\mu}{\gamma} & \dfrac{\lambda\mu}{\gamma^2} & \dfrac{\lambda^2\mu}{\gamma^3} & \cdots & \dfrac{\lambda^{m-1}}{\gamma^{m-1}} \\
        0 & 0 & \dfrac{\mu}{\gamma} & \dfrac{\lambda\mu}{\gamma^2} & \cdots & \dfrac{\lambda^{m-2}}{\gamma^{m-2}} \\
        & \cdots \\
        0 & 0 & \cdots & 0 & \dfrac{\mu}{\gamma} & \dfrac{\lambda}{\gamma} \\
        \end{bmatrix}
$$
