# Proving integration identity

Can you please help me prove this identity below? I have tried integration by parts and I am able to see where the numerator of the RHS comes from; however, I am unable to get the denominator. Additionally, I am unsure of how to use induction to show this, because I know that I would have to use integration by parts $k-1$ times to prove this... thanks for the help!

$$\int_{\alpha w}^\infty \frac{z^{k-1}e^{-z}}{(k-1)!}\mathrm dz=\sum_{x=0}^{k-1} \frac{(\alpha w)^x e^{-\alpha w}}{x!}$$

-
This is essentially an identity for the (upper) incomplete gamma function; indeed you need repeated integration by parts for this. –  Guess who it is. Sep 25 '11 at 5:49
No induction is needed here. Differentiate term by term the sum on the RHS with respect to $\alpha w$. Nearly everything cancels out and the net result is minus the function in the integral, evaluated at $z=\alpha w$. Since the LHS and the RHS go to $0$ when $\alpha w\to+\infty$, the proof is complete. –  Did Sep 25 '11 at 5:56

$$\int_{\alpha w}^\infty \frac{z^{k-1}e^{-z}}{(k-1)!}\mathrm dz=\sum_{x=0}^{k-1} \frac{(\alpha w)^x e^{-\alpha w}}{x!}$$

The right side is the probability that the number of occurrences in a Poisson process before time $w$ is less than $k$ (with an average of $\alpha$ occurrences per unit of time).

The left side is the probability that the waiting time until the $k$th occurrence is more than $w$.

One side looks at the discrete probability distribution of the number of occurrences in a given time interval; the other looks at the continuous probability distribution of the the time until the $k$th occurrence.

But the two events are the same event. So they must have the same probability. Therefore they are equal, quod erat demonstrandum.

Later edit: I find a complaint of cirucularity in the comments. That is mistaken. Find the probability distribution of the number of successes in $n$ independent Bernoulli trials with probability $p$ of success on each trial; take the limit as $n\to\infty$ while $np$ remains fixed at $\lambda$. The limiting probability of $x$ successes is $e^{-\lambda} \lambda^x/x!$. Say this is in unit time; the numbers of successes in non-overlapping time intervals are independent; then the number of successes before time $t$ has expected value $t\lambda$ and the probability of exactly $x$ successes is $e^{-t\lambda}(t\lambda)^x/x!$. Now the probability of fewer than $x$ successes before time $t$ is the sum of $x$ terms given above (but I'm using "$x$" where "$n$" was used). What then is the probability distribution of the waiting time until the $n$th success? The value of the cumulative distribution function at time $t$ is just $1$ minus the sum given above. Differentiate that to get the density. The integral of the density is the integral above.

So there's no circularity.

-
This seems a little circular to me. Depending on how you define the Poisson process to begin with, this identity is essentially a theorem (or lemma) to be proved from the definition. For example, if you start with a definition of the Poisson process as the number of events at time $t$ such that the time between events are iid exponential, then you still need to prove that the counting process has a marginal Poisson distribution. From there, the result does drop out. –  cardinal Sep 25 '11 at 18:23
There's no circularity, as you'll now find explained above. –  Michael Hardy Sep 25 '11 at 19:07
Your edit simply describes the approach that Didier mentions. Perhaps circularity is not quite the right word, but my point was that by the time that you've established the two essential facts about the Poisson process that you've assumed from the outset, you've already (essentially) proven the theorem. :) (By the way, the lack of complete adequacy of the term circular also explains my original hedge through the modifier "a little".) –  cardinal Sep 25 '11 at 21:17
....and of course integrating by parts, plus mathematical induction, will also do it! –  Michael Hardy Sep 26 '11 at 18:40

This one cries out for a generating function. For $|t|<1$, $$\sum_{k=0}^\infty t^k \int_{\alpha w}^\infty \frac{z^{k}}{k!} e^{-z} \ dz = \int_{\alpha w}^\infty \sum_{k=0}^\infty \frac{(tz)^k}{k!} e^{-z} \ dz$$ $$= \int_{\alpha w}^\infty e^{t z - z}\ dz = \frac{e^{(t-1) \alpha w}}{1-t}$$ $$= e^{-\alpha w} \left(\sum_{k=0}^\infty \frac{(\alpha w t)^k}{k!}\right)\left(\sum_{k=0}^\infty t^k\right)$$ $$= \sum_{k=0}^\infty t^k \sum_{j=0}^k \frac{(\alpha w)^j}{j!}$$

-
Sorry but this does not (cry out). –  Did Sep 25 '11 at 7:23
I guess the cries are not audible to everyone. –  Robert Israel Sep 25 '11 at 20:36
My first comment may have been too concise, let me expand on it: usually, introducing generating functions provides a huge simplification of the problem, which I fail to see in the present case. // Unrelated: what happened to the exponential factor in your last step? –  Did Sep 26 '11 at 1:33

Here's one way of proceeding: first, verify that both sides of the purported identity agree for $k=1$. Now, if you carry out integration by parts on the left hand side, you should obtain the recursion relation

$$\beta_{k-1}=\beta_{k-2}+\frac{(\alpha w)^{k-1}e^{-\alpha w}}{(k-1)!}$$

where

$$\beta_{k-1}=\int_{\alpha w}^\infty \frac{z^{k-1}e^{-z}}{(k-1)!}\mathrm dz=\frac{\Gamma(k,\alpha w)}{\Gamma(k)}=Q(k,\alpha w)$$

and $\Gamma(k,u)$ and $Q(k,u)$ are various notations for the (upper) incomplete gamma function.

The trick now is to replace $\beta_{k-1}$ in the recursion relation with the sum on the right hand side, and verify that the recursion still holds. This along with the verified initial condition $k=1$ proves your identity.

As a variation of Didier's strategy in the comments: after letting $\alpha w=0$, to verify the equation

$$\int_0^\infty \frac{z^{k-1}e^{-z}}{(k-1)!}\mathrm dz=e^{0}\left(1+\sum_{x=1}^{k-1} \frac{0^x}{x!}\right)$$

one can demonstrate that the expression on the right does simplify to $1$; showing that

$$(k-1)!=\int_0^\infty z^{k-1}e^{-z}\mathrm dz=\Gamma(k)$$

can be done by verifying that both sides of the equation agree when $k=1$ and establishing the recursion $(k-1)!=(k-1)(k-2)!$ through integration by parts.

Differentiating both sides of the original identity with respect to $u=\alpha w$ yields the relation

$$-\frac{u^{k-1}e^{-u}}{(k-1)!}=e^{-u}\left(\sum_{x=1}^{k-1} \frac{xu^{x-1}}{x!}-\sum_{x=0}^{k-1} \frac{u^x}{x!}\right)$$

I'll leave the simplification to the reader.

-

Another answer, my second one to this question:

Differentiate both sides with respect to $\omega$. On the left you need the chain rule in a trivial way and the fundamental theorem of calculus, and you get only one term. On the right you get $2k-1$ terms (after apply the product rule to all but one of the $k$ terms) and $2k-2$ of them cancel out. The highest-degree term is equal to the expression you get on the right side. That proves they differ by a constant; finding the constant is the remaining task.

-
Interesting solution. I am sure I saw it quite recently, but cannot seem to remember where. –  Did Sep 26 '11 at 1:30