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).
 A: The proof is done by induction:
$$ P(n) \ \ \ \  \ \ \ a^n+b^n \text{ is an integer }$$


*

*Basis steps  first we know that $a+b,a^2+b^2 $ are all integers as you proved, so $P(1),P(2)$ are true. (you can also notice that $a+b=-p$ and $a^2+b^2=p^2-2q$)

*Induction step assume that $P(k)$ is true for all integers $k$ such that $k\leq n$ and let's prove $P(n+1)$. Using the fact the $a,b$ are roots of $x^2+px+q=0$ then $a^2+pa+q=0$ and $b^2+pb+q=0$  a multiplication of this two equations by $a^{n-1},b^{n-1}$ respectively gives us: $$a^{n+1}+pa^n+qa^{n-1}=0\\ b^{n+1}+pb^n+qb^{n-1}=0 $$
hence $a^{n+1}+b^{n+1}=-p(a^n+b^n)-q(a^{n-1}+b^{n-1})$ is an integer using because $a^{n}+b^{n}$ is an integer (From IH $P(n)$ is true) and $a^{n-1}+b^{n-1}$ is an integer  (From IH $P(n-1)$ is true). As a conclution $P(n+1)$ is true and the induction terminates.

A: 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.
