MHB How Does Nicholson Apply Induction in Theorem 12 Proof?

[Math Amateur]

I am reading W. Keith Nicholson's book: Introduction to Abstract Algebra (Third Edition) ...

I am focused on Section 4.2:Factorization of Polynomials over a Field.

I need some help with the proof of Part 1 of Theorem 12 on page 218

The relevant text from Nicholson's book is as follows:https://www.physicsforums.com/attachments/4596I do not follow how Nicholson is using the Principle of Mathematical Induction in Part (1) of the above proof ... ... indeed I find his proof strategy quite puzzling.

Nicholson seems to me to proceed as follows:

He proves the case for $$n$$ = deg $$f = 1$$ ... well and good ...

Now, according to my understanding of the Principle of Mathematical Induction he should assume (1) is true for deg $$f = n$$ and then prove it true for deg $$f = n + 1$$.

... ... BUT ... Nicholson does not seem to do this ... ?Can someone please explain exactly how Nicholson is using the Principle of Mathematical Induction ...

Help will be appreciated ...

Peter

 

[Fallen Angel]

Hi Peter,

There is a difference between using simple or strong induction.

Suppose we want to prove some property $P$ for all natural numbers.

If we use simple induction then we will do what you expect, assume $P(n)$ is true and then prove $P(n+1)$.

But, if we use strong induction we will assume $P(i)$ true for all $i<n$ and then prove $P(n)$, and that's what Nicholson is doing here.

He assumes that every polynomial of degree $d<n$ has a unique factorization, and then proves that a polynomial of degree $n$ also has a unique factorization.

 

[Math Amateur]

Hi Peter,

There is a difference between using simple or strong induction.

Suppose we want to prove some property $P$ for all natural numbers.

If we use simple induction then we will do what you expect, assume $P(n)$ is true and then prove $P(n+1)$.

But, if we use strong induction we will assume $P(i)$ true for all $i<n$ and then prove $P(n)$, and that's what Nicholson is doing here.

He assumes that every polynomial of degree $d<n$ has a unique factorization, and then proves that a polynomial of degree $n$ also has a unique factorization.

Thanks for the help, Fallen Angel ...

Reflecting on on this now ...

Thanks again,

Peter

 

[Deveno]

This is somewhat off-topic, but "strong" induction and "weak" (regular) induction are actually equivalent.

It is (hopefully) clear that strong induction certainly implies regular induction: if we assume something is true for all:

$n_0 \leq k < n$

then it is certainly true for $k = n-1$ (as long as $n \geq n_0 + 1$, of course).

Of course, it is *not* as clear that weak induction implies strong induction.

Suppose the statement we wish to prove (for all $n \geq n_0$) is $P(n)$. We then consider:

$Q(n) \stackrel{\text{def}}{=} \forall (n_0 < m < n): P(m)$

and apply weak induction to $Q$, proving strong induction for $P$.

This is especially useful in using induction on "divisibility orderings", where it may be hard to get a statement $P(n)$ into the form $P(n-1)$ and "something else" (a tactic that works very well on SUMS, typically), but it is easy to get a statement on FACTORS of $n$.

 

[Math Amateur]

This is somewhat off-topic, but "strong" induction and "weak" (regular) induction are actually equivalent.

It is (hopefully) clear that strong induction certainly implies regular induction: if we assume something is true for all:

$n_0 \leq k < n$

then it is certainly true for $k = n-1$ (as long as $n \geq n_0 + 1$, of course).

Of course, it is *not* as clear that weak induction implies strong induction.

Suppose the statement we wish to prove (for all $n \geq n_0$) is $P(n)$. We then consider:

$Q(n) \stackrel{\text{def}}{=} \forall (n_0 < m < n): P(m)$

and apply weak induction to $Q$, proving strong induction for $P$.

This is especially useful in using induction on "divisibility orderings", where it may be hard to get a statement $P(n)$ into the form $P(n-1)$ and "something else" (a tactic that works very well on SUMS, typically), but it is easy to get a statement on FACTORS of $n$.

Thanks for for the help Deveno ...

Just by the way ... I am so happy to see you back!

Peter