Proving the Cauchy-Schwarz inequality by induction

I ran across this problem in some old notes, and I frustratingly can't figure out how to do it

Let $a_i$ and $b_i$ be sequences of natural numbers, use induction to show

$\sum_{i=1}^n (a_ib_i)^{1/2} \le (\sum_{i=1}^n a_i)^{1/2}(\sum_{i=1}^n b_i)^{1/2} $

Obviously this is trivial to show for n=1. I can't make much progress on n+1. I've tried various tactics, squaring both sides etc.

Any hint or help would be appreciated. Thanks.

Solution 1:

Hint: Another way would be to rewrite using the substitutions $x_i^2=a_ib_i$ and $y_i^2=a_i^2$ in the form $$CS(n): \quad \frac {\left( \sum_{i=1}^n x_i \right)^2}{\sum_{i=1}^n y_i} \le \sum_{i=1}^n \frac{x_i^2}{y_i}$$ This form is particularly amenable to induction, after you prove the base case of $n=2$.

Solution 2:

Set for first $a_i = c_i^2$ and $b_i = d_i^2$, with $c_i,b_i\geq 0$. We know that: $$\left(\sum_{i=1}^{n}c_i d_i\right)^2 \leq \left(\sum_{i=1}^{n}c_i^2\right)\left(\sum_{i=1}^{n}d_i^2\right)\tag{1}$$ and we need to prove that: $$\left(\sum_{i=1}^{n+1}c_i d_i\right)^2 \leq \left(\sum_{i=1}^{n+1}c_i^2\right)\left(\sum_{i=1}^{n+1}d_i^2\right).\tag{2}$$ We have: $$\begin{eqnarray*}\left(\sum_{i=1}^{n+1}c_i d_i\right)^2 &=& \left(\sum_{i=1}^{n}c_i d_i\right)^2+(c_{n+1}d_{n+1})^2\\ &+& 2c_{n+1}d_{n+1}\left(\sum_{i=1}^{n}c_i d_i\right),\end{eqnarray*}$$ $$\begin{eqnarray*}\left(\sum_{i=1}^{n+1}c_i^2\right)\left(\sum_{i=1}^{n+1}d_i^2\right)&=&\left(\sum_{i=1}^{n}c_i^2\right)\left(\sum_{i=1}^{n}d_i^2\right)+(c_{n+1}d_{n+1})^2\\&+&c_{n+1}^2\sum_{i=1}^n d_i^2 + d_{n+1}^2\sum_{i=1}^n c_i^2\end{eqnarray*}$$ hence in order to prove $(2)$ we just need to show that $$2c_{n+1}d_{n+1}\left(\sum_{i=1}^{n}c_i d_i\right)\leq c_{n+1}^2\sum_{i=1}^n d_i^2 + d_{n+1}^2\sum_{i=1}^n c_i^2.\tag{3}$$ Since $$c_{n+1}^2\sum_{i=1}^n d_i^2 - 2c_{n+1}d_{n+1}\left(\sum_{i=1}^{n}c_i d_i\right)+ d_{n+1}^2\sum_{i=1}^n c_i^2$$ regarded as a bivariate polynomial in $c_{n+1}$ and $d_{n+1}$, has a non-positive discriminant due to $(1)$, $(3)$ is proved.

Solution 3:

Key Step:

$a_1b_1+a_2b_2+...+a_nb_n+a_{n+1}b_{n+1} $ $= (a_1b_1+a_2b_2+...+a_nb_n)+a_{n+1}b_{n+1}$
$ \le \left(a_1^2+a_2^2+...+a_n^2 \right)^{1/2}\left(b_1^2+b_2^2+...+b_n^2\right)^{1/2}+a_{n+1}b_{n+1}$ $\le \left( a_1^2+a_2^2+...+a_n^2+a_{n+1}^2 \right)^{1/2} \left( b_1^2+b_2^2+...+b_n^2+b_{n+1}^2 \right)^{1/2}$

where in the first inequality we used the induction hypothesis, and in the second
inequality we use the case n = 2 in the form $\alpha \beta +a_{n+1}b_{n+1} \le (\alpha^2+a_{n+1}^2)^{1/2}(\beta^2+b_{n+1}^2)^{1/2}$ with the new variables $\alpha =\left( a_1^2+a_2^2+...+a_n^2 \right)^{1/2}$ and $\beta = \left(b_1^2+b_2^2+...+b_n^2\right)^{1/2}$