Sketch: ${\rm (a)}:$ Let $b_n\triangleq n^2 a_n$ be a new sequence. Then $(n+1)b_{n+1} = 2(2n+1)b_n + 2(3n+1)$. ${\rm (b)}:$ Let now $c_n =b_n+2$. Then arrive at $(n+1)c_{n+1}=2(2n+1)c_n$. ${\rm (c)}:$ Prove by induction that $c_n = \binom{2n}{n}$, and thus $a_n = \frac{1}{n^2}(\binom{2n}{n}-2)$. ${\rm (d)}:$ Finally if $n=p$ is a prime, use double counting to show $\binom{2p}{p}-2=\sum_{k=1}^{p-1}\binom{p}{k}^2$, which yields the desired claim.