How can I prove that $(a_1+a_2+\dotsb+a_n)(\frac{1}{a_1}+\frac{1}{a_2}+\dotsb+\frac{1}{a_n})\geq n^2$ I've been struggling for several hours, trying to prove this horrible inequality:
$(a_1+a_2+\dotsb+a_n)\left(\frac{1}{a_1}+\frac{1}{a_2}+\dotsb+\frac{1}{a_n}\right)\geq n^2$.
Where each $a_i$'s are positive and $n$ is a natural number.
First I tried the usual "mathematical induction" method, but it made no avail, since I could not show it would be true if $n=k+1$.
Suppose the inequality holds true when $n=k$, i.e.,
$(a_1+a_2+\dotsb+a_k)\left(\frac{1}{a_1}+\frac{1}{a_2}+\dotsb+\frac{1}{a_k}\right)\geq n^2$.
This is true if and only if
$(a_1+a_2+\dotsb+a_k+a_{k+1})\left(\frac{1}{a_1}+\frac{1}{a_2}+\dotsb+\frac{1}{a_k}+\frac{1}{a_{k+1}}\right) -a_{k+1}\left(\frac{1}{a_1}+\dotsb+\frac{1}{a_k}\right)-\frac{1}{a_{k+1}}(a_1+\dotsb+a_k)-\frac{a_{k+1}}{a_{k+1}} \geq n^2$.
And I got stuck here.
The question looks like I have to use AM-GM inequality at some point, but I do not have a clue. Any small hints and clues will be appreciated.

Here is the proof by induction
that you wanted.
I added a more exact
version of
the identity used
in the proof
at the end.
Let
$s_n
=u_nv_n
$
where
$u_n=\sum_{k=1}^n a_k,
v_n= \sum_{k=1}^n \dfrac1{a_k}
$.
Then,
assuming
$s_n \ge n^2$,
$\begin{array}\\
s_{n+1}
&=u_{n+1}v_{n+1}\\
&=(u_n+a_{n+1}) (v_n+\dfrac1{a_{n+1}})\\
&=u_nv_n+u_n\dfrac1{a_{n+1}}+a_{n+1}v_n+1\\
&=s_n+u_n\dfrac1{a_{n+1}}+a_{n+1}v_n+1\\
&\ge n^2+u_n\dfrac1{a_{n+1}}+a_{n+1}v_n+1\\
\end{array}
$
So it is sufficient
to show that
$u_n\dfrac1{a_{n+1}}+v_na_{n+1}
\ge 2n
$.
By simple algebra,
if $a, b \ge 0$ then
$a+b
\ge 2\sqrt{ab}
$.
(Rewrite as
$(\sqrt{a}-\sqrt{b})^2\ge 0$
or,
as an identity,
$a+b
=2\sqrt{ab}+(\sqrt{a}-\sqrt{b})^2$.)
Therefore
$\begin{array}\\
u_n\dfrac1{a_{n+1}}+v_na_{n+1}
&\ge \sqrt{(u_n\dfrac1{a_{n+1}})(v_na_{n+1})}\\
&= \sqrt{u_nv_n}\\
&=2\sqrt{s_n}\\
&\ge 2\sqrt{n^2}
\qquad\text{by the induction hypothesis}\\
&=2n\\
\end{array}
$
and we are done.
I find it interesting that
$s_n \ge n^2$
is used twice in the
induction step.
Note that,
if we use the identity above,
$a+b
=2\sqrt{ab}+(\sqrt{a}-\sqrt{b})^2$,
we get this:
$\begin{array}\\
s_{n+1}
&=s_n+u_n\dfrac1{a_{n+1}}+a_{n+1}v_n+1\\
&=s_n+2\sqrt{u_n\dfrac1{a_{n+1}}a_{n+1}v_n}+1+(\sqrt{u_n\dfrac1{a_{n+1}}}-\sqrt{a_{n+1}v_n})^2\\
&=s_n+2\sqrt{s_n}+1+\dfrac1{a_{n+1}}(\sqrt{u_n}-a_{n+1}\sqrt{v_n})^2\\
&=(\sqrt{s_n}+1)^2+\dfrac1{a_{n+1}}(\sqrt{u_n}-a_{n+1}\sqrt{v_n})^2\\
&\ge(\sqrt{s_n}+1)^2\\
\end{array}
$
with equality 
if and only if
$a_{n+1}
=\sqrt{\dfrac{u_n}{v_n}}
=\sqrt{\dfrac{\sum_{k=1}^n a_k}{\sum_{k=1}^n \dfrac1{a_k}}}
$.
