Proving the Gamma-Poisson relationship using induction I am asked to show
$$\int_{x}^{\infty}\dfrac{1}{\Gamma(\alpha)}z^{\alpha - 1}e^{-z}\text{ d}z = \sum_{y=0}^{\alpha - 1}\dfrac{x^y e^{-x}}{y!}$$
for $x > 0$, $\alpha = 1, 2, \dots$.
Naturally, I thought to use induction for this. The $\alpha = 1$ case is trivial. Now suppose the above equality holds for $\alpha = k \geq 1$. After some work, I showed that
$$\begin{align}
\int_{x}^{\infty}\dfrac{1}{\Gamma(k+1)}z^{(k+1) - 1}e^{-z}\text{ d}z &= \dfrac{1}{k}\int_{x}^{\infty}\dfrac{1}{\Gamma(k)}z^{(k+1) - 1}e^{-z}\text{ d}z  \tag{1}\\
&= \dfrac{x^ke^{-x}}{k\Gamma(k)}+\dfrac{1}{k}\int_{x}^{\infty}\dfrac{1}{\Gamma(k)}z^{k - 1}e^{-z}\text{ d}z \tag{2}\\
&= \dfrac{x^ke^{-x}}{\Gamma(k+1)}+\dfrac{1}{k}\int_{x}^{\infty}\dfrac{1}{\Gamma(k)}z^{k - 1}e^{-z}\text{ d}z \tag{3}\\
&= \dfrac{x^ke^{-x}}{k!} + \dfrac{1}{k}\sum_{y=0}^{k - 1}\dfrac{x^y e^{-x}}{y!} \tag{4}
\end{align}$$
by the induction hypothesis. Particularly, the $\dfrac{1}{k}$ is annoying - if that weren't there, this would be proven. 
Did I do something wrong? My integration by parts $(2)$ work is:
$$\int_{x}^{\infty}z^{(k+1)-1}e^{-z}\text{ d}z = -\left.[z^{(k+1)-1}e^{-z}]\right|^{\infty}_{x}+\int_{x}^{\infty}z^{k-1}e^{-z}\text{ d}z = x^{k}e^{-x}+\int_{x}^{\infty}z^{k-1}e^{-z}\text{ d}z\text{.}$$
$(1)$ uses $\Gamma(k+1) = k\Gamma(k)$.
 A: Compute the recursion directly:  Define $$\Gamma(\alpha;x) = \int_{z = x}^\infty \frac{z^{\alpha-1} e^{-z}}{\Gamma(\alpha)} \, dz$$ (which is the regularized upper incomplete gamma function).  For integer $\alpha > 1$, integration by parts with the choice
$$u = \frac{z^{\alpha-1}}{\Gamma(\alpha)}, \quad du = \frac{z^{\alpha-2}}{\Gamma(\alpha-1)} \, dz, \\
dv = e^{-z} \, dz, \quad v = -e^{-z},$$ yields
$$\begin{align*} \Gamma(\alpha;x) 
&= \left[-\frac{z^{\alpha-1}e^{-z}}{\Gamma(\alpha)} \right]_{z=x}^\infty + \Gamma(\alpha-1;x) \\
&= \frac{x^{\alpha-1} e^{-x}}{\Gamma(\alpha)} + \Gamma(\alpha-1; x) \\
&= \frac{x^{\alpha-1} e^{-x}}{(\alpha-1)!} + \Gamma(\alpha-1;x).
\end{align*}$$  Then unfolding the recursion and observing $\Gamma(1;x) = e^{-x}$, we get
$$\Gamma(\alpha;x) = \sum_{k=0}^{\alpha-1} e^{-x} \frac{x^k}{k!},$$ as claimed.
A: Intuitive explanation & proof
First I'll try to explain this in words. Suppose you are fishing, and your catches occur randomly, however, with a fixed 'average' rate.  Then the number of fishes you will probably have caught at a certain moment are Poisson distributed (https://en.wikipedia.org/wiki/Poisson_distribution):
Suppose that according to the statistics, you should have caught $\mu$ fishes by now.  Then the chance you caught $k$ fishes by now is:
$$ \displaystyle P(X=k) = \frac{\mu^k e^{-\mu}}{k!}$$
So the sum in your exercise expresses the chance on having caught less than $k$   fishes: 
$$\sum_{x=0}^{k-1}\frac{\mu^x e^{-\mu}}{x!}$$
Well: the chance that you caught less than $k$ fishes, is equivalent to the chance that either now or in the future, there will be a specific moment that you will have caught exactly $k-1$ fishes. 
Why? Because with the given success rate per time, eventually the moment will come that you have hooked fish number $k-1$.
So how can we express this with the Poisson distribution? Well, we keep focused on fish $k-1$, however, we just let our expectation value $\mu$ tend to infinity.
$$ = \int_{\mu}^{\infty} \frac{z^{k-1}e^{-z}}{{(k-1)}!}  \, dz $$
How? By simply waiting till the end of times...
Proof
(from: http://qr.ae/TYDZVK)
Consider the following upper incomplete Gamma function [1],
$$ \Gamma(s, \mu) = \int_{\mu}^{\infty} z^{s - 1} e^{-z}dz $$
Using integration by parts,
$$ \Gamma(s, \mu) = [-z^{s - 1}e^{-z}]_{\mu}^{\infty} - \int_{\mu}^{\infty}(s - 1)z^{s - 2}(-e^{-z})dz $$
This gives,
$$ \Gamma(s, \mu) = (s - 1)\Gamma(s - 1, \mu) + \mu^{s-1}e^{-\mu}$$
Note that this is a recurrence relation. If $s$ is a positive integer (say $k$), then, we can solve the recurrence relation in the following manner,
$$ \Gamma(k, \mu) = (k - 1)\Gamma(k - 1, \mu) + \mu^{k-1}e^{-\mu} \;\;\; \cdots \;\;\; (1)$$
Write the recurrence relation for $k-1$ and multiply by $k-1$ to get,
$$ (k - 1)\Gamma(k - 1, \mu) = (k - 1)(k - 2)\Gamma(k - 2, \mu) + (k - 1)\mu^{k-2}e^{-\mu} \;\;\; \cdots \;\;\; (2) $$
Write the recurrence relation for $k-2$ and multiply by $(k-1)(k-2)$ to get,
$$ (k - 1)(k - 2)\Gamma(k - 2, \mu) = (k - 1)(k - 2)(k - 3)\Gamma(k - 3, \mu) + (k - 1)(k - 2)\mu^{k-3}e^{-\mu} \;\;\; \cdots \;\;\; (3) $$
We can continue so on up to,
$$ (k - 1)!\Gamma(1, \mu) = 0 \times \Gamma(0, \mu) + (k - 1)!\mu^{0}e^{-\mu} \;\;\; \cdots \;\;\; (k) $$
Adding all of the k equations, we get,
$$ \Gamma(k, \mu) = (k - 1)! \sum_{x = 0}^{k - 1} \frac{\mu^{x}e^{-\mu}}{x!}$$
That is,
$$ \Gamma(k, \mu) = \Gamma(k) \sum_{x = 0}^{k - 1} \frac{\mu^{x}e^{-\mu}}{x!}$$
$$ \frac{\Gamma(k, \mu)}{\Gamma(k)} = \sum_{x = 0}^{k - 1} \frac{\mu^{x}e^{-\mu}}{x!} $$
Hence proved.
[1] Incomplete Gamma Function (http://mathworld.wolfram.com/IncompleteGammaFunction.html)
See also: 
Poisson and Erlang distribution: relation between their CDF's (https://goo.gl/i8eo7h)
