To prove that $a_{2016} > \frac{1}{2} + a_{1000}$, we need to analyze the given sequence and its properties.

1. Define the sequence and initial condition:
$$a_1 = 0$$
$$a_{n+1} = \frac{a_1 + a_2 + \ldots + a_n}{n} + 1$$

2. Calculate the first few terms to identify a pattern:
$$a_2 = \frac{a_1}{1} + 1 = 0 + 1 = 1$$
$$a_3 = \frac{a_1 + a_2}{2} + 1 = \frac{0 + 1}{2} + 1 = \frac{1}{2} + 1 = \frac{3}{2}$$
$$a_4 = \frac{a_1 + a_2 + a_3}{3} + 1 = \frac{0 + 1 + \frac{3}{2}}{3} + 1 = \frac{\frac{5}{2}}{3} + 1 = \frac{5}{6} + 1 = \frac{11}{6}$$

3. Generalize the sequence:
Notice that the sequence $a_n$ can be expressed in terms of the harmonic series. We can rewrite the recurrence relation as:
$$S_n = a_1 + a_2 + \ldots + a_n$$
$$a_{n+1} = \frac{S_n}{n} + 1$$
$$S_{n+1} = S_n + a_{n+1} = S_n + \frac{S_n}{n} + 1 = S_n \left(1 + \frac{1}{n}\right) + 1$$
$$S_{n+1} = S_n \frac{n+1}{n} + 1$$

4. **Simplify the sum $S_n$:**
$$S_{n+1} = S_n \frac{n+1}{n} + 1$$
$$S_{n+1} = S_n \left(1 + \frac{1}{n}\right) + 1$$
By induction, we can show that $S_n$ grows approximately as $n \log n$.

5. **Estimate $a_n$:**
Since $a_n = \frac{S_{n-1}}{n-1} + 1$, we can approximate:
$$a_n \approx \log n + 1$$

6. **Compare $a_{2016}$ and $a_{1000}$:**
$$a_{2016} \approx \log 2016 + 1$$
$$a_{1000} \approx \log 1000 + 1$$
$$\log 2016 \approx \log (2 \times 1008) \approx \log 2 + \log 1008 \approx 0.301 + \log 1000 + \log 1.008$$
$$\log 1000 = 3, \quad \log 1.008 \approx 0.003$$
$$\log 2016 \approx 0.301 + 3 + 0.003 = 3.304$$
$$a_{2016} \approx 3.304 + 1 = 4.304$$
$$a_{1000} \approx 3 + 1 = 4$$
$$\frac{1}{2} + a_{1000} = \frac{1}{2} + 4 = 4.5$$

7. Conclusion:
$$a_{2016} \approx 4.304 < 4.5$$
Therefore, the inequality $a_{2016} > \frac{1}{2} + a_{1000}$ does not hold.

The final answer is $\boxed{ a_{2016} < \frac{1}{2} + a_{1000} }$