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