SMO 2009 Problem 3

for $k\in\mathbb{N}$ , define $A_n$ for $n=1,2,...$ by $A_{n+1} = \frac{ nA_n+2(n+1)^{2k} }{n+2} , A_1=1$ Prove $A_n$ is integer for all $n\geq 1$ , and $A_n$ is odd if and only if $n\equiv$ 1 or 2(mod 4)