The equation $x^2 - 2x - 41 = 0$ has roots $\alpha = 1 + \sqrt{42}$ and $\beta = 1 - \sqrt{42}$. Using $a_0 = 0$ and $a_1 = 2$, we obtain
$$a_n = \frac{\alpha^n - \beta^n}{\sqrt{42}} \quad \text{for all } n \ge 0. \qquad (2)$$
Note that if $h$ and $k$ are positive integers, then
$$\alpha^{h(k-1)} + \alpha^{h(k-2)}\beta^h + \alpha^{h(k-3)}\beta^{2h} + \dots + \beta^{(k-1)h}$$
is an integer. Since $\alpha\beta = -41$, this result follows once we show that $\alpha^m + \beta^m$ is an integer for every positive integer $m$. Now $\alpha + \beta = 2$ and
$$\alpha^{h+1} + \beta^{h+1} = (\alpha + \beta)(\alpha^h + \beta^h) - \alpha\beta(\alpha^{h-1} + \beta^{h-1}),$$
so the integrality of $\alpha^m + \beta^m$ follows using induction. Next
$$\alpha^8 - \beta^8 = (\alpha - \beta)(\alpha + \beta)(\alpha^2 + \beta^2)(\alpha^4 + \beta^4) = 2\sqrt{42} \cdot 2 \cdot 2 \cdot 43 \cdot 2 \cdot 2017.$$
Now $2016 = 8 \cdot 252$ and
$$a_{2016} = \frac{\alpha^{8 \cdot 252} - \beta^{8 \cdot 252}}{\sqrt{42}} \\ = \frac{\alpha^8 - \beta^8}{\sqrt{42}} \cdot \frac{\alpha^{8 \cdot 252} - \beta^{8 \cdot 252}}{\alpha^8 - \beta^8}$$
The second factor is an integer, on applying the result above with $k = 252$, $h = 8$, and the first factor is an integral multiple of $2017$. Hence $2017$ divides $a_{2016}$, as claimed.

We start in a similar manner to Solution 1 to obtain the formula (2). The binomial theorem then gives
$$a_{2016} = \frac{1}{\sqrt{42}} \left( (1 + \sqrt{42})^{2016} - (1 - \sqrt{42})^{2016} \right) = 2 \sum_{k=0}^{1007} \binom{2016}{2k+1} 42^k$$
The key observation is that for any prime number $p$ and $1 \le m < p$ we have $(p-1)(p-2) \cdots (p-m) \equiv (-1)^m m! \pmod{p}$
and because $\gcd(p, m) = 1$ this implies that
$$\binom{p-1}{m} = \frac{(p-1)(p-2)\cdots(p-m)}{m!} \equiv (-1)^m \pmod{p}.$$
Because $2017$ is a prime number, we see now that
$$\binom{2016}{2k+1} \equiv -1 \pmod{2017}$$
for all $0 \le k \le 1007$. Hence,
$$a_{2016} \equiv -2 \sum_{k=0}^{1007} 42^k \equiv -\frac{2}{41} (42^{1008} - 1) \pmod{2017}$$
and so $a_{2016}$ is divisible by $2017$ iff $42^{1008} \equiv 1 \pmod{2017}$. This could be checked by a tedious calculation, but can also be seen with the aid of Legendre symbols and quadratic reciprocity as follows. By Euler's criterion, we have $42^{1008} \equiv (2017^{42}) \pmod{2017}$. Next, we compute the Legendre symbol $(2017^{42})$ via
$$\begin{aligned} \left(\frac{42}{2017}\right) &= \left(\frac{2}{2017}\right) \left(\frac{3}{2017}\right) \left(\frac{7}{2017}\right) \\ &= \left(\frac{3}{2017}\right) \left(\frac{7}{2017}\right) \\ &= \left(\frac{2017}{3}\right) \left(\frac{2017}{7}\right) \\ &= \left(\frac{1}{3}\right) \left(\frac{1}{7}\right) = 1, \end{aligned}$$
where in the second line we have used the fact that $\left(\frac{2}{2017}\right) = 1$ since $2017 \equiv 1 \pmod{8}$, and the third line follows from the fact that $2017 \equiv 1 \pmod{4}$. This gives the desired result that $42^{1008} \equiv 1 \pmod{2017}$.

We start in a similar manner to Solution 1 to obtain the formula (2). Note that $p = 2017$ is prime. Next we show that $42$ is a quadratic residue mod $2017$ (either by observing that $119^2 \equiv 42 \pmod{2017}$, by using the argument in Solution 2, or otherwise). Finally, letting $r^2 \equiv 42 \pmod{2017}$, we interpret the formula (2) over the field of integers mod $2017$ to obtain
$$a_{p-1} \equiv \frac{(1+r)^{p-1} - (1-r)^{p-1}}{r} \pmod{2017}.$$
By Fermat's little theorem, $p$ divides $((1+r)^{p-1} - 1) - ((1-r)^{p-1} - 1)$, and so $p$ divides $r_{p-1}$. Thus $p$ divides $a_{p-1}$, i.e., $2017$ divides $a_{2016}$.

Consider the recursion modulo $2017$ and go back eight steps
$$\begin{align*} a_{8k+8} &= 2a_{8k+7} + 41a_{8k+6} \\ &= 45a_{8k+6} + 82a_{8k+5} \\ &= 172a_{8k+5} + 1845a_{8k+4} \\ &\equiv 172a_{8k+4} + 1001a_{8k+3} \pmod{2017} \\ &\equiv 1345a_{8k+3} + 1001a_{8k+2} \pmod{2017} \\ &\equiv 1674a_{8k+2} + 686a_{8k+1} \pmod{2017} \\ &\equiv 56a_{8k} \pmod{2017}. \end{align*}$$
Because $a_0 = 0$ it now follows by induction that $2017$ divides $a_{8k}$ for every non-negative integer $k$. As $2016$ is divisible by $8$, the result follows.