STEP-BY-STEP LESSON · §5.2

Mathematical Induction I: Proving Formulas

Connect the base case and inductive step in a proof of a formula.

How to build an argument: methods and reasons

Before writing: assumptions, goals and established facts (§4.2)

Assumption: a stated hypothesis or an explicitly temporary premise. Identify its domain.
Goal: what remains to be shown. It is not available as a reason for a later step.
Established: a statement derived from hypotheses, definitions, earlier steps or an applicable theorem. Name that reason.
Introduce witnesses when their existence is justified; give different arbitrary quantities different variables. Finish by matching the result to the original goal.

Writing a proof · §4.2

Example: constructing the witness for an odd product

Assumption
$m=2a+1,\ n=2b+1,\quad a,b\in\mathbb Z$
Take arbitrary odd integers m and n.
Reason: Their representations follow from the definition of odd.
Goal
$\exists s\in\mathbb Z:\ mn=2s+1$
This is the goal, not something already known.
Reason: An existential conclusion requires constructing a witness.
Established
$mn=(2a+1)(2b+1)=4ab+2a+2b+1$
Expand before introducing s.
Reason: Substitution and the distributive law.
Established
$s=2ab+a+b\in\mathbb Z,\quad mn=2s+1$
The constructed integer s proves the product odd.
Reason: Closure of integers and the definition of odd; the goal was not assumed.

Direct proof

When to choose: Choose it when definitions turn the hypothesis into usable equations or properties.

For every x in D: P(x) implies Q(x). Given: an arbitrary x in D satisfying P. Goal: Q for that same x.

Start: Introduce the objects and their domains; assume only the stated hypotheses. Expand the relevant definition.

Finish: State Q and explain why arbitrariness gives the universal claim. Never use Q as a premise.

Worked example with reasons

Assumption
$a,b\in\mathbb Z,\quad a>0,\ b>0,\ a\mid b$
Take arbitrary positive integers a and b with a dividing b.
Reason: These are the hypotheses, not conclusions.
Goal
$a\le b$
We must establish this inequality.
Reason: Writing a goal does not establish it.
Established
$b=aq,\quad q\in\mathbb Z$
Introduce an integer q witnessing divisibility.
Reason: Definition of a dividing b; a is nonzero.
Established
$q=\frac ba>0$
The quotient is positive.
Reason: Both b and a are positive; division by a is allowed.
Established
$q\ge1$
A positive integer cannot lie strictly between 0 and 1.
Reason: This uses q being an integer, not positivity alone.
Established
$aq\ge a,\quad b\ge a$
Replace aq by b to obtain the goal.
Reason: Multiplication by a positive a preserves the inequality; b=aq was established above.

Source concepts · approved book access required

PDF 198 · p. 174, PDF 215 · p. 191

Counterexample

When to choose: Use it to refute a universal claim. A failed proof attempt alone does not refute anything.

To refute every x in D satisfying P also satisfies Q, find one x in D with P true and Q false.

Start: Write the exact claim and choose a permitted test object. Verify its hypotheses.

Finish: Show explicitly which conclusion fails; one valid counterexample refutes the universal claim.

Worked example with reasons

Goal
$\forall n\in\mathbb Z\ (n>1\Rightarrow \operatorname{Prime}(n))$
Test the claim that every integer greater than 1 is prime.
Reason: A universal statement can be disproved by one permitted instance.
Established
$n=9,\quad9\in\mathbb Z,\quad9>1$
The chosen value satisfies the domain and hypothesis.
Reason: A counterexample must meet every hypothesis.
Established
$9=3\cdot3,\quad1<3<9$
Nine has a positive divisor other than 1 and itself, so it is not prime.
Reason: Definition of prime. Composite means nonprime only within integers greater than 1.

Source concepts · approved book access required

PDF 185 · p. 161, PDF 198 · p. 174

Proof by cases

When to choose: Choose cases when a definition or remainder changes the calculation. First show the cases cover every allowed object.

Given P, cover all possibilities C₁,…,Cₖ and prove Q in each.

Start: Derive the case split from a definition or theorem; do not merely list convenient examples.

Finish: Conclude Q because every allowed object belongs to a handled case.

Worked example with reasons

