[Proof] Since
$$(n+2) a_{n+1}=n a_{n}+2(n+1)^{2 r}$$

Therefore $\square$
$$(n+2)(n+1) a_{n+1}=(n+1) n a_{n}+2(n+1)^{2 r+1}$$

Let
$$\begin{array}{l} b_{n}=(n+1) n a_{n}, n=1,2,3, \cdots \\ b_{n+1}=b_{n}+2(n+1)^{2 r+1} \end{array}$$

Then $\square$
Thus, from $b_{1}=2$ we have
$$b_{n}=2 \sum_{k=1}^{n} k^{2 r+1}, n=1,2, \cdots$$

When $n=1$, it is clear from $b_{1}=2$ that $1 \cdot(1+1) \mid b_{1}$. Suppose $n>1$, since
$$b_{n}=2 n^{2 r+1}+\sum_{k=1}^{n-1}\left(k^{2 r+1}+(n-k)^{2 r+1}\right)$$

And $2 r+1$ being odd implies
$$n \mid k^{2 r+1}+(n-k)^{2 r+1},$$

Therefore
$$n \mid b_{n}$$

On the other hand, from
$$b_{n}=\sum_{k=1}^{n}\left(k^{2 r+1}+(n+1-k)^{2 r+1}\right)$$

And
$$n+1 \mid k^{2 r+1}+(n+1-k)^{2 r+1}$$

We know
$$n+1 \mid b_{n}$$

By the fact that $n$ and $n+1$ are coprime, we get
$$n(n+1) \mid b_{n}, n=1,2,3, \cdots$$

That is, $a_{n}=\frac{b_{n}}{n(n+1)}$ is a positive integer.
Next, we discuss the parity of $a_{n}$. When $n$ is even, it is clear that $a_{n}$ and $\frac{b_{n}}{n}$ have the same parity. Also, $\frac{b_{2}}{2}=1+2^{2 r+1}$, and when $n>2$,
$$\begin{aligned} b_{n} & =2 n^{2 r+1}+\sum_{k=1}^{n-1}\left(k^{2 r+1}+(n-k)^{2 r+1}\right) \\ & =2 n^{2 r+1}+2 \sum_{k=1}^{\frac{n-2}{2}}\left(k^{2 r+1}+(n-k)^{2 r+1}\right)+2 \cdot\left(\frac{n}{2}\right)^{2 r+1} \end{aligned}$$

Therefore, $\frac{b_{n}}{n}$ and $\left(\frac{n}{2}\right)^{2 r}$ have the same parity. This immediately gives us
$$a_{n}=\left\{\begin{array}{l} \text { even, when } n \equiv 0(\bmod 4), \\ \text { odd, when } n \equiv 2(\bmod 4) . \end{array}\right.$$

When $n$ is odd, it is clear that $a_{n}$ and $\frac{b_{n}}{n+1}$ have the same parity. Since $b_{1}=2$, and when $n>1$,
$$\begin{aligned} b_{n} & =\sum_{k=1}^{n}\left(k^{2 r+1}+(n+1-k)^{2 r+1}\right) \\ & =2 \sum_{k=1}^{\frac{n-1}{2}}\left(k^{2 r+1}+(n+1-k)^{2 r+1}\right)+2\left(\frac{n+1}{2}\right)^{2 r+1} \end{aligned}$$

Thus, $\frac{b_{n}}{n+1}$ and $\left(\frac{n+1}{2}\right)^{2 r}$ have the same parity, hence
$$a_{n}=\left\{\begin{array}{l} \text { even, when } n \equiv 3(\bmod 4), \\ \text { odd, when } n \equiv 1(\bmod 4) . \end{array}\right.$$

In summary, $a_{n}$ is even if and only if $n \equiv 0$ or $3(\bmod 4)$.