NTIC Review of Previous Ideas

Section 1.2 Review of Previous Ideas

Before going further, we need a bit of review. The following three topics may be considered prerequisites for the course.

🔗

Subsection 1.2.1 Well-Ordering

🔗

The first principle is both simple and deep. It is an axiom of the positive integers, but we give it its usual name.

🔗

Axiom 1.2.1. Well-Ordering Principle.

Any nonempty set of positive integers has a least/smallest element.

🔗

This principle actually holds with any subset of

$\mathbb{Z}$ which is bounded below, such as

$\mathbb{N}$ (recall Definition 1.0.1).

🔗

Let's use it as an example to prove the following fact which you probably didn't know required proof.

🔗

Fact 1.2.2. Consecutive Integers.

There are no integers between 0 and 1.

🔗

Proof.

This proof proceeds by contradiction. Assume there are some such integers, and let

\begin{equation*} S=\{x\in\mathbb{Z}\mid 0<x<1\}\text{.} \end{equation*}

This set must then have a least element $a\text{,}$ and $0<a<1\text{.}$ If we multiply through by $a$ (which is positive) then we obtain $0<a^2<a\text{.}$

Thus $a^2$ is another integer such that $0<a^2<1\text{,}$ so $a\in S\text{,}$ but we also know that $a^2<a\text{.}$ So $a^2$ is an element of $S$ which is less than the least element of $S\text{.}$ That is a contradiction, so our original assumption was wrong and there are no such integers (i.e. $S$ is empty).

🔗

Remark 1.2.3.

To review, proofs by contradiction and contrapositive both start by assuming the negation of the conclusion. A proof by contrapositive uses that assumption to prove the negation of the original assumption. A proof by contradiction, on the other hand, leads to some absurdity, but not necessarily just negating the original assumptions. In the proof above of Fact 1.2.2, the contradiction is that you can't have two different smallest elements of a set.

🔗

Subsection 1.2.2 Induction

🔗

Sometimes we need a way to prove a statement for all integers

$n$ after a certain point, for instance integers greater than or equal to

$n=1\text{.}$ This is usually called proof by induction. Usually there are two steps in a typical ‘simple’ induction.

First we prove the “base case” (often $n=1$ or $n=0$ ).
Then we prove the “induction step”, that the case $n=k$ implies case $n=k+1\text{.}$

🔗

These combine to prove a fact for all cases

$n\geq 1\text{.}$

🔗

Example 1.2.4. Archetype for Induction.

We shall show that

$\begin{equation*} \sum_{i=1}^n i=\frac{n(n+1)}{2} \end{equation*}$

Solution

The base case is to check that $1=\frac{1(1+1)}{2}\text{,}$ which is easy.

The induction step begins with the assumption that

\begin{equation*} \sum_{i=1}^k i=\frac{k(k+1)}{2} \end{equation*}

and then proceeds by showing that the formula is still true when $k$ is replaced with $k+1\text{.}$ For this proof, to add just one more integer $k+1$ to the sum means

\begin{equation*} \sum_{i=1}^{k+1} i=\sum_{i=1}^k i+(k+1) \end{equation*}

(which we can see by rewriting the sum). Then we can just plug in the induction assumption to obtain

\begin{equation*} \sum_{i=1}^k i+(k+1)=\frac{k(k+1)}{2}+(k+1)=(k+1)\left(\frac{k}{2}+1\right)=\frac{(k+1)(k+2)}{2} \end{equation*}

which is exactly what is required to finish the induction step, namely

\begin{equation*} \sum_{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2}\text{.} \end{equation*}

🔗

We could use well-ordering (Axiom 1.2.1) to prove that the induction proof technique works, but will not do so here.

🔗

Subsection 1.2.3 Divisibility

🔗

Definition 1.2.5.

If an integer $n$ can be written as a product $kd=n$ of two integers $k$ and $d\text{,}$ then we say that $d$ divides $n\text{,}$ or that $n$ is divisible by $d\text{,}$ or that $d$ is a divisor of $n\text{.}$ We write $d\mid n$ to denote that $d$ divides $n\text{.}$

🔗

Example 1.2.6.

Divisibility is familiar.

For instance, the concept that $n$ is even is just the same thing as $2\mid n\text{.}$
The divisors of 8 are … $\pm 1, \pm 2, \pm 4, \pm 8\text{.}$ (Don't forget negative divisors.)
Very often we can write this generically, so for example $n\mid x+1$ means that $x+1$ can be written as the product of $n$ and some other integer $m\text{.}$

🔗

There are lots of interesting things to say about divisibility. Let's prove a somewhat unexpected statement using induction and just what we already know.

🔗

Example 1.2.7.

Show that $4\mid 5^n-1$ for $n\geq 0\text{.}$

Solution

This proof will proceed by induction. This time the base case will be $n=0\text{.}$ We'll try to make the steps clear with separate bullets.

Base step: If $n=0$ the formula says that 4 divides $5^0-1=1-1=0\text{,}$ which is definitely true.
Induction step:
- Suppose $4\mid 5^k-1\text{.}$ Then, by Definition 1.2.5, $5^k-1=4x$ for some integer $x\text{.}$
- Hence $5^k=1+4x$ is a fact we could use later.
- Our goal in this step is to show $4\mid 5^{k+1}-1\text{.}$
- Since we need something true about $5^{k+1}-1\text{,}$ let's consider $5^{k+1}$ first. The key observation will be that $5^{k+1}=5^k\cdot 5\text{.}$
- Using the fact we obtained from the induction assumption we can write this as $5^k\cdot 5=(1+4x)\cdot 5\text{;}$ this means that
  
  \begin{equation*} 5^{k+1}-1=5(1+4x)-1=20x+4. \end{equation*}
- Certainly $20x+4$ is divisible by 4.
- Thus we have shown that $4\mid 5^{k+1}-1\text{,}$ so we have finished the induction step, and our proof by induction is complete.

🔗

There are lots of other propositions about divisibility you are probably familiar with from previous courses. Here is a sampler.

🔗

Proposition 1.2.8. Divisibility Facts.

If $a\mid b$ and $b\mid c$ then $a\mid c\text{.}$
If $a\mid b$ then $ca\mid cb\text{.}$
If $c\mid a$ and $c\mid b$ then $c\mid au+bv$ for any integers $u,v\text{.}$
If $n>0$ then all divisors of $n$ are less than or equal to $n\text{.}$

🔗

These are not hard to prove (see Exercise 1.4.1). For instance, the second one can be proved by simply noting

$b=ka$ for some

$k\in\mathbb{Z}\text{,}$ so that

$cb=c(ka)=c(ak)=(ca)k\text{.}$ The others are similar, and are good practice with using basic algebraic manipulation in proofs.