No need for induction to derive the formula. $na_{n+1}=2(n+1)a_n-n-2\implies n(a_{n+1}-1)=2(n+1)(a_n-1)\implies\frac{a_{n+1}-1}{a_n-1}=2\cdot\frac{n+1}{n}$ $\implies a_n=1+(a_1-1)\prod_{k=2}^n\frac{a_k-1}{a_{k-1}-1}=1+2\prod_{k=2}^n\frac{2k}{k-1}=1+2^n\prod_{k=2}^n\frac{k}{k-1}=n2^n+1$

A similar reasoning also establish, for any prime $p>2$, there exists infinitely many $m$, for which $p\mid a_m$ and $p\mid a_{m+1}$ (one just needs to ensure $m\equiv -2\pmod{p}$ and $m\equiv -2 \pmod{p-1}$ for infinitely many $m$'s, which is immediate by CRT).

Letting $b_n = a_n - 1$, we get $\frac{b_{n+1}}{n+1} = 2\frac{b_n}{n}$ and $b_1 = 2$. From here, it is easy to get that $b_n = n2^n$ and thus $a_n = n2^n + 1$ for all $n \geq 1$. Now let $p$ be an arbitrary odd prime. Taking $n = p-2$, we want $p \mid a_n = (p-2)2^{p-2} + 1$ and $p \mid a_{n+1} = (p-1)2^{p-1} + 1$. Those are easily verified by FLT, thus we are done. $\square$

Its a bit hard to notice but after checking small cases and notin how is this sequence formed u may try to show that $a_n=n2^n+1$ which is what are we going to do right now. The base case its clear so assume that this holds for $n=k$, hence we will prove it for $n=k+1$ $$ka_{k+1}=2(k+1)a_k-k-2=2(k+1)(k2^k+1)-k-2=k^22^{k+1}+k2^{k+1}+k=k((k+1)2^{k+1}+1) \implies a_{k+1}=(k+1)2^{k+1}+1$$Now the existence of FLT and $3-2=1$ (becuase of $a_1=3$) make us choose $m=p-2$ for any odd prime $p$ $$a_{p-2}=(p-2)2^{p-2}+1 \equiv 1-2^{p-1} \equiv 0 \pmod p$$$$a_{p-1}=(p-1)2^{p-1}+1 \equiv 1-2^{p-1} \equiv 0 \pmod p$$Thus we are done