$na_n=(n-1)a_n+a_n=a1+...+a_{n-1}+n-1+a_n=na_{n+1}-n+n-1=na_{n+1}-1$ $a_{n+1}=a_n+\frac{1}{n}$ $a_{2016}-a_{1000}=\frac{1}{1000}+\frac{1}{1001}+..+\frac{1}{2015}>\frac{1016*2}{1000+2015} =\frac{2032}{3015}>\frac{2}{3}$

$$a_n= \frac{1}{1}+ \frac{1}{2} + ... + \frac{1}{n-1}$$$$\frac{1}{1000} + ... + \frac{1}{2015} > \frac{1015}{2015} > \frac{1}{2}$$$\blacksquare$

same but different ending (maybe it is long) $a_{2016}=\frac{a_{1}+...+a_{2015}}{2016}+1$ $a_{2016}=\frac{(a_{1}+..+a_{999})+a_{1000}+...+a_{2015}}{2016} +1$ It is obvious that $a_{k+1} > a_{k}$ $a_{2016}>\frac{(a_{1}+..+a_{999})+2015a_{1000}}{2016}+1$ And $a_{1000}=a_{999}+\frac{1}{1000}<a_{999}+a_{2}$ $a_{2016}>\frac{(a_{1}+..+a_{999})+2015a_{1000}}{2016}+1>\frac{(a_{1}+a_{3}+...+a_{998})+2016a_{1000}}{2016}+1>a_{1000}+\frac{1}{2}$