Observe that since $P_i\in\mathbb {Z}[x] $ it follows that $P_i(z)=0\iff P_i (\overline z)=0$, hence $(x^2+1)|P_n (x)\iff P_n (i)=0$. Put $P_n (i)=p_n $. Then $p_1=2i,p_2=0,p_{n+2}=2ip_{n+1}+2p_n $. Iterating given relation, $p_{n+2}=2i(2ip_n+2p_{n-1})+2p_n=4ip_{n-1}-2p_n=4ip_{n-1}-2 (2ip_{n-1}+2p_{n-2})=-4p_{n-2}$. Thus $p_n=-p_{n-4} $. Using the recursion, $p_3=4i,p_4=-8$, hence in the first $4$ values only $p_2=0$. It follows that $p_n=0\iff n\equiv 2\pmod 4$. So our required answer is $n\equiv 2\pmod 4$