# Proof by induction stuck at very end!!

• Nov 24th 2009, 09:20 PM
usagi_killer
Proof by induction stuck at very end!!
• Nov 24th 2009, 11:54 PM
Shanks
It would be better to prove it By using the Second Mathematical Induction(change the inductive hypothesis to $n\le k$)
• Nov 25th 2009, 03:38 AM
dedust
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}$