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.

• @AdamHughes But the sequence is composed of natural numbers, so $a_1$ can't be negative, for example. Commented Sep 3, 2014 at 21:12
• Did your notes cover the Cauchy-Schwartz inequality? Try putting $a_i=c_i^2,b_i=d_i^2$. Commented Sep 3, 2014 at 21:13
• en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality#Proof Commented Sep 3, 2014 at 21:15
• My notes didn't cover it, but I recall the inequality. With Cauchy inequality it's pretty trivial. Seems really obvious now. Thanks guys. Commented Sep 3, 2014 at 21:16
• Isn't the point here to prove Cauchy-Schwarz by induction? Done below, anyway. Commented Sep 3, 2014 at 21:31

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

• I like this kind of induction, where the base step is also what is needed for the induction. Commented Apr 1, 2018 at 22:01
• A proof of Pick's Theorem has this same feature, with the added bonus that the base case is significantly harder to prove than the induction step.
– Shai
Commented Oct 20, 2021 at 20:45

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

• Writing $x^2=a b$ feels a bit weird if $ab$ could be negative. Though I guess we don't use $x^2\ge0$ anywhere. Commented Apr 1, 2018 at 22:16
• @ThomasAhle the OP mentions $a_i, b_i$ as sequences of natural numbers. Hard to get $a_i b_i$ negative after that. Commented Apr 2, 2018 at 0:53

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.

There is also

$$\frac{\langle a, b\rangle}{\|a\|\|b\|} = \frac{\langle a', b'\rangle + a_nb_n}{\sqrt{\|a'\|^2+a_n^2}\sqrt{\|b'\|^2+b_n^2}} \le \frac{\|a'\|\|b'\| + a_nb_n}{\sqrt{\|a'\|^2+a_n^2}\sqrt{\|b'\|^2+b_n^2}} \le 1$$

where we used the notation $a = (a_1,\dots,a_{n-1}, a_n) = (a', a_n)$ and $\langle a,b\rangle = \sum_i a_i b_i$ and $\|a\| = \sqrt{\sum_i a_i^2}$.

Like many of the other answers, this assumes that you first prove the $n=2$ case, that is

\begin{align*} (x_1y_1+x_2y_2)^2 &= (x_1y_1)^2 + 2x_1y_1x_2y_2 + (x_2y_2)^2 \\&\le (x_1y_1)^2 + (x_2y_1)^2 + (x_1y_2)^2 + (x_2y_2)^2 \\& = (x_1^2+x_2^2)(y_1^2+y_2^2) \end{align*}

where we used $2xy \le x^2+y^2$, the basic inequality proven by $0\le(x-y)^2 = x^2+y^2-2xy$.