# 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 $\displaystyle n\le k$)

3. write the inductive hypothesis as
$\displaystyle \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}$$\displaystyle \geq \left( \sum\limits_{i=1}^{k}a_{i}^{2}\right) ^{2}+\left( \sum\limits_{i=1}^{k}b_{i}^{2}\right) ^{2} Let\displaystyle RHS denote the right hand side of the above inequality. Notice that \displaystyle \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}$$\displaystyle =\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}$

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

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

From the inductive hypothesis,

$\displaystyle \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}$$\displaystyle \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 \displaystyle 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}$$\displaystyle \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) $$\displaystyle +b_{k+1}^{2} Hence, \displaystyle \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}$$\displaystyle \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}$