Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section1.2Review of Previous Ideas

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

Subsection1.2.1Well-Ordering

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

This principle actually holds with any subset of \(\mathbb{Z}\) which is bounded below, such as \(\mathbb{N}\).

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

Proof

To review, proofs by contradiction and contrapositive both start by assuming the negation of the conclusion. A proof by contrapositive uses that to prove the negation of the original assumption, while a proof by contradiction can negate any other true fact or lead to some other absurdity; in this case, you can't have two different smallest elements of a set.

Subsection1.2.2Induction

Sometimes we need a way to prove a statement for all integers \(n\) after a certain point, for instance greater than or equal to \(n=1\). This is usually called proof by induction. There are (usually) 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\).

These combine to prove a fact for all cases \(n\geq 1\).

Example1.2.3Archetype for Induction

We shall show that \begin{equation*}\sum_{i=1}^n i=\frac{n(n+1)}{2}\end{equation*}

Solution

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

Subsection1.2.3Divisibility

Definition1.2.4

If an integer \(n\) can be written as a product \(kd=n\) of two integers \(k\) and \(d\), then we say that \(d\) divides \(n\), or that \(n\) is divisible by \(d\), or that \(d\) is a divisor of \(n\). We write \(d\mid n\) for this concept.

Examples:

  • For instance, \(n\) even is just the same thing as \(2\mid n\).

  • The divisors of 8 are … \(\pm 1, 2, 4, 8\)! (Don't forget negative divisors.)

  • Very often we can write this generically, so that \(n\mid x+1\) means that \(x+1\) can be written as the product of \(n\) and some other integer \(m\).

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

Example1.2.5

Show that \(4\mid 5^n-1\) for \(n\geq 0\).

Solution

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

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}\), so that \(cb=c(ka)=c(ak)=(ca)k\). The others are similar, and are good practice with such manipulation.