TOPIC 2 / 2

Induction, Bijections & Countability

Useful preparation: Direct, Contrapositive & Contradiction Proofs

For a long equation, swipe sideways inside its formula box to see every term.

Meaning & notation

Induction turns one verified starting point and a reusable transition into infinitely many conclusions. Bijections compare sets by pairing their elements without omission or duplication. Both methods replace an impossible infinite checklist with a finite rule whose correctness can be proved for arbitrary inputs.

Induction: For integers $\displaystyle n \ge n_{0}$ , prove $\displaystyle P\, \left(n_{0}\right)$ , then prove $\displaystyle P\, \left(k\right) \Rightarrow P\, \left(k + 1\right)$ for every $\displaystyle k \ge n_{0}$ . Strong induction may assume all cases from $\displaystyle n_{0}$ through k.
Injection, surjection, and bijection: An injection never identifies different inputs. A surjection reaches every element of its specified codomain. A bijection has both properties and therefore has an inverse function.
Countability: Use N={1,2,3,…}. A set is countably infinite if it admits a bijection with N; here “countable” includes finite sets as well.

Conditions before calculation

The base cases must cover the range actually needed by the transition. A recurrence using two preceding terms normally needs two starting values.
The inductive assumption concerns earlier cases only. The next case must be derived, not introduced as an additional assumption.
Every map needs a domain, codomain, and well-defined rule. Changing the codomain can change surjectivity without changing the formula.

Why the method works

1. Expose the next contribution

For a sum, separate the new term before using the induction hypothesis. This identifies the exact connection between successive cases rather than merely recognizing a pattern.

2. Prove both mapping properties

For injectivity, equate two outputs and derive equal inputs. For surjectivity, begin with an arbitrary target and construct an allowed preimage.

f(a)=f(b)\Rightarrow a=b,\qquad\forall y\in B\ \exists x\in A:\ f(x)=y

3. Compare infinite sets by a rule

An infinite proper subset can pair perfectly with its parent set. Listing initial values suggests the pairing, but an inverse formula proves that every target is reached exactly once.

Worked examples

EXAMPLE 1

Prove that the sum of the first n terms 2,5,8,… equals $\displaystyle \frac{n\, \left(3\, n + 1\right)}{2}$ for $\displaystyle n \ge 1$ .

At $\displaystyle n = 1$ , the formula gives 2, matching the first term.
Assume the formula at arbitrary $\displaystyle k \ge 1$ . The next term is $\displaystyle 3\, \left(k + 1\right) - 1 = 3\, k + 2$ .
Add that term and factor; this is the formula with k replaced by $\displaystyle k + 1$ .
$\frac{k(3k+1)}2+3k+2=\frac{3k^2+7k+4}2=\frac{(k+1)(3k+4)}2$

Conclusion: The base and transition prove the identity for every positive integer n.

EXAMPLE 2

Construct a bijection from N onto the integers Z.

Send odd input $\displaystyle 2\, k - 1$ to $\displaystyle k - 1$ and even input 2k to −k, for positive integer k.
$f(2k-1)=k-1,\qquad f(2k)=-k$
Odd inputs give distinct nonnegative integers; even inputs give distinct negative integers. The two output ranges cannot overlap.
For target $\displaystyle t \ge 0$ , choose input $\displaystyle 2\, t + 1$ . For target $\displaystyle t < 0$ , choose input −2t. These are positive integers with the required outputs.

Conclusion: The rule is injective and surjective, so Z is countably infinite.

Pitfalls & counterexamples

Tempting claim: Checking several initial cases completes an induction proof.

Correction: Initial cases do not provide a transition for arbitrary k.

Test the claim: The claim $\displaystyle n^{2} \le 100$ holds for $\displaystyle n = 1$ through 10 but fails at $\displaystyle n = 11$ .

Check your understanding

Is $\displaystyle f\, \left(x\right) = x^{2}$ from R to [0, $\displaystyle \infty$ ) a bijection?

Write a reason before opening the explanation. This reflection is not graded or saved.

Compare your reasoning

It is surjective but not injective.

Every nonnegative y has preimage $\displaystyle \sqrt{y}$ , but 2 and −2 both map to 4.

Connect this idea

Induction formalizes recursive constructions. Bijections justify equal-size cosets and provide a precise foundation for comparing finite and infinite collections.

Practise this topic →Review concept flashcards

Reference reading

Use these texts to study the underlying definitions and theorems in greater depth. The explanations and examples above are written for Numerive.