Proving Formulas and Divisibility by Mathematical Induction

Welcome back. In the previous lesson, proof by contradiction worked by assuming the negation of a claim and deriving an impossibility. Mathematical induction has a different purpose: it proves an entire infinite family of statements, indexed by integers, by establishing a valid starting point and a rule that carries truth from any case to the next.

By the end of this lesson, you will be able to write a complete induction proof for both a summation formula and a divisibility statement, while clearly distinguishing the base case, inductive hypothesis, and inductive step.

---

From one case to infinitely many

Suppose $P(n)$ is a statement about an integer $n$, and we want to prove it for every integer $n\ge a$. The principle of mathematical induction says that this follows if we establish two facts:

1. Base case: $P(a)$ is true.
2. Inductive step: for every integer $k\ge a$, if $P(k)$ is true, then $P(k+1)$ is true.

Symbolically, the structure is:

$$P(a),\forall k\ge a[P(k)⟹P(k+1)].$$

Then $P(n)$ is true for all integers $n\ge a$.

The usual domino image captures the intuition. The base case makes the first domino fall; the inductive step proves that every fallen domino causes the next one to fall. But the logical content is more precise than the metaphor. From the base case, the inductive step gives $P(a+1)$. Applying the same step with $k=a+1$ gives $P(a+2)$, and so on. Any particular integer $n\ge a$ is reached after finitely many such applications.

The inductive hypothesis is the temporary assumption $P(k)$, where $k$ is arbitrary subject to $k\ge a$. It is not an assumption that $P(n)$ holds for every $n$; rather, it is the hypothesis of the conditional statement that you are proving:

$$P(k)⟹P(k+1).$$

A useful formal perspective is to define the set

$$T=\{n\in \mathbb{Z}:n\ge a\text{ and }P(n)\text{ is true}\}.$$

The base case says that $a\in T$. The inductive step says that whenever $k\in T$, then $k+1\in T$. The induction principle guarantees that $T$ contains every integer beginning at $a$.

Both parts matter. A statement can satisfy the implication $P(k)⟹P(k+1)$ merely because $P(k)$ is always false; without a genuine base case, no chain ever begins.

---

Anatomy of a sound induction proof

Before doing any algebra, state exactly what $P(n)$ means. For a claimed formula, $P(n)$ is the equality at a particular value of $n$, not the whole universal statement at once.

A reliable proof template is:

Proof. Let $P(n)$ be the statement [write the desired formula or divisibility claim with $n$].

Base case. Verify $P(a)$ directly.

Inductive step. Let $k\ge a$ be arbitrary. Assume $P(k)$ is true. This is the inductive hypothesis. Using it, prove $P(k+1)$.

Therefore, by mathematical induction, $P(n)$ is true for all integers $n\ge a$. $\square$

For a formula involving a sum, the central observation is usually that the $(k+1)$-st sum consists of the first $k$ terms plus one new term. For divisibility, the central task is usually to rewrite the expression at $k+1$ so that the expression from the inductive hypothesis appears inside it.

The following diagram makes the “one new term” idea concrete.

---

A formula proof: the sum of the first odd numbers

We will prove that for every integer $n\ge 1$,

$$1+3+5+\cdots +(2n-1)=n^2.$$

The diagram suggests why the formula should be true: after adding the first $n$ odd-numbered layers, we have built an $n$-by-$n$ square. Induction turns that visual pattern into a proof.

Let $P(n)$ be the statement

$$1+3+5+\cdots +(2n-1)=n^2.$$

Base case. When $n=1$, the statement is

$$1=1^2,$$

which is true.

Inductive step. Let $k\ge 1$, and assume $P(k)$. Thus,

$$1+3+5+\cdots +(2k-1)=k^2.$$

We must prove $P(k+1)$, namely,

$$1+3+5+\cdots +(2k-1)+(2(k+1)-1)=(k+1{)}^2.$$

Start from the left-hand side of this desired equality. The inductive hypothesis applies to the sum through $2k-1$:

$$\begin{array}{rl}1+3+5+\cdots +(2k-1)+(2(k+1)-1)& =k^2+2k+1\\ & =(k+1{)}^2.\end{array}$$

Therefore $P(k+1)$ is true. By mathematical induction,

$$1+3+5+\cdots +(2n-1)=n^2$$

for every integer $n\ge 1$. $\square$

The proof has a characteristic rhythm:

• identify the extra term when passing from $k$ to $k+1$;
• replace the earlier portion using the inductive hypothesis;
• simplify until the required $(k+1)$-formula appears.