Assumption
$n\in\mathbb Z,\quad 2\nmid n$
Let n be an arbitrary odd integer.
Reason: The hypothesis fixes the domain but does not yet provide the required m.
Goal
$n^2=8m+1\quad m\in\mathbb Z$
We need to construct an integer m.
Reason: The conclusion is existential: both the equation and integrality must be shown.
Established
$n=4q+r,\quad q\in\mathbb Z,\quad r\in\{0,1,2,3\}$
Only r=1 or r=3 is possible for odd n.
Reason: Quotient–remainder theorem 4.5.1; residues 0 and 2 make n even. This proves completeness.
Established
$(4q+1)^2=16q^2+8q+1=8(2q^2+q)+1$
Case 1: set m=2q²+q.
Reason: Expand the square and factor 8. Sums and products of integers are integers.
Established
$(4q+3)^2=16q^2+24q+9=8(2q^2+3q+1)+1$
Case 2: set m=2q²+3q+1.
Reason: Expansion, 9=8+1, then factor 8; the constructed m is an integer.
Established
$\exists m\in\mathbb Z:\ n^2=8m+1$
Both possible cases give the required integer; it may depend on the case.
Reason: Exhaustive cases establish the original claim for arbitrary odd n.

Source concepts · approved book access required

PDF 230 · p. 206, PDF 231 · p. 207

Contraposition

When to choose: Use it when negating the conclusion gives a more useful starting definition.

To prove P⇒Q, prove ¬Q⇒¬P. Given ¬Q; goal ¬P.

Start: Write the contrapositive and introduce an arbitrary object satisfying ¬Q.

Finish: Establish ¬P, then invoke equivalence with the original implication.

Worked example with reasons

Goal
$2\mid n^2\Rightarrow 2\mid n$
Prove the statement for every integer n.
Reason: This is Proposition 4.7.4.
Assumption
$2\nmid n$
Instead prove: if n is odd, then n² is odd.
Reason: P⇒Q is equivalent to ¬Q⇒¬P. For integers, not even means odd. We do not assume n² even here.
Established
$n=2k+1,\quad k\in\mathbb Z$
Introduce an integer k.
Reason: Definition of odd.
Established
$n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$
The square is odd.
Reason: Algebra and closure of integers show 2k²+2k is an integer; then use the definition of odd.
Established
$2\mid n^2\Rightarrow 2\mid n$
The original implication follows from the proved contrapositive.
Reason: Logical equivalence of a conditional and its contrapositive.

Source concepts · approved book access required

PDF 246 · p. 222, PDF 247 · p. 223, PDF 248 · p. 224

Contradiction

When to choose: Use it when the negation creates incompatible established facts.

Assume the hypotheses and the negation of the desired conclusion; derive a contradiction.

Start: State exactly what is temporarily assumed for contradiction.

Finish: Name the conflicting statements and discharge the assumption.

Worked example with reasons

Goal
$2\mid n^2\Rightarrow 2\mid n$
Prove the statement for every integer n.
Reason: This is Proposition 4.7.4.
Assumption
$2\mid n^2,\quad 2\nmid n$
Assume a counterexample: n² is even but n is not even.
Reason: Negating the universal conditional gives one integer satisfying the hypothesis and negating the conclusion. Every integer is either even or odd.
Established
$n=2k+1,\quad k\in\mathbb Z$
Introduce an integer k.
Reason: Definition of odd.
Established
$n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$
The square is odd.
Reason: Algebra and closure of integers show 2k²+2k is an integer; then use the definition of odd.
Established
$2\mid n^2\ \land\ 2\nmid n^2$
This is impossible; the assumed counterexample cannot exist.
Reason: No integer is both even and odd (Theorem 4.7.2). Discharging the contradictory assumption proves the original claim.

Source concepts · approved book access required

PDF 246 · p. 222, PDF 247 · p. 223, PDF 248 · p. 224

Mathematical induction

When to choose: Use it for a claim indexed by every integer n from a starting value, when the next case relates to the previous one.

Prove P(n₀). For arbitrary k≥n₀, assume P(k) and derive P(k+1).

Start: State the indexed property and starting value; check the base without using the induction hypothesis.

Finish: Invoke induction only after both the base and the implication are established.

Worked example with reasons

Goal
$1+3+\cdots+(2n-1)=n^2,\quad n\ge1$
Prove the sum formula for every positive integer n.
Reason: The domain and indexed property specify what induction must cover.
Established
$n=1:\quad1=1^2$
The first case holds.
Reason: Direct evaluation establishes the base.
Assumption
$1+3+\cdots+(2k-1)=k^2,\quad k\ge1$
Fix an arbitrary integer k and assume only its case.
Reason: This temporary induction hypothesis is permitted to prove the implication P(k)⇒P(k+1).
Established
$1+3+\cdots+(2k-1)+(2k+1)=k^2+2k+1$
Separate the next term and replace the old sum by k².
Reason: This is the exact point where the induction hypothesis is used.
Established
$k^2+2k+1=(k+1)^2$
This is the required case k+1.
Reason: Algebra proves the implication. The base and induction principle now give all integers n≥1.

