Simple birth process: prove time to reach state $n+1$ satisfies $ \mathbb P(T_n < t) = (1 - e^{-\lambda t})^n$ Consider the birth process $\{ X(t) : t \geq 0\}$ with state space $S=\{1,2, \dots \}$ and birth intensities $\lambda _i= i \lambda $.
Let $U_i$ be the amount of time that the process spends in state $i$ before it moves to state $i+ 1$.
Let $T_n=U_1+ \dots + U_n$ be the amount of time it takes for the process to reach state $n+1$, starting from state $1$.

Use induction to prove that $\mathbb P (T_n <t)= \left(1-e^{-\lambda t}\right)^n$ for $n\geq 1$.


We use the principle of mathematical induction. We start with our base case: $n=1$.
$$ \mathbb P(T_1 < t) = 1 - \mathbb P(T_1\geq t).$$
This final probability is given by an exponential distribution with parameter $\lambda_1= 1 \cdot \lambda$ according to the definition of a birth process. This is true since the inter-event time is exponentially distributed with rate $\lambda_i$ We see:
$$ \mathbb P(T_1 < t) = 1 - e^{-\lambda t}= \left(1 - e^{-\lambda t}\right)^1.$$
And thus the base case holds. Now suppose for some $k\geq 1$ we have that:
$$\mathbb P (T_k <t)= \left(1-e^{-\lambda t}\right)^k$$
This is our induction hypothesis. We need to make the inductive step and prove that this equality holds for $k+1$.
$$\mathbb P (T_{k+1} <t)=\dots \text{"magic and sorcery"}\dots = (1-e^{-\lambda t})^{k+1}$$

How do I make the inductive step; do I need to condition on something so that our previous case shows up?

EDIT: with the comment from clarinetist we write:
$$\mathbb{P}(T_{k+1} < t) = \mathbb{P}(T_k + U_{k+1} < t) = \int_{0}^{t} \mathbb{P}(T_k < t - u)f_{U_{k+1}}(u)\text{ d}u$$
Using the induction hypothesis this can be written as:
$$\mathbb{P}(T_{k+1} < t) = \mathbb{P}(T_k + U_{k+1} < t) = \int_{0}^{t} (1-e^{- \lambda(t-u)})^{k} \lambda_{k+1} e^{\lambda_{k+1}u} \text{ d}u$$
But this does not make things better I think.
 A: You are halfway there with the hint.
Since we know $\lambda_k=k\lambda$ (this is given in the question), we can solve the integral explicitly, and since this is a simple birth process, we know $f_{U_{k+1}}(u)=\lambda_k e^{-\lambda_k u}=k\lambda e^{-k\lambda u}$
\begin{align}
\mathbb{P}(T_{k+1}<t)&=\mathbb{P}(T_k+U_{k+1}<t)=\int_0^t \mathbb{P}(T_k<t-u)(k+1)\lambda e^{-(k+1)\lambda u}du \\
&=\int_0^t (k+1)\lambda e^{-(k+1)\lambda u}(1-e^{-\lambda (t-u)})^k du \\
&=\left[-e^{-(k+1)\lambda u}(1-e^{-\lambda (t-u)})^k\right]_0^t -\int_0^t (-e^{-(k+1)\lambda u})\times k(1-e^{-\lambda (t-u)})^{k-1}(-\lambda e^{-\lambda (t-u)})du \\
\end{align}
by integration by parts, so
\begin{align}
\mathbb{P}(T_{k+1}<t)&=(1-e^{-\lambda t})^{k}-e^{-\lambda t}\int_0^tk\lambda (1-e^{-\lambda (t-u)})^{k-1} e^{-k\lambda u} du \\
&=(1-e^{-\lambda t})^{k}-e^{-\lambda t}\int_0^t \mathbb{P}(T_{k-1}<t-u)k\lambda e^{-k\lambda u} du
\end{align}
and we recognise this integral as the integral from the first line but with $k$ rather than $k+1$; that is
\begin{align}
\mathbb{P}(T_{k+1}<t)&=(1-e^{-\lambda t})^{k}-e^{-\lambda t}\int_0^t \mathbb{P}(T_{k-1}<t-u)k\lambda e^{-k\lambda u} du \\
&=(1-e^{-\lambda t})^{k}-e^{-\lambda t}\mathbb{P}(T_{k}<t) \\
&=(1-e^{-\lambda t})^{k}-e^{-\lambda t}(1-e^{-\lambda t})^k \\
&=(1-e^{-\lambda t})(1-e^{-\lambda t})^k = (1-e^{-\lambda t})^{k+1} 
\end{align}
as required. In general, seeing a problem like this in which we can conition on times (ie. write the probability in terms of integrals) and where we have to use induction, my mind immediately goes to using integration by parts on the integral to reduce '$k$' or whatever variable we're doing induction by.
