1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ It looks correct to me. $\endgroup$ Jul 22 '18 at 5:59
  • $\begingroup$ Please try to concoct informative titles, see the edited title for an example. $\endgroup$
    – Did
    Jul 22 '18 at 8:29
  • $\begingroup$ @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. $\endgroup$ Jul 22 '18 at 15:37
  • 1
    $\begingroup$ 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. $\endgroup$
    – rtybase
    Jul 22 '18 at 16:12
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 22 '18 at 16:16
5
$\begingroup$

$$ 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 $$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.