# Proof of inequality with induction

I have to show that $\prod_{k=1}^n(1+a_k) \geq 1 + \sum_{k=1}^n a_k$ is valid for all $1 \leq k \leq n$ using the fact that $a_k \geq 0$.

Showing that it works for $n=0$ was easy enough. Then I tried $n+1$ and get to: \begin{align*} \prod_{k=1}^{n+1}(1+a_k) &= \prod_{k=1}^{n}(1+a_k)(1+a_{n+1}) \\ &\geq (1+\sum_{k=1}^n a_k)(1+a_{n+1}) \\ &= 1+\sum_{k=1}^{n+1} a_k + a_{n+1}\sum_{k=1}^n a_k \end{align*}

In order to finish it, I need to get rid of the $+ a_{n+1}\sum_{k=1}^n a_k$ term. How do I accomplish that? It seems that this superfluous sum is always positive, making this not really trivial, i. e. saying that it is even less if one omits that term and therefore still (or even more so) satisfies the $\geq$ …

-
Typo, in one line you have $1+a_{n+1}$ (correct) and in the next $1-a_{n+1}$ (wrong). –  André Nicolas Oct 21 '11 at 18:17
Sorry, I have two problems, the second one has $(1-a_k)$ and and $1-\sum$. In the second, $0 \leq a_k \leq 1$ is an even stricter boundary. –  queueoverflow Oct 21 '11 at 18:52

We want to prove that the equation $$\prod_{k=1}^n(1+a_k) \geq 1 + \sum_{k=1}^n a_k$$ is true for all $n\geq0$ and any $a_i\geq0$. You've already dealt with the base case of $n=0$. Now, the inductive step in the proof involves assuming that the statement is true for a specific value of $n$, let's say $n=m$: $$\prod_{k=1}^m(1+a_k) \geq 1 + \sum_{k=1}^m a_k$$ and demonstrating that it must then be true for $n=m+1$. This is done as follows: $$\prod_{k=1}^{m+1}(1+a_k)= (1+a_{m+1})\prod_{k=1}^{m}(1+a_k)\geq(1+a_{m+1})\left(1 + \sum_{k=1}^m a_k\right)=$$ $$1+a_{m+1}+\sum_{k=1}^m a_k+a_{m+1}\sum_{k=1}^m a_k=1+\sum_{k=1}^{m+1}a_k+(\text{something that's bigger than 0})\geq 1+\sum_{k=1}^{m+1}a_k$$

-

Typo! You have

$$= \prod_{k=1}^{n}(1+a_k)(1+a_{n+1}) ,$$

followed by

$$\geq (1-\sum_{k=1}^n a_k)(1-a_{n+1}) .$$

The minus signs in the last line should be replaced by plus signs, then everything works out fine.

-