# Check proof that, if $a_{1}a_{2}... a_{n}=1$ with $a_i\gt0$ then $(1+a_{1})(1+a_{2})...(1+a_{n})\geq2^{n}$ [duplicate]

Theorem: Suppose there is a sequence of positive real numbers such that $a_{1}a_{2}... a_{n}=1$ then

$$(1+a_{1})(1+a_{2})...(1+a_{n})\geq2^{n}$$

(Prove by induction, do not use geometric mean)

I believe I have a proof, but I am unsure it is correct. Could you help me identify any mistakes or find a more direct approach?

Proof: Let $n=1$ then clearly $a_{1}=1$ and $(1+1)\geq2$

Assume the claim is true for all sequences of length $k<n$. Then from a sequence $a_{1}a_{2}..a_{n}$, let $c=a_{i}a_{j}$ where $a_{i}\geq1$ and $a_{j}\leq1$. We know we can pick these because otherwise the product must be less or than greater one.

Then $c(a_{1}a_{2}...a_{n})= 1$ where $i\neq j$ and $i\neq k$ and by the induction hypothesis:

$$(c+1)(a_{1}+1)(a_{2}+1)...(a_{n}+1)\geq 2^{n-1}$$

And
$$(1+a_{i})(1+a_{j})=a_{i}a_{j}+a_{i}+a_{j}+1$$

We want to show this product is greater than $2(c+1)$.

$$(1-a_{j})\geq (1-a_{j})$$

$$a_{i}(1-a_{j})\geq (1-a_{j})$$ since $a_{i}\geq 1$.

$$a_{i}-a_{i}a_{j}\geq (1-a_{j})$$

$$a_{i} + a_{j} \geq a_{i}a_{j} + 1$$

$$a_{i} + a_{j} + (a_{i}a_{j} + 1) \geq a_{i}a_{j} + 1 + (a_{i}a_{j} + 1)$$

$$(1+a_{i})(1+a_{j}) \geq 2(a_{i}a_{j} + 1) = 2(c+1)$$

Finally:

$$(1+a_{i})(1+a_{j})(a_{1}+1)...(a_{n}+1)\geq 2(c+1)\frac{2^{n-1}}{c+1}=2^{n}$$

Note: This exercise comes from Udi Manber's Intro to Algorithms.

• It looks correct to me. Jul 22 '18 at 5:59
• Please try to concoct informative titles, see the edited title for an example.
– Did
Jul 22 '18 at 8:29
• @rtybase Thank you. that is the same setup, but the book specifically asks for an induction method. The answer is using geometric mean, which the book said not to use. Jul 22 '18 at 15:37
• Contributing to already existing questions with creative answers is obviously better. Follow the links to that question and you'll see more duplicates ... duplicates are polluting this site. Jul 22 '18 at 16:12
• Math is really hard to search, I definitely attempted to find the answer first. I still think this is a unique solution, but I don't want to pollute any sites and I don't think I have any more desire to contribute here. Please delete my question. Jul 22 '18 at 16:16

$$a+b \geq 2\sqrt{ab}$$
$$(1+a_1)(1+a_2)\ldots(1+a_n) \geq 2\sqrt{a_1} \cdot 2\sqrt{a_2} \ldots 2\sqrt{a_n} = 2^n\sqrt{a_1a_2a_3 \ldots a_n} = 2^n$$