2. Direct proof, contradiction and induction

Let $P(n)$ be a statement about integers $n\ge n_0$, where $n_0$ is fixed. The principle of mathematical induction says:

1. Prove the base case $P(n_0)$.
2. For an arbitrary integer $k\ge n_0$, assume $P(k)$ and prove $P(k+1)$.
3. Conclude that $P(n)$ holds for every integer $n\ge n_0$.

The assumption in step 2 is the induction hypothesis. It is conditional, not an assumption that the final theorem is already true. The base starts the chain, and the implication extends any valid link to the next.

Here is a justification using the least-element property of the nonnegative integers. If a counterexample existed, there would be a least counterexample $m\ge n_0$. It could not be $n_0$ because of the base case. Then $m-1\ge n_0$ would not be a counterexample, and the induction step would force $P(m)$, a contradiction.

For an arbitrary integer starting index $n_0$, applying the least-element property to the shifted indices $m-n_0\ge0$ justifies the preceding least-counterexample step.

Conversely, ordinary induction on the positive integers implies the least-element property. Suppose a nonempty set $S\subseteq\{1,2,3,\ldots\}$ has no least element. Let $P(n)$ assert that none of $1,\ldots,n$ belongs to $S$. If $1\in S$ it is the least element, so $P(1)$ holds. If $P(k)$ holds but $k+1\in S$, then $k+1$ is the least element of $S$, a contradiction. Thus $P(k)\Rightarrow P(k+1)$. Induction gives $P(n)$ for every positive integer $n$, so $S$ is empty, contradicting its assumed nonemptiness. Hence every nonempty set of positive integers has a least element. Translating indices by $n\mapsto n-n_0+1$ gives the corresponding induction version for any integer starting index $n_0$.

Learning goals

Write direct, contrapositive and contradiction proofs; prove existence and uniqueness separately; use induction and least-counterexample arguments. A proof explains why every allowed instance follows from definitions and established facts. Checking many instances may suggest a theorem but never replaces that universal argument.

Proof architecture

To prove $P\Rightarrow Q$ directly, assume $P$ and derive $Q$. To use the contrapositive, assume $\neg Q$ and derive $\neg P$. To argue by contradiction, assume the premises together with the negation of the desired conclusion and obtain an impossibility. The contradiction must arise from the declared assumptions, not from an unrelated false statement.

For an existence claim $\exists x\ P(x)$, constructing an explicit witness is often strongest. To establish a unique object, first show at least one exists, then assume two candidates satisfy its defining conditions and prove they agree. An equation that every candidate must satisfy proves necessity, not existence, until a candidate is substituted back.

Worked example: parity. If an integer $n$ is odd, write $n=2k+1$. Then $n^2=4k^2+4k+1=2(2k^2+2k)+1$ is odd. Taking the contrapositive proves that an integer with even square must itself be even. We did not assume that every integer has a square root in $\mathbb Z$.

Theorem: induction from well-ordering

Let $P(n)$ be a predicate on integers $n\ge n_0$. If $P(n_0)$ is true and $P(n)\Rightarrow P(n+1)$ for every $n\ge n_0$, then $P(n)$ holds for all such integers.

Proof. Suppose the set of failing indices is nonempty. The well-ordering property gives its least member $m$. It cannot equal $n_0$ because the base case holds, so $m-1\ge n_0$. Minimality gives $P(m-1)$, and the induction implication gives $P(m)$, contradicting failure. Hence the failing set is empty.

Strong induction replaces the assumption $P(n)$ in the step by all cases from $n_0$ through $n$. The same least-counterexample proof justifies it. It is useful when a construction uses several smaller inputs rather than only the immediately preceding one.

Worked examples

A finite sum. Prove $1+3+\cdots+(2n-1)=n^2$ for $n\ge1$. At $n=1$, both sides are one. Assuming the formula at $n$, adding the next term $2n+1$ gives $n^2+2n+1=(n+1)^2$, which is the required next case. The step uses the existing formula, not the desired next equality as an assumption.

Existence and uniqueness of a linear solution. For real $a\ne0,b$, the equation $ax+b=0$ has exactly one solution. The value $x=-b/a$ exists and substitution verifies it. If $x,y$ are solutions, subtraction gives $a(x-y)=0$, hence $x=y$. If $a=0$, there are either no solutions ($b\ne0$) or infinitely many ($b=0$), showing the hypothesis is necessary.

Graded practice

1. Foundation. Prove that the sum of two odd integers is even by definitions.
2. Core. Prove by induction that $\sum_{k=1}^n k=n(n+1)/2$ for $n\ge1$.
3. Core. Prove that $2^n\ge n+1$ for integers $n\ge0$, identifying where the base case enters.
4. Proof. Prove by strong induction that every integer $n\ge2$ is a product of primes. Do not claim uniqueness of the factorization from this proof.

Full solutions

1. If the integers are $2r+1$ and $2s+1$, their sum is $2(r+s+1)$, twice an integer and hence even.
2. At $n=1$, $1=1\cdot2/2$. If the formula holds at $n$, the next sum is $n(n+1)/2+(n+1)=(n+1)(n+2)/2$. Induction gives the result for every $n\ge1$.
3. At $n=0$, $1=0+1$. If $2^n\ge n+1$, then $2^{n+1}\ge2(n+1)\ge n+2$, since $n\ge0$. Thus the implication holds and the true base starts the chain. The implication alone would not establish any particular case.
4. At $n=2$, the number itself is prime. Suppose all integers from $2$ to $n-1$ have the property. If $n$ is prime, it is a one-factor product. Otherwise $n=ab$ for integers $2\le a,b<n$. By the hypothesis both factors are products of primes, and concatenating their factorizations gives one for $n$. This establishes existence only; uniqueness requires an additional divisibility argument.

Summary and term definitions

A witness realizes existence; uniqueness rules out distinct candidates. An induction hypothesis is the conditional assumption used only inside the step. A least counterexample is the smallest failing integer under well-ordering. Write the goal before choosing a method. Base cases, exceptional parameters and the difference between necessary and sufficient conditions belong to the argument, not to optional commentary.