Help me to prove this statement about quadratic equations? (from Gelfand's Algebra).

Question

$ 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).

Answer 1

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.

Answer 2

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.