Thread: Proof by induction stuck at very end!!

1. Proof by induction stuck at very end!!

Show that $\sqrt{a_1^2 + b_1^2} + \sqrt{a_2^2 + b_2^2} + ... + \sqrt{a_n^2 + b_n^2} \ge \sqrt{(a_1+a_2+...+a_n)^2 + (b_1+b_2+...+b_n)^2}$ for all real values of the variables. Furthermore, give a condition for equality to hold.

Base case:

Let $n = 2$

$\sqrt{a_1^2+b_1^2} + \sqrt{a_2^2+b_2^2} \ge \sqrt{(a_1+a_2)^2+(b_1+b_2)^2}$

$(a_1^2+b_1^2) + 2\sqrt{(a_1^2+b_1^2)(a_2^2+b_2^2)} + (a_2^2+b_2^2) \ge (a_1+a_2)^2 + (b_1+b_2)^2$

$2\sqrt{(a_1^2+b_1^2)(a_2^2+b_2^2)} \ge a_1^2+2a_1a_2+a_2^2 + b_1^2+2b_1b_2+b_2^2 - a_1^2-b_1^2-a_2^2-b_2^2$

$2\sqrt{(a_1^2+b_1^2)(a_2^2+b_2^2)} \ge 2a_1a_2+2b_1b_2$

$(a_1^2+b_1^2)(a_2^2+b_2^2) \ge (a_1a_2+b_1b_2)^2$

Which is true because of Cauchy-Schwarz.

Inductive Hypothesis:

Assume the inequality is true for $n = k$

$\sqrt{a_1^2 + b_1^2} + \sqrt{a_2^2 + b_2^2} + ... + \sqrt{a_k^2 + b_k^2} \ge \sqrt{(a_1+a_2+...+a_k)^2 + (b_1+b_2+...+b_k)^2}$

is true.

Proof:

Need to prove it's true for $n = k+1$

$\sqrt{a_1^2 + b_1^2} + \sqrt{a_2^2 + b_2^2} + ... + \sqrt{a_{k+1}^2 + b_{k+1}^2} \ge \sqrt{(a_1+a_2+...+a_{k+1})^2 + (b_1+b_2+...+b_{k+1})^2}$

So let's add $\sqrt{a_{k+1}^2 + b_{k+1}^2}$ to our inductive hypothesis.

This yields:

$\sqrt{a_1^2 + b_1^2} + \sqrt{a_2^2 + b_2^2} + ... + \sqrt{a_k^2 + b_k^2} + \sqrt{a_{k+1}^2 + b_{k+1}^2} \ge \sqrt{(a_1+a_2+...+a_k)^2 + (b_1+b_2+...+b_k)^2} + \sqrt{a_{k+1}^2 + b_{k+1}^2}$

now what?

2. It would be better to prove it By using the Second Mathematical Induction(change the inductive hypothesis to $n\le k$)

3. write the inductive hypothesis as
$\left( \sqrt{a_{1}^{2}+b_{1}^{2}}+\sqrt{a_{2}^{2}+b_{2}^{ 2}}+\cdots
+\sqrt{a_{k}^{2}+b_{k}^{2}}\right)
^{2}$
$\geq \left( \sum\limits_{i=1}^{k}a_{i}^{2}\right)
^{2}+\left( \sum\limits_{i=1}^{k}b_{i}^{2}\right)
^{2}$

Let $RHS$ denote the right hand side of the above inequality.
Notice that
$\left( \sqrt{a_{1}^{2}+b_{1}^{2}}+\sqrt{a_{2}^{2}+b_{2}^{ 2}}+\cdots
+\sqrt{a_{k}^{2}+b_{k}^{2}}+\sqrt{a_{k+1}^{2}+b_{k +1}^{2}}\right)
^{2}$
$=\left( \sum\limits_{i=1}^{k}\sqrt{a_{i}^{2}+b_{i}^{2}}\ri ght)
^{2}+2\sqrt{a_{k+1}^{2}+b_{k+1}^{2}}\left( \sum\limits_{i=1}^{k}\sqrt
{a_{i}^{2}+b_{i}^{2}}\right) +\left( \sqrt{a_{k+1}^{2}+b_{k+1}^{2}}\right)
^{2}$

$\left( \sum\limits_{i=1}^{k+1}a_{i}\right) ^{2}$ $=\left( \sum\limits_{i=1}%
^{k}a_{i}\right) ^{2}+$
$2a_{k+1}\left( \sum\limits_{i=1}^{k}a_{i}\right)
+a_{k+1}^{2}$

$\left( \sum\limits_{i=1}^{k+1}b_{i}\right) ^{2}$ $=\left( \sum\limits_{i=1}%
^{k}b_{i}\right) ^{2}+$
$2b_{k+1}\left( \sum\limits_{i=1}^{k}b_{i}\right)
+b_{k+1}^{2}$

From the inductive hypothesis,

$\left( \sum\limits_{i=1}^{k}\sqrt{a_{i}^{2}+b_{i}^{2}}\ri ght) ^{2}%
+2\sqrt{a_{k+1}^{2}+b_{k+1}^{2}}\left( \sum\limits_{i=1}^{k}\sqrt{a_{i}%
^{2}+b_{i}^{2}}\right) +\left( \sqrt{a_{k+1}^{2}+b_{k+1}^{2}}\right)
^{2}$
$\geq RHS+2\sqrt{a_{k+1}^{2}+b_{k+1}^{2}}\left( \sum\limits_{i=1}^{k}%
\sqrt{a_{i}^{2}+b_{i}^{2}}\right) +\left( \sqrt{a_{k+1}^{2}+b_{k+1}^{2}%
}\right) ^{2}$

and now it only remain to show that

$2\sqrt{a_{k+1}^{2}+b_{k+1}^{2}}\left( \sum\limits_{i=1}^{k}\sqrt{a_{i}%
^{2}+b_{i}^{2}}\right) +\left( \sqrt{a_{k+1}^{2}+b_{k+1}^{2}}\right)
^{2}$
$\geq2a_{k+1}\left( \sum\limits_{i=1}^{k}a_{i}\right) +a_{k+1}%
^{2}+2b_{k+1}\left( \sum\limits_{i=1}^{k}b_{i}\right)$
$+b_{k+1}^{2}$

Hence,

$\left( \sqrt{a_{1}^{2}+b_{1}^{2}}+\sqrt{a_{2}^{2}+b_{2}^{ 2}}+\cdots
+\sqrt{a_{k+1}^{2}+b_{k+1}^{2}}\right)
^{2}$
$\geq \left( \sum\limits_{i=1}^{k+1}a_{i}^{2}\right)
^{2}+\left( \sum\limits_{i=1}^{k+1}b_{i}^{2}\right)
^{2}$