How to derive Poisson distribution from gamma distribution?

Let $T_1, T_2, \dots$ be iid sequence of exponential random variables with parameter $\lambda$. The sum $S_n = T_1 + T_2 + \dots + T_n$ is a Gamma distribution. Now as I understand the Poisson distribution is defined by $N_t$ as follows:

$$N_t = \max\{k: S_k \le t\}$$

How do I formally show that $N_t$ is a Poisson random variable?

Any suggestions appreciated. I tried to work out a number of proofs but cannot get to the final equation.

References

http://en.wikipedia.org/wiki/Exponential_distribution

http://en.wikipedia.org/wiki/Gamma_distribution

http://en.wikipedia.org/wiki/Poisson_distribution

-
@user862, the proofs I know off-hand aren't particularly direct. Durrett has a derivation in his probability book which is pretty clean. It takes 3-4 pages, I think; which, if you've read any of his books, is a long proof by his standards. Resnick takes a Little bit more abstract approach in his stochastic processes text. Constructing and wielding bigger hammers lets him get more general results, though. Ross undoubtedly has a treatment in his stochastic processes book, but I'm not that familiar with it. –  cardinal May 9 '11 at 11:58
Found the proof in Durrett's book. It is explained really clearly. Thanks for the pointers. –  user862 May 9 '11 at 17:14

I'm sure that Durrett's proof is nice. A straight forward solution to the question asked is as follows.

For $n \geq 1$

$$\begin{array}{rcl} P(N_t = n) & = & \int_0^t P(S_{n+1} > t \mid S_n = s) P(S_n \in ds) \\ & = & \int_0^t P(T_{n+1} > t-s) P(S_n \in ds) \\ & = & \int_0^t e^{-\lambda(t-s)} \frac{\lambda^n s^{n-1} e^{-\lambda s}}{(n-1)!} \mathrm{d} s \\ & = & e^{-\lambda t} \frac{\lambda^n }{(n-1)!} \int_0^t s^{n-1} \mathrm{d} s \\ & = & e^{-\lambda t} \frac{(\lambda t)^n}{n!} \end{array}$$

For $n = 0$ we have $P(N_t = 0) = P(T_1 > t) = e^{-\lambda t}$.

This does not prove that $(N_t)_{t \geq 0}$ is a Poisson process, which is harder, but it does show that the marginal distribution of $N_t$ is Poisson with mean $\lambda t$.

-
(+1) Appealing to conditional densities is not strictly necessary here. Note that $\renewcommand{\Pr}{\mathbb{P}}\Pr(N_t = n) = \Pr(S_n \leq t, S_{n+1} > t) = \Pr(S_n \leq t, S_n + T_{n+1} > t)$ and we need only integrate the joint density over the region $\{(s_n, t_{n+1}): 0 \leq s_n \leq t, t_{n+1} > t - s_n\} \subset \mathbb{R}^2$. Since $S_n$ and $T_{n+1}$ are independent, this is a straightforward undertaking. –  cardinal May 9 '11 at 22:37
@cardinal - and how is @NRH's answer not straight-forward? In fact I would say its easier, because only 1 integration is required. –  probabilityislogic Jul 15 '11 at 0:03
@probabilityislogic: My "straightforward" reference was just a remark about the remaining calculation not shown in my comment. It wasn't meant in any relative sense with respect to @NRH's answer. –  cardinal Jul 16 '11 at 20:50
@probabilityislogic: There is quite a lot of (additional) theory hiding in the first two lines of @NRH's proof. The point of my comment was that we can get the same result by using only the barebones of joint probability distributions, namely just the product measure. This is, in my view, a fundamentally simpler basis for the calculation than introducing conditional expectation and the justification needed for going from line one to two of @NRH's answer. I don't mean that as criticism in any way, my intent was just to provide an alternative method. –  cardinal Jul 16 '11 at 21:49