Third Lesson of the Course

Commentary on Chapter 3 of D'Angelo-West Text

30jan11, revised in part 3feb16
\begin{document} \maketitle Caution: This commentary on D'Angelo-West was written for online Netmath students who (1) had to purchase the textbook, and (2), were far less mathematically prepared than the the current students at Illinois. Therefore, it took a very low-level approach, but required careful reading of the text. So, there is a different emphasis here, which will be developed in the lectures. I will write this in blue.

\section{Introduction} Chapter 3 of our textbook is concerned with the \textit{ Induction Axiom of Arithmetic}. It is not an opinion, nor an experimental result that it holds. It is an assumption which every mathematician accepts. Some logicians test its validity by proposing alternatives, or rejecting it. But this is not a logic course. Our purpose here is to understand how to apply this axiom to prove theorems. To understand this commentary without studying the textbook is not advisable. However, you can read the commenatry first, and then the textbook to see what I consider important. To reduce clutter we shall usually forget to mention that we are talking only about numbers in $\mathbb{N}$. In other words, in this context "number" shall mean a member of $\mathbb{N}$. \section{Examples} \subsection{The sum of odd numbers is square} As stated, this is trivially false, for $3+5=8 \ne n^2 $ for any $n$. So we must mean something else. From the picture it is obvious what the theorem says and, perhaps you think it is also obviously true. Question 1. State the theorem correctly in your own words. In that case, you won't mind seeing a rigorous proof. \begin{itemize} \item For $ n=1$, it is the sum of the first odd number and is a square. \item And $ n^2 + (2(n+1) -1) = n^2 + (2n +1 ) = (n+1)^2 \item Done! \end{itemize} Done what? \textbf{This is NOT a proof!} It is a fragment of a proof. Indeed, it is the heart of a proof, but, as it stands, it doesn't even make sense. Question 2. List the chief faults of this "proof". Here is a formal proof: \begin{eqnarray*} \mbox{Let } P(n)& = & (\sum_{k=1}^n (2k-1) = n^2) \\ P(1) & = & (\sum_{k=1}^1 (2k-1) = 2-1 = 1 = 1^2) \mbox{ half done} \\ P(n) & = & (\sum_{k=1}^n (2k-1) = n^2) \mbox{ hypothesis, so use it}\\ \mbox{ Calculate } \sum_{k=1}^{n+1} (2k-1) & = & \sum_{k=1}^{n} (2k-1) + (2n+1) \\ &=& P(n) + (2n+1) = n^2 + 2n+1 + 1 = (n+1)^2\\ \therefore & & P(n+1) \\ \end{eqnarray*} Question 3. Where is the hypothesis used? Now were done, because $P(1)$ holds and $P(n) \implies P(n+1)$ is true. \subsection{Sermon} So what's so difficult here? Some advice on induction problems: \begin{enumerate} \item Recognize the problem as being one amenable to finite induction. \item Analyze the problem and formulate a conjecture (=tentative theorem).. \item Test your conjectur for $n=1,2,3,4$. \item Develop a strategy of proof, and compose one. \item Check your work. What did you leave out? \end{enumerate} Here fit 100 practice problems. Put a couple simple ones into your Journal. As you will notice when looking through the problems given in the D'Angelo-West, they are either uninteresting, like the one above, or very obscure and difficult. For our purposes, you need to know how use the principle of induction, and to uynderstand the difference between simple induction and so-called \textit{strong induction}

Here is an \textbf{Interesting Example 2}:

Consider the number of ways of enumerating (lining up in an order from first to last) a finite set. For example, of 5 people. There are 5 to chose as first, 4 for second, etc . So the answer is $n! = n(n-1)...1 $. The number of ways to select a subset of items is $2^n$. Which is the larger ?

\begin{eqnarray*} n! & \sim & 2^n \\ n=1 \implies 1& = & 1 \\ n=2 \implies 2 & < & 4 \\ n=3 \implies 6 & < & 8 \\ n=4 \implies 24 & > & 16 \\ n=5 \implies 120 & > & 32 \\ \end{eqnarray*} \textbf{Conjecture:} $ (\forall n \ge 4)(n! > 2^n)$.
Let $ P(n)= (n! > 2^n)$.
\textbf{proof by induction}.
$P(1)$ was calculated above.
Consider that $P(n+1) = (n+1)!=(n+1)n! > (n+1)2^n > 2\; 2^n=2^{n+1}. QED

Here is an \textbf{Interesting Example 3} of an incorrect argument:

\textbf{Conjecture:} All people are right handed
The \textit{chirality} of a person is their \textit{handedness}; either right or left. We "prove" the theorem by first proving this
\textbf{Lemma:} All finite sets of people have the same chirality.
\textbf{proof by induction}.
$P(1)$ is obvious.
Now assume $P(n)$ and consider $P(n+1)$. Line them up in a row, and note that the first $n$ people have, by the induction hypothesis, the same chirality. Similarly, the last $n$ people. But clearly these two sets overlap, they have some people in common. Hence all $n+1$ of them have the same chirality.

