Given $ a_{k+1} \ge \frac{k a_{k}}{(a_{k}^{2} + k-1)}, \:\: k > 0$, prove $ S_{n} = a_{1} + .. + a_{n} \ge n, \:\: n \ge 2 $ Suppose a sequence of positive real numbers with
$$  a_{k+1} \ge \frac{k a_{k}}{(a_{k}^{2} + k-1)}, \:\: k > 0$$
prove that $$ S_{n}  = a_{1} + .. + a_{n} \ge n, \:\: n \ge 2 $$

Solution: I will show two different approaches, one is finished, the other one is still confusing


*

*Finished approach:


By induction, for the base case we have 
$$ a_{2} \ge a_{1}/a_{1}^{2} = 1/a_{1}^ \implies a_{1} a_{2} \ge 1 $$
by AM-GM we get $a_{1}+a_{2} \ge 2\sqrt{a_{1}a_{2}} \ge 2 $. (base case proven).
Now assume it is true for $n=k$. We will prove for $n=k+1$.
$$ S_{k+1} = S_{k} + a_{k+1} \ge k + a_{k+1} $$
if $a_{k+1} \ge 1$ then the the proof is finished. Now if $0 < a_{k+1} < 1$, here is another approach in the induction:
notice that the known inequality at the top of the post is equivalent with
$$  a_{k} \ge k/a_{k+1} - (k-1)/a_{k} $$
summing all from $k=1,2,...,m$ we get 
$$ S_{m} \ge m/a_{m+1} $$
using this to prove for $n=k+1$ with $0 < a_{k+1} < 1$, we get
$$ S_{k+1} = S_{k} + a_{k+1} \ge k/a_{k+1} + a_{k+1}  = (k-1)/a_{k+1} +  ( a_{k+1} + 1/a_{k+1} )$$
Now $a_{k+1} + 1/a_{k+1} \ge 2$ this is because $f(x) = x + 1/x \ge 2, \:\: 0 < x < 1$ (function is monotonically decreasing with convergence to 2). So we have
$$ S_{k+1} \ge (k-1)/a_{k+1} +  ( a_{k+1} + 1/a_{k+1} ) \ge (k-1) + 2 = k + 1$$
THus we have solved the problem. 


*

*Unfinished approach:


Here is a hint of the IMO 2015 shortlisted problem:
"Using AM-GM on $S_{k}$ and $k a_{k+1}$ we may prove:
$S_{k} + k a_{k+1} \ge 2k$
then sum all of them from $k=1,2,....,m$."
the inequality is quite easy to prove, but after the summation idk what else to do:
$$ S_{1} + a_{2} \ge 2 $$
$$ S_{2} + 2 a_{3} \ge 2(2) $$
$$ ...$$
$$ S_{m} + (m) a_{m+1} \ge 2(m) $$
then 
$$ S_{1} + ... + S_{m} + a_{2} + ... + (m) a_{m+1} \ge m (m+1) $$

Remember $S_k=a_1+a_2+\dots+a_k$, so
$$
S_1+S_2+\dots+S_m=ma_1+(m-1)a_2+\dots+a_m.
$$
Hence you have
$$
m(a_1+a_2+\dots+a_m+a_{m+1})\geq m(m+1)
$$
which gives $S_{m+1}\geq m+1$.
