How to prove AM-GM by induction 3 Let $a_1;a_2;...;a_n\ge 0$. Prove that $$\frac{\sum ^n_{k=1}a_k}{n}\ge \sqrt[n]{\prod ^n_{k=1}a_k}$$

We will prove it's true with $n=k$. Indeed we need to prove it's true with $n=k+1$
WLOG $a_1\le a_2\le \cdots\le a_{k+1}$
So  $a_{k+1}\ge \frac{\sum ^k_{x=1}a_k}{k}=x\ge 0\Rightarrow a_{k+1}\ge x+y(y\ge 0)$
We have: $$\left(\frac{a_1+...+a_{k+1}}{k+1}\right)^{k+1}\ge \left(\frac{kx+x+y}{k+1}\right)^{k+1}=\left(x+\frac{y}{k+1}\right)^{k+1}$$
But $$a_1\cdot \cdot \cdot a_{k+1}\le x^k\left(x+y\right)$$
Then we need to prove $\left(x+\frac{y}{k+1}\right)^{k+1}\ge x^k\left(x+y\right) $
I'm stuck here, i need someone can solve my stuck.
 A: Hint: 
The idea is that first you prove that is valid for all $n=2^k$, $k\in \mathbb{N}$ (that is for infinite number of $n$). Then you use regresion induction (I think that what is called). You go from $n$ to $n-1$.
A: If one of variables is equal to zero, it's obvious.
Now, let $\prod\limits_{k=1}^na_k\neq0.$
Since our inequality is homogeneous, we can assume that $\prod\limits_{k=1}^na_k=1$ and we need to prove that
$$a_1+a_2+...+a_n\geq n.$$
Now, for $n=1$ it's obvious and let $a_1\geq a_2\geq...\geq a_{n+1}$ and $\prod\limits_{k=1}^{n+1}a_k=1.$
Thus, $a_1\geq1$ and $a_{n+1}\leq1,$ which says
$$(a_1-1)(a_{n+1}-1)\leq0$$ or
$$a_1+a_{n+1}\geq1+a_1a_{n+1}$$ and by the assuming of the induction we obtain:
$$a_1+a_2+...+a_{n+1}\geq1+a_2+...+a_{n}+a_1a_{n+1}\geq1+n\sqrt[n]{a_2...a_{n}a_1a_{n+1}}=n+1$$ and we are done!
A: Sometimes when you're proving things by induction it's paradoxically easiser to prove something stronger, because then you have a stronger "inductive hypothesis" to work with. Here for example we can prove this:


Suppose $t_1,\dots, t_n\ge0$ and $t_1+\dots+t_n=1$. If $a_1,\dots,a_n\ge0$ then $t_1a_1+\dots+t_na_n\ge a_1^{t_1}\dots a_n^{t_n}$.


Note that this becomes the inequality you ask about if $t_j=1/n$.
Alas we need to prove the case $n=2$ separately. Since $e^x$ is convex, if $0\le t\le 1$ then $$a_1^ta_2^{1-t}=e^{t\log(a_1)+(1-t)\log(a_2)}
\le te^{\log(a_1)}+(1-t)e^{\log(a_2)}=ta_1+(1-t)a_2.$$That's exactly the case $n=2$, with $t_1=t$ and $t_2=1-t$.
Now suppose it's true for $n=k$, $k\ge 2$. You can use the case $n=k$ together with the case $n=2$ to do the case $n=k+1$, by a little algebraic trick... If $t_{k+1}=1$ then all the other $t_j=0$, so there's nothing to prove. Assume $t_{k+1}<1$. Let $t=1-t_{k+1}$. Then
$$\frac{t_1}t+\dots+\frac{t_k}t=1.$$Apply the case $n=k$ with $t_j/t$ in place of $t$ and you get $$\frac1t(t_1a_1+\dots+t_ka_k)\ge a_1^{t_1/t}\dots a_k^{t_k/t}.$$ So  the case $n=2$ shows that $$\begin{aligned}t_1a_1+\dots+t_{k+1}a_{k+1}
&=t\left(\frac1t(t_1a_1+\dots+t_ka_k)\right)+(1-t)a_{k+1}
\\&\ge\left(\frac1t(t_1a_1+\dots+t_ka_k)\right)^ta_{k+1}^{t_{k+1}}
\\&\ge\left(a_1^{t_1/t}\dots a_k^{t_k/t}\right)^ta_{k+1}^{t_{k+1}}
\\&=a_1^{t_1}\dots a_{k+1}^{t_{k+1}}.\end{aligned}$$
A: Here is how the proof by induction works. Let $\mu_n=\frac1n\sum_{i=1}^n a_i$ and $\rho_n=\big(\prod_{i=1}^n a_i\big)^{1/n}$. 
Assuming $\mu_n\ge \rho_n$ by way of induction, we have
$$
\mu_{n+1}=\frac{n}{n+1}\Big(\frac{a_1+\dots+a_n}{n}\Big)+\frac{a_{n+1}}{n+1}=\frac{n}{n+1}\mu_n+\frac1{n+1}a_{n+1}\ge \frac{n}{n+1}\rho_n + \frac1{n+1}a_{n+1}
$$
We want to show that last quantity is at least $\rho_{n+1}=\rho_n^{n/(n+1)}a_{n+1}^{1/(n+1)}$. Letting
$$
x=\rho_n,\qquad y=a_{n+1},\qquad\lambda=\frac1n
$$
for ease of reading, we must show that
$$
(1-\lambda)x+\lambda y\stackrel{?}\ge x^{1-\lambda}\cdot y^{\lambda}
$$
Taking logs, this is equivalent to showing
$$
\log\big((1-\lambda)x+\lambda y\big)\stackrel{?}\ge(1-\lambda)\log x+\lambda \log y
$$
This last equality is indeed true, and is a consequence of the fact that $\log$ is concave down, or that the second derivative of $\log$ is always negative.