Since I am right handed, all people are right handed! Where is the error? \subsection{All primes are odd.} Recall that a number divible only by itself and 1 is called a \textit{ prime number}. Aha, you say. 2 is a prime and it is even. So the theorem is false. But every other number after 2 is also even and therefore not prime. So maybe if we ammend the statement we do get a theorem. Question 4. State the correct theorem about odd primes. So, do we really need finite induction here? No, but it is instructive to do so anyway. So what should $P(n)$ read like? Maybe the $n$ counts the primes. So we proceed thus \begin{eqnarray*} \mbox{Label the primes } & & p_1=2, p_2=3, p_3=5, \mbox{ etc } \\ \mbox{Define } P(n) & := & ( n \ge 2 \implies p_n \mbox { is odd } ) \\ P(1) & = & (1 \ge 2 \implies 2 \mbox { is odd }) \\ \mbox{ Since } (1 \ge 2) & &\mbox { is false } \\ \mbox{ and } ( 0 \implies 1) & & \mbox{ is true } \\ \therefore 2 & & \mbox{ is odd } \\ \end{eqnarray*} First of all, the above argument has devolved into nonsense. First of all, is our $P(n)$ really a statement about all primes. Do we know, for example, that there really is a $p_{42}$ in the list? What about $p_{14072079482528}$ ? That index is the national debt as of 11:15:24 pm GMT on 30jan11. Much more interesting than the national debt is a theorem that there are really infinitely many primes. And we follow Euclid to prove this by contradiction. \begin{itemize} \item Suppose there are only finetely many primes. \item Name them $p_1, p_2, ..., p_n $. \item Take their product $ N = p_1 p_2 ... p_n $ \item Add 1 and consider the number $N+1$. \item It is clearly not in the list of all primes. \item And it is not divisible my any of the primes because, if it were, then $ \frac{N + 1}{p_k} = \frac{p_1p_2...p_n}{p_k} + \frac{1}{p_k} $ \item Which is a sum of a whole number plus a proper fraction, and so not whole. \item So it is a composite number, itself the product of primes. \item Hence we arrive at a contradiction. $N+1$ cannot by neither a prime nor not a prime. \item Done \end{itemize} The following is the most important part of this lesson. \section{Fundamental Theorem of Arithmetic a.k.a. Prime Decomposition Theorem} In the previous argument we used the \textit{fundamental theorem of arithmetic}, that every number is either a prime or a product of primes. Curiously, we cannot prove this theorem without induction. In fact, we have to use a seemingly stronger version of the Axiom, called \textit{ Axiom of Strong Induction}. In words, this says that if there is a first natural number for which a proposition $P(n)$ holds, and thereafter, $P(k)$ holds for all numbers between that first and the present one (without gaps !) then $P(n)$ holds for all natural numbers. \textbf{Principle of Strong Induction} \begin{eqnarray*} \mbox{If } (\exists n_0)(n=n_0 &\implies& P(n)) \\ \mbox{and } & & (\forall n > n_0)( n_0 < k < n \implies P(k) ) \\ \mbox{then } (\forall n > n_0)( P(n)) & & \mbox{ holds true. } \\ \end{eqnarray*} \subsection{Proof of the FTA by strong induction} The textbook has several examples of strong indction. But this is the only one you really need to remember forever as a legacy of your having passed MA348. We shall give a conversational proof. You should turn it into a set of steps in your Journal. Obviously, we start with $n_0 = 2$ because $1$ is not a prime, nor a composite. Question 5. Do you detect an error in an earlier statement in this lesson? And, is $2$ a prime or a product of primes? Yes. So now, take a deep breath, we may assume that all numbers from 3 to $n-1$ are either primes or products of primes. How about $n$? If it is a prime, we're done. If it is not a prime, it must be the product of two numbers, neither equal to 1. Explicitly, $ n = ab$ for some numbers less than $n$. We apply the strong induction hypothesis. Both $a$ and $b$ are primes or products of primes. So their product is again a product of primes. Basta! Not so fast. Do both $a$ and $b$ satisfy the hypotheses of the strong induction? Are both of them necessarily bigger than 2 and less than $n$? Mebbe we have to tighten up the argument. Question 6. Fix the gap in the argument above to take care of the case that either or both of $a=2$ and $b=2$. \subsection{Housekeeping} Often, we want to express the prime factorization of a number in an orderly manner, using unique primes, in order: $(\forall n)(\exists m, e_1, e_2, ..., e_m, p_1 < p_2 < ... < p_m \mbox{ primes })( n = p_1^{e_1} p_2^{e_2} .... p_m^{e_m} ) $ \section{Pay Day !} Regardless of how D'Angelo-West prove their theorems, or you might be inclined to solve a problem "as in the book", you \textbf{should} attempt to prove everything using the \textit{ Prime Factorization Theorem}, in either of its formulation. In this course, you should apply the Prime Factorization Theorem (PFT) whenever possible, because this among the central theorems in three of the remaining lessons of the Discrete Math half of the course. Solutions to homework problems that do not do this, but instead copy the methods of some problems in the textbook, will receive only partial credit. \subsection{Another look at Strong Induction} There is a corollary of the PFT which says that the prime factorization is unique up to order. You may amuse yourself by reading D'Angelo-West's proof. It is an elegant application of induction. Finally, you might wonder, is "strong" induction really stronger that just plain garden variety induction? The theorem seems to have a much more demanding hypothesis to check. In a logic course, such as MA414, or from Google, you'll see that the two principles of induction are logically equivalent. So, use one or the other, whichever works. \end{document}