Need help with this proof via induction

$$\tag{*} \underbrace{(x_1 + \ldots + x_n)}_{A}~\underbrace{\left(\frac1{x_1} + \ldots + \frac1{x_n}\right)}_B \ge n^2$$

$$ \begin{split} (x_1 + &\ldots + x_n + x_{n+1}) \left(\frac1{x_1} + \ldots + \frac1{x_n} + \frac{1}{x_{n+1}}\right) \\ &= \left(A+x_{n+1}\right)\left(B+\frac{1}{x_{n+1}}\right) \\ &= AB + \frac{A}{x_{n+1}} + Bx_{n+1}+ 1 \overset{(*)} \\ \\ &\ge n^2 + \color{red}{\frac{A}{x_{n+1}} + Bx_{n+1}}+ 1 \\ &\ge n^2 + \color{red}{2\sqrt{AB}}+1\overset{(*)} \\ \\ &\ge n^2+2n+1 \\ &= (n+1)^2 \ \ \ \ \square \end{split} $$ where the red part follows from the basic inequality $a+b\ge 2\sqrt{ab} \ \ (a,b \ge 0)$


HINT

For the inductive step, assume this is true for some $n-1 \ge 1$ and let's prove it for $n$. We get $$ \begin{split} \sum_{k=1}^n x_k \sum_{k=1}^n \frac{1}{x_k} &= \left(x_n + \sum_{k=1}^{n-1} x_k\right) \left(\frac1{x_n} + \sum_{k=1}^{n-1} \frac{1}{x_k}\right) \\ &= 1 + x_n \sum_{k=1}^n \frac{1}{x_k} + \frac1{x_n} \sum_{k=1}^{n-1} x_k + \sum_{k=1}^{n-1} x_k \sum_{k=1}^{n-1} \frac{1}{x_k} \end{split} $$ By the inductive hypothesis, you know the last term is at least $(n-1)^2$ and you need to prove that the whole sum is at least $n^2$. Can you do it now?


When expanding, you have $n^2$ summands of the form $\frac{x_i}{x_j}$. Those with $i=j$ are equal and contribute $1$ each to the sum. Those with $i\ne j$ come in pairs and $$\frac{x_i}{x_j}+\frac{x_j}{x_i}=\left(\sqrt{\frac{x_i}{x_j}}-\sqrt{\frac{x_j}{x_i}}\right)^2+2\ge 2.$$

Tags:

Induction