3. Zadatak

Kvadriranjem izraza $p+q=5$ dobivamo $p^2+q^2+2pq=25$. Zbog $p^2+q^2=9$ slijedi da je $pq=8$.

Pokažimo sada tvrdnju matematičkom indukcijom. Baza indukcije zadovoljena je za $n=1$ i $n=2$.

Za pretpostavku indukcije pretpostavimo sljedeće: postoji prirodan broj $N\geq2$ takav da je $p^n+q^n$ neparan cijeli broj za sve prirodne brojeve $n\in\{1,2,\ldots,N\}$. Za korak indukcije koristimo identitet

$$p^{N+1}+q^{N+1}=(p+q)(p^N+q^N)-pq(p^{N-1}+q^{N-1}).$$

Zbog $pq=8$ (i pretpostavke indukcije) znamo da je $pq(p^{N-1}+q^{N-1})$ paran cijeli broj, a zbog pretpostavke indukcije znamo da je $(p+q)(p^N+q^N)$ neparan cijeli broj.

Sada zaključujemo da je i $p^{N+1}+q^{N+1}$ neparan cijeli broj, čime je dokazana tvrdnja indukcije, a time i tvrdnja zadatka.