- #31
Deveno
Science Advisor
Gold Member
MHB
- 2,726
- 6
on induction in general:
first you prove it for a base case (start the ball rolling).
then you show that IF it holds for n-1, THEN it also holds for n, and then conclude it holds for all natural numbers greater than the number used in the base case (which is usually n = 0 or n = 1).
here, you need a way to reduce the degree of a polynomial by 1. the easiest way to do this is to use the euclidean (or division algorithm), which says we can write a polynomial
f(x) = (x - a)q(x) + r(x), where 0 ≤ deg(r(x)) < deg(x-a) = 1, so r(x) is a constant polynomial.
so f(x) = (x - a)q(x) + r. this means f(a) = (a - a)q(x) + r = 0q(x) + r = r, so we can write this as:
f(x) = (x - a)q(x) + f(a). in particular, if a is a root of f, so that f(a) = 0,
f(x) = (x - a)q(x), and comparing degrees, we see that deg(q(x)) = deg(f(x)) - 1.
now a one degree polynomial x + c has one root, namely -c. so a one degree polynomial has at most 1 root.
if we assume an n-1 degree polynomial has at most n-1 roots, then we let f(x) be any arbitrary n degree polynomial. if f has no roots at all, it certainly has less than n roots.
otherwise, suppose f has a root a. we can write:
f(x) = (x - a)q(x), where deg(q(x)) = n-1, and by our induction hypothesis, has at most n-1 roots. therefore f has the (at most) n-1 roots of q, and the root a, which is at most n roots.
first you prove it for a base case (start the ball rolling).
then you show that IF it holds for n-1, THEN it also holds for n, and then conclude it holds for all natural numbers greater than the number used in the base case (which is usually n = 0 or n = 1).
here, you need a way to reduce the degree of a polynomial by 1. the easiest way to do this is to use the euclidean (or division algorithm), which says we can write a polynomial
f(x) = (x - a)q(x) + r(x), where 0 ≤ deg(r(x)) < deg(x-a) = 1, so r(x) is a constant polynomial.
so f(x) = (x - a)q(x) + r. this means f(a) = (a - a)q(x) + r = 0q(x) + r = r, so we can write this as:
f(x) = (x - a)q(x) + f(a). in particular, if a is a root of f, so that f(a) = 0,
f(x) = (x - a)q(x), and comparing degrees, we see that deg(q(x)) = deg(f(x)) - 1.
now a one degree polynomial x + c has one root, namely -c. so a one degree polynomial has at most 1 root.
if we assume an n-1 degree polynomial has at most n-1 roots, then we let f(x) be any arbitrary n degree polynomial. if f has no roots at all, it certainly has less than n roots.
otherwise, suppose f has a root a. we can write:
f(x) = (x - a)q(x), where deg(q(x)) = n-1, and by our induction hypothesis, has at most n-1 roots. therefore f has the (at most) n-1 roots of q, and the root a, which is at most n roots.