Solução:

Para $n = 1$, temos que $x^1 + y^1$ é divisível por $x + y$ pois são iguais.

Para $n \geq 3$ ímpar, faremos indução supondo que vale para $n - 2$. Temos então:

$$\begin{eqnarray*} x^n+y^n &=& x^2(x^{n-2} + y^{n-2}) + y^n - x^2y^{n-2}\\ &=& x^2(x^{n-2}+y^{n-2}) + y^{n-2}(y^2 - x^2). \end{eqnarray*}$$

Podemos escrever $y^2 - x^2 = (y+x)(y-x)$, o que mostra que o segundo termo é divisível por $x + y$. E o primeiro termo é divisível por $x + y$ por hipótese de indução. Logo, a soma é divisível por $x + y$, que é o que desejávamos.