MIT6.042 Notes Induction

Veröffentlicht am   |   in   |  

PART I Definition

The well ordering principle

Every nonempty set of nonnegative integers has a smalleset element

This statement is known as The well ordering principle.Some sorts of obvious.We can use it to prove some propositions.

The template for The well ordering principle proofs

More generally, to prove that “$P(n)$ is True for all $N\in \mathbb N$” using The well ordering principle you can take the following steps:

  • Define the set, $C$,of counterexamples to P being true.Namely, define$$C:=\{n \in \mathbb N \mid P(n) \:is \:false\}$$
  • Use a proof by contradiction and assume that $C$ is nonempty.
  • By the Well Ordering Principle, there will be a smallest element, n, in $ C$.
  • Reach a contradiction (somehow)—often by showing how to use n to find another member of $ C$ that is smaller than n. (This is the open-ended part of the proof task.)
  • Conclude that $ C$ must be empty, that is, no counterexamples exist. QED.

To make it clear,I’ll show you a example.
Consider this:for anny positive integers m and n, the faction $m/n$ can be written in lowest terms.
Suppose to the contrary that there were $m, n \in \mathbb Z^+$ such that the fraction $m/n$ cannot be written in lowest terms.Now let $C$ be the set of positive integers that are numerators of such fractions.Then $m \in C$, so $C$ is nonempty.Therefore by well ordering,there must be a smallest integer, $m_0 \in C$.So by definition of C, there is an integer $n_0 \gt 0$ such that
$$\text{the fraction } \frac {m_0}{n_0}\text{cannot be written in lowest terms}$$
This means that $m_0$ and $n_0$ must have a common factor,$p \gt 1$.But $$\frac {m_0/p}{n_0/p} = \frac {m_0}{n_0},$$
so any way of expressing the left hand in lowest terms will also work for right hand, which implies,$$\text{the fraction} \frac{m_0/p}{n_0/p}$$ cannot be written in lowest terms either.
So by definition of $C$, the numerator,$m_0/p$ is in $C$, but $m_0/p \lt m_0$ which contradicts the fact that m0 is the smallest element of $C$.So the assumption is false,that is , the $C$ is empty and hence there are no such fractions at all.QED.

Ordinary Induction

The Principle of Induction.

  • $P(0)$is true, and

  • $P(n)$ IMPLIES $P(n+1)$ for all nonnegative integers, n,
    then

  • $P(m)$is true for all nonnegative integers, m.

PART II Problems

Try to prove:$$1+r+r^2+r^3+…+r^n=\frac {1-r^{n+1}}{1-r}(r\ne1)\tag{1}$$

First , use the well ordering principle.
Suppose to the contrary,some nonegative integers serve as counterexamples to it.Let’s collect them in a set:$$C:=\{ n\in \mathbb N\mid 1+r+r^2+r^3+…+r^n\ne\frac {1-r^{n+1}}{1-r} \}$$.So by well ordering principle, C has a minimum element, call it $c$.That is , $c$ is the smallest conterexample to the theorem.Since $c$ is the smallest, so for all $n\lt c$the theorem will hold.For $n=0$ the above theorem is true so $c \gt 0$.This means $c-1 \ge 0$,the equation (1) for $c-1$ is true.$$1+r+r^2+r^3+…+r^{c-1}=\frac {1-r^{c}}{1-r}(r\ne1)\tag{2}$$.But when we add $r^c$ to both sides we get $$1+r+r^2+r^3+…+r^{c-1}+r^c=\frac {1-r^{c}}{1-r}+r^c=\frac {1-r^{c+1}}{1-r}(r\ne1)\tag{3}$$Which means equation (1) does hold for $c$.This is a contradiction.So set $C$ is empty,and we’re done.QED

Secondly ,we’ll use the induction method.
First for $n=0$,equation (1) obviously is true.Now,suppose for $n=k$ the equation(1) also holds,which means:$$1+r+r^2+r^3+…+r^k=\frac {1-r^{k+1}}{1-r}(r\ne1)$$is true.
Adding $r^{k+1}$ to both sides we get $$1+r+r^2+r^3+…+r^k +r^{k+1}=\frac {1-r^{k+1}}{1-r}+r^{k+1}=\frac {1-r^{k+2}}{1-r}(r\ne1)$$.Thus,if for $k$ the equation is true, then so for $k+1$.So for every nonegative integers the equation holds.QED