# How to prove by induction the following :

How to prove using induction the following is true : Let $X_1, X_2,\ldots,X_n$ be i.i.d r.v. that are distributed exponentially with $\lambda$. Then $\forall n \ge 3$ $$\Pr(X_1 > \sum_{k=2}^n X_k) = \frac 1 {2^{n-1}}$$

I was able to show the basis step, where $n=3$ $$\Pr(X_1 > X_2+X_3) = \int_0^\infty \Pr(X_1 > x + y) f(x) f(y) \, dx\, dy = \int_0^\infty e^{-\lambda (x+y)} \frac 1 \lambda e^{-\lambda x} e^{-\lambda y} \,dx\, dy = \left.- \frac 1 2 e^{-2\lambda x}\right]_0^\infty \cdot \left.\frac {- 1} 2 e^{-2\lambda x}\right]_0^\infty = \frac 1 {2^{3-1}}$$

Now am I supposed to go about solving for the inductive step, it says in the question to use the memoryless property when proving for this.

Use the fact that for exponential random variables $X$, $$\Pr[X>s+t|X>s] = \Pr[X>t].$$ Using this, we get $$\Pr[X_1>X_2+\cdots+X_n] = \\ \Pr[X_1>X_2+\cdots+X_n|X_1>X_2+\cdots+x_{n-1}] \Pr[X_1>X_2+\cdots+X_{n-1}] = \\ \Pr[X_1 > X_n] \Pr[X_1>X_2+\cdots+X_{n-1}].$$ Now you can use induction. What we use here is that if $X_1>X_2+\cdots+X_n$ then also $X_1>X_2+\cdots+X_{n-1}$, since $X_n \geq 0$.
Even without (formally) using induction, in this way you easily get $$\Pr[X_1>X_2+\cdots+X_n] = \Pr[X_1>X_2] \cdots \Pr[X_1>X_n] = \frac{1}{2^{n-1}},$$ due to symmetry and the fact that exponential random variables have no atoms (so $\Pr[X_1 = X_2] = 0$).