The hypothesis is not decorative. The key move was replacing the long partial sum with $k^2$. If that substitution never occurs, the proof has probably not actually used induction.

---

A divisibility proof: preserving a factor

Now consider a statement with no visible sum:

$$4\mid (5^n-1)\text{for every integer }n\ge 1.$$

Here, $4\mid (5^n-1)$ means that there is an integer $m$ such that

$$5^n-1=4m.$$

That definition is what makes the induction work.

Let $P(n)$ be the statement that $4\mid (5^n-1)$.

Base case. For $n=1$,

$$5^1-1=4.$$

Since $4\mid 4$, $P(1)$ is true.

Inductive step. Let $k\ge 1$, and assume $P(k)$. By the definition of divisibility, there exists an integer $m$ such that

$$5^k-1=4m.$$

We need to prove that $4\mid (5^{k+1}-1)$. The useful algebraic rewrite is

$$5^{k+1}-1=5(5^k-1)+4.$$

The factor $5^k-1$ has appeared, so we can now use the inductive hypothesis:

$$\begin{array}{rl}{5}^{k+1}-1& =5(5^k-1)+4\\ & =5(4m)+4\\ & =4(5m+1).\end{array}$$

Since $5m+1$ is an integer,

$$4\mid (5^{k+1}-1).$$

Thus $P(k+1)$ is true. By mathematical induction,

$$4\mid (5^n-1)$$

for every integer $n\ge 1$. $\square$

Notice that the integer $m$ need not be the same for every exponent $k$. The inductive hypothesis says only that for the arbitrary current value $k$, some integer $m$ exists. That is all the proof needs.

---

How to make the inductive step work

The hardest part of an induction proof is normally not the base case. It is finding a representation of the $(k+1)$-st claim that exposes the $k$-th claim.

For the odd-number formula, the structural identity was

$$\sum _{j=1}^{k+1}(2j-1)=\sum _{j=1}^k(2j-1)+(2k+1).$$

For the divisibility proof, the key identity was

$$5^{k+1}-1=5(5^k-1)+4.$$

In each case, the expression controlled by $P(k)$ appears as a visible component of the next case.

When you approach a new induction problem, use this workflow:

1. Specify the domain and first index.
   If the statement claims validity for $n\ge 5$, then the base case is $P(5)$, not automatically $P(1)$.

2. Write $P(k)$ and $P(k+1)$ separately.
   This often reveals what changes: one extra summand, one additional factor, a larger polygon, or a new recursive term.

3. State the inductive hypothesis in full.
   Do not merely write “assume true.” Write the actual equality or divisibility condition you may use.

4. Begin with the part of $P(k+1)$ that is structurally connected to $P(k)$.
   For sums, this is usually the left-hand side. For divisibility, it is often an algebraic rearrangement of the target.

5. Finish with exactly the desired conclusion.
   In a divisibility proof, explicitly display the target as $d$ times an integer. In a formula proof, simplify to the right side required by $P(k+1)$.

Several common errors are worth actively avoiding:

Error	Why it fails	Repair
Checking several numerical cases and stopping	Any finite list can miss a later failure.	Prove the general conditional $P(k)⟹P(k+1)$.
Assuming $P(n)$ for all $n$	That is the theorem you are trying to prove.	Assume only $P(k)$ for an arbitrary $k$ in the inductive step.
Proving only one particular step, such as $P(10)⟹P(11)$	This gives no mechanism for all later cases.	Keep $k$ arbitrary.
Omitting the base case	The forward rule has no established starting point.	Verify the first index in the stated domain.
Claiming divisibility without producing an integer factor	“Looks divisible” is not a proof.	End with $E=dq$ and state that $q\in \mathbb{Z}$.

Induction is therefore not a substitute for reasoning. It is a framework that concentrates the reasoning into one reusable transition: from an arbitrary valid case to the next valid case.

---

Key takeaways

Mathematical induction proves a statement $P(n)$ for every integer $n\ge a$ by establishing:

$$P(a)$$

and

$$\forall k\ge a[P(k)⟹P(k+1)].$$

For a summation formula, compare the first $k+1$ terms with the first $k$ terms and add the new term. For a divisibility statement, rewrite the $(k+1)$-st expression until the divisible expression from the hypothesis appears, then exhibit the required factor.

The inductive hypothesis is a local, conditional assumption about an arbitrary $k$; it is not permission to assume the whole theorem. A valid proof requires both a genuine base case and a complete, general inductive step.

Next, you will complete this proof-methods module by proving that a function is bijective, separating the two tasks of injectivity and surjectivity.