Source concepts · approved book access required

PDF 304 · p. 280

Negating quantified statements

When to choose: Use it to identify precisely what would make a quantified claim false, especially before a counterexample or contradiction.

Negate one outer quantifier at a time, preserving variable order, domains and the scope of the predicate.

Start: Mark the scope of each quantifier; move the negation inward one rule at a time.

Finish: Read the final statement and check that it describes failure of the original claim. Equivalence does not by itself prove either statement true.

Worked example with reasons

Goal
$\neg\forall x\in D\ \exists y\in E\ P(x,y)$
Rewrite the negation without changing its meaning.
Reason: The domains D and E remain fixed throughout.
Established
$\exists x\in D\ \neg\exists y\in E\ P(x,y)$
There is an x for which the inner existential statement fails.
Reason: Negation of a universal quantifier: ¬∀x R(x) ⇔ ∃x ¬R(x).
Established
$\exists x\in D\ \forall y\in E\ \neg P(x,y)$
For that same x, every y fails P.
Reason: Negation of an existential quantifier: ¬∃y P(x,y) ⇔ ∀y ¬P(x,y). The order ∃x∀y is preserved.

Source concepts · approved book access required

PDF 164 · p. 140

Theorem, proposition, lemma and corollary

Theorem / proposition

Both are statements established by proof. The name often signals how a text organizes or emphasizes a result, not a different degree of truth.

Lemma

A proved auxiliary result used in another argument. For example, −|r|≤r≤|r| for real r supports later bounds. If r≥0, |r|=r and −r≤r; if r<0, |r|=−r and r≤−r. These cases cover every real r.

Lemma 4.5.4, printed p. 207 / PDF 231

Corollary

A result derived from an established theorem. If r is rational, r+r is rational by closure of rational numbers under addition (Theorem 4.3.2); because 2r=r+r, its double is rational.

Example 4.3.4, printed p. 187 / PDF 211; printed box: Corollary 4.2.3

Keep the domain conditions

With Epp’s definition, d divides 0 for every nonzero integer d: 0=d·0. Do not omit d≠0.

Prime and composite classifications here concern integers n>1. “Not prime” alone does not make 0, 1 or a negative integer composite.

Before you begin

Direct Proof and Counterexample I: Introduction

Integer n is even iff there is an integer k with n=2k. Evenness gives this representation, and the representation gives evenness.

n even ↔ ∃k∈ℤ: n=2k

For “every odd integer has an odd square”, testing 3,5,7 suggests a pattern but leaves infinitely many cases. Write an arbitrary odd integer as 2k+1 with integer k; no special value is assumed.

n=2k+1; k∈ℤ

Symbols

P(n): statement about integer n
k→k+1: step to the next index

Definitions and notation for this topic

Mathematical induction

To establish P(n) for all integers n≥n₀, prove P(n₀), then prove P(k)→P(k+1) for an arbitrary integer k≥n₀.

The base starts the argument and the arbitrary step propagates it. A displayed P(k)→P(k+1) alone omits the base and is not a complete induction proof.

Separate glossary example

For n≥1, 1+…+n=n(n+1)/2. Base n=1: 1=1. If the formula holds at k, add k+1 to get (k+1)(k+2)/2.

P(1); for every k≥1, P(k)⇒P(k+1).

Open glossary card

Step by step

Step 1 / 6

State the property

P(n) must be a specific statement for every integer n in the stated range.

P(n): 1+2+…+n = n(n+1)/2, n≥1

First fix the same property for every index.

Worked example

Complete the inductive step for 1+…+n.

Assume 1+…+k=k(k+1)/2. The next case adds k+1 on the left.
Replace only the old sum: 1+…+k+(k+1)=k(k+1)/2+(k+1).
Factor out k+1: (k+1)(k/2+1)=(k+1)(k+2)/2, the required next-case formula.

Read the sum, then prove the step

In a sum, the index visits every integer from the lower bound through the upper bound. ∑ adds terms; ∏ multiplies them. An induction proof requires a base case and a general implication P(k)→P(k+1). The induction hypothesis may replace the old part through k, not the entire unproved next case.

Worked example

Prove for every integer n≥1: ∑ from i=1 through n of (2i+1) = n(n+2).

