# Proof that $\left(\sum^n_{k=1}x_k\right)\left(\sum^n_{k=1}y_k\right)\geq n^2$

If $x_1,...,x_n$ are positive real numbers and if $y_k=1/x_k$, prove that $$\left(\sum^n_{k=1}x_k\right)\left(\sum^n_{k=1}y_k\right)\geq n^2.$$

I've been learning induction, and I've come across this problem that I really can't even break down and begin to think about. I've been told it has something to do with Cauchy-Schwarz, but I cannot figure out how to apply it. I would appreciate help figuring out how to go about and formulate this proof. Thanks!

• Does it help to call $x_k$ by the name of $a_k^2$? – Daniel Fischer Sep 25 '13 at 1:15
• Cauchy-Schwarz inequality has sum of $a_k^2$ and sum of $b_k^2$ terms multiplied together. Can you guess that? – peterwhy Sep 25 '13 at 1:16
• One way to begin on a problem like this is to take a small $n$ and see what's going on. For $n=2$ the inequality is $$(a+b)\left(\frac{1}{a} + \frac{1}{b}\right) \geq 4$$. Can you show that? – Matthew Leingang Jul 26 '16 at 17:03
• Just use the Cauchy-Schwarz Inequality with $x_i=\sqrt{a_i}$ and $y_i=\frac{1}{\sqrt{a_i}}$. – Mark Viola Jul 26 '16 at 17:18

There are couple of ways to prove this. One way is via AM-GM, i.e., we have $$\sum_{k=1}^n x_k \geq n \sqrt[n]{x_1 x_2 \ldots x_n}$$ and $$\sum_{k=1}^n \dfrac1{x_k} \geq n \sqrt[n]{\dfrac1{x_1 x_2 \ldots x_n}}$$ Multiplying the two, we get what we want.

Another way is consider the vectors $$\left(\sqrt{x_1},\sqrt{x_2}, \ldots, \sqrt{x_n} \right) \text{ and }\left(\dfrac1{\sqrt{x_1}},\dfrac1{\sqrt{x_2}}, \ldots, \dfrac1{\sqrt{x_n}} \right)$$ and apply Cauchy-Schwarz to get what you want.

• In the first proof you are actually proving the AM-HM inequality ;) – N. S. Sep 25 '13 at 1:23
• Very helpful. Thank you! :) – Jackson Sep 25 '13 at 1:29

You can in fact prove it by induction on $n$. For the induction step observe that

\begin{align*} \left(\sum_{k=1}^{n+1}x_k\right)\left(\sum_{k=1}^{n+1}\frac1{x_k}\right)&=\left(\sum_{k=1}^nx_k+x_{n+1}\right)\left(\sum_{k=1}^n\frac1{x_k}+\frac1{x_{n+1}}\right)\\ &=\left(\sum_{k=1}^nx_k\right)\left(\sum_{k=1}^n\frac1{x_k}\right)+x_{n+1}\sum_{k=1}^n\frac1{x_k}+\frac1{x_{n+1}}\sum_{k=1}^nx_k+1\\ &\ge n^2+1+x_{n+1}\sum_{k=1}^n\frac1{x_k}+\frac1{x_{n+1}}\sum_{k=1}^nx_k\;; \end{align*}

$(n+1)^2=n^2+2n+1$, so to finish the step, it suffices to show that

$$x_{n+1}\sum_{k=1}^n\frac1{x_k}+\frac1{x_{n+1}}\sum_{k=1}^nx_k\ge 2n\;.$$

For $k=1,\ldots,n$ let $u_k=\dfrac{x_k}{x_{n+1}}$; then

$$x_{n+1}\sum_{k=1}^n\frac1{x_k}+\frac1{x_{n+1}}\sum_{k=1}^nx_k=\sum_{k=1}^n\left(\frac1{u_k}+u_k\right)\;,$$

and it’s not hard to show that if $u>0$, then $\dfrac1u+u\ge 2$, either by showing that $f(u)=\frac1u+u$ on the positive reals has a minimum at $u=1$, or by observing that for $u>0$ we have $f(u)\ge 2$ if and only if $u^2+1\ge 2u$ and showing that this inequality is always true.

The function $$f(x)=\frac{1}{x}$$ Is convex on $$(0,\infty)$$, so for $$a_1,\ldots,a_n>0$$ we have $$\frac{n}{a_1+\cdots+a_n}\leq\frac{1}{na_1}+\cdots+\frac{1}{na_n}.$$ Rearranging, we obtain the result.

$$\left(\sum_{k=1}^n {\sqrt{x_k}}^2\right)\left(\sum_{k=1}^n {\sqrt{x_k^{-1}}}^2\right) \ge \left(\sum_{k=1}^n {\sqrt{x_k}}\sqrt{x_k^{-1}}\right)^2 = n^2$$

We let $$x_{i+n}=x_i$$ for $$i\in\{1,2\dots n\}$$ .What you have is $$\sum_\limits{i=1}^n (\frac{x_1}{x_{1+i}}+\frac{x_2}{x_{2+i}}+\dots \frac{x_n}{x_{n+i}}).$$

By the rearrangement inequality each of these summands is greater than $$1+1+\dots +1=n$$

\begin{align} \sum_{k = 1}^{n}\left(\sqrt{x_{k}\,} + {\mu \over \sqrt{x_{k}\,}}\right)^{2} &\geq 0\,, \qquad \mu \in {\mathbb R} \\[3mm] \left(\sum_{k = 1}^{n}{1 \over x_{k}}\right)\mu^{2} + 2n\mu + \left(\sum_{k = 1}^{n}x_{k}\right) &\geq 0 \\ \left(2n\right)^{2} - 4\left(\sum_{k = 1}^{n}{1 \over x_{k}}\right)\left(\sum_{k = 1}^{n}x_{k}\right) & \leq 0 \end{align}

$$\begin{array}{|c|}\hline\\ \color{#ff0000}{\large\quad% \sum_{k = 1}^{n}x_{k}\sum_{k = 1}^{n}{1 \over x_{k}} \color{#000000}{\ \geq\ } n^{2} \quad} \\ \\ \hline \end{array}$$

You can use Cauchy-Schwarz inequality with $$u_i = \sqrt{x_i}$$ and $$v_i=\frac{1}{\sqrt{x_i}}$$.