Help me to prove this statement about quadratic equations? (from Gelfand's Algebra). $ x^2+px+q=0 ${p,q are integers; a,b are roots}. Prove $a^n+b^n$(n is any natural number) is an integer.
This is the third part of the problem.I have previously proved that $a^2+b^2$ and $a^3+b^3$ are integers using the binomial theorem and vieta's laws$(a+b=-p, ab=q)$. Using the same approach here,i have:
$a^n+b^n = (a+b)^n-a^{n-1}b-a^{n-2}b^2...-ab^{n-1}$ 
$=(-p)^n-ab(a^{n-2}+a^{n-3}b+...+b^{n-2})$
$=(-p)^n-q((a+b)^{n-2}...))$ 
Here i am stumped.I think that depending on whether n is even or odd the equation reduces to the previous two cases i have already proven.How do i state this formally?
PS: i am an independent learner without much experience with proofs.Please give a concise proof if you can(or a really detailed hint).

It can be proved by induction on $n$, as follows:
From
$x^2 + px + q = 0 \tag{1}$
it follows that the roots $a$, $b$ satisfy
$a + b = -p, \tag{2}$
$ab = q; \tag{3}$
from (2), (3) we have
$p^2 = (a + b)^2 = a^2 + 2ab + b^2 = a^2 + 2q + b^2, \tag{4}$
or
$a^2 + b^2 = p^2 - 2q \in \Bbb Z, \tag{5}$
since $p, q \in \Bbb Z$.  Also, since
$(a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 = a^3 + b^3 + 3ab(a + b), \tag{6}$
it follows that
$a^3 + b^3 = (a + b)^3 - 3ab(a + b) = -p^3 + 3pq \in \Bbb Z. \tag{7}$
Now assume that $m \ge 3$ and that $a^k + b^k \in \Bbb Z$ for $1 \le k \le m$; note we have established the case $m = 3$ in the above.  Then
$a^{m+ 1} + b^{m + 1} = (a + b)(a^m + b^m) - (a^mb + ab^m) = (a + b)(a^m + b^m) - ab(a^{m - 1} + b^{m - 1})$
$= -p(a^m + b^m) - q(a^{m - 1} + b^{m - 1}); \tag{8}$
by hypothesis, $a^m + b^m, a^{m - 1} + b^{m - 1} \in \Bbb Z$; since $p, q \in \Bbb Z$, it follows that $a^{m + 1} + b^{m + 1} \in \Bbb Z$ as well.  This completes the induction and shows that $a^n + b^n \in \Bbb Z$ for all $n \ge 1$.  QED.