Read the first case before starting the induction.
```
n=1: ∑_{i=1}^{1}(2i+1)=3=1(1+2)
```
Why: The first term is 3 because the index starts at 1. The base case is now established directly.
Fix an arbitrary integer k≥1 and assume the formula through k.
```
∑_{i=1}^{k}(2i+1)=k(k+2)
```
Why: This is a temporary assumption inside the conditional step, not an assumption that every case is already true.
Separate the next sum into its old part and its one new term.
```
∑_{i=1}^{k+1}(2i+1)=∑_{i=1}^{k}(2i+1)+[2(k+1)+1]
```
Why: The new term uses the same rule at i=k+1. All earlier terms remain unchanged.
Replace only the old sum, then simplify.
```
k(k+2)+(2k+3)=k²+4k+3=(k+1)(k+3)
```
Why: The first replacement uses the induction hypothesis. The factorization yields exactly (k+1)((k+1)+2), the required formula at k+1.
Combine the base and the general implication.
```
P(1) ∧ ∀k∈ℤ (k≥1 → (P(k)→P(k+1)))
```
Why: The base starts the chain, and the proved implication reaches each subsequent integer case. Therefore the formula holds for every integer n≥1.

Self-review goal: Identify the index bounds, the old sum, the new term and the exact target at k+1. Explain where the hypothesis was used and why checking three numerical cases alone would not prove the formula.

Induction can extend a product

For a product through k+1, separate the old product through k and multiply by the new factor. Unlike a sum, the new part is not added. Verify that every denominator and cancelled factor is nonzero.

Worked example

Prove ∏_{i=1}^{n}((i+1)/i) = n+1 for integers n≥1.

Verify the base n=1.
```
2/1=2=1+1
```
Why: Only the i=1 factor occurs in the first product.
Assume the product identity for arbitrary k≥1.
```
∏_{i=1}^{k}((i+1)/i)=k+1
```
Why: This is the hypothesis for the old product only.
Separate the last factor and use the hypothesis.
```
∏_{i=1}^{k+1}((i+1)/i)=[∏_{i=1}^{k}((i+1)/i)]·(k+2)/(k+1)=(k+1)·(k+2)/(k+1)
```
Why: The extra index is k+1, so its factor is (k+2)/(k+1).
Cancel and close the induction.
```
(k+1)·(k+2)/(k+1)=k+2
```
Why: Since k+1>0, cancellation is valid. k+2 is precisely the claimed right side at n=k+1. Base and step prove the identity for all n≥1.

Try it yourself

Prove ∏_{i=1}^{n}(i/(i+1))=1/(n+1), for n≥1, by stating the base and the new factor.

Show worked answer

Check the base and assume the old product.
```
n=1: 1/2; ∏_{i=1}^{k}(i/(i+1))=1/(k+1)
```
Why: The base matches 1/(1+1); the hypothesis is used only in the next step.
Multiply by the new factor.
```
[1/(k+1)]·[(k+1)/(k+2)]=1/(k+2)
```
Why: All denominators are positive for k≥1. This is the required next case, and the base completes the induction.

Apply a geometric sum with its actual bounds

A finite geometric sum has a constant ratio between successive terms. For a real r≠0,1 and integer n≥0, let S=1+r+…+rⁿ. Multiplying by r shifts the same terms one place; subtraction cancels the middle terms. For r=1 the sum is simply n+1. For r=0 the displayed terms are 1+0+…+0, so the sum is 1, without needing a convention for 0⁰. A formula application does not require a new induction proof unless the question asks for one.

Worked example

Derive the sum formula and use it to compute 1−2+4−8+16.

Write the original and shifted sum.
```
S=1+r+…+rⁿ; rS=r+r²+…+r^{n+1}
```
Why: Both sums have n+1 terms. At n=0 these are just S=1 and rS=r.
Subtract the second equality from the first.
```
(1−r)S=1−r^{n+1}
```
Why: Every intermediate power occurs once with each sign. Only the first term and the shifted final term remain.
Divide by the nonzero factor and substitute.
```
S=(1−r^{n+1})/(1−r); r=−2,n=4 ⇒ S=(1−(−2)⁵)/3=11
```
Why: The ratio is −2, and the powers run from 0 to 4: there are five terms. The denominator 1−r is 3, not zero.

Try it yourself

Evaluate ∑_{i=1}^{4}3ⁱ using the geometric formula. Explain how you handle the lower bound 1.

Show worked answer

Factor out the first power and reindex.
```
∑_{i=1}^{4}3ⁱ=3∑_{j=0}^{3}3ʲ
```
Why: The four original terms become 3 times 1,3,9,27.
Use the formula with upper index 3.
```
3(1−3⁴)/(1−3)=3·40=120
```
Why: Using upper index 4 without changing the lower bound would add the wrong number of terms.

Optional self-check

Which term is added when extending a sum of squares through k to one through k+1?

Show answer

(k+1)²: the upper index changes, while each term is still a square.

Source / textbook · approved access required

Open source: printed p. 275 · PDF 299