MTH1020 · Analysis of Change
Induction & Functions
Week 2 of Monash MTH1020 Analysis of Change pairs the principle of mathematical induction with the formal theory of functions. It covers summation and product (Σ/Π) notation and telescoping sums, the base-case-plus-induction-step template for proving statements about all natural numbers, and the classification of functions as injective, surjective or bijective, along with even/odd/periodic symmetry, composition and inverses. Mid-semester Test 1 is sat in the Week-2 applied class, so this material is examined almost immediately, and induction proofs must be written to the Monash communication standard.
What this chapter covers
- 01Summation Σ and product Π notation; dummy index; telescoping sums via 1/(n(n+1)) = 1/n − 1/(n+1)
- 02The principle of mathematical induction: base case P(1), induction step P(k) ⇒ P(k+1)
- 03Canonical induction results: Σ(2i−1) = n², Σ1/(j(j+1)) = n/(n+1), n³−n divisible by 3, 11ⁿ−1 divisible by 10
- 04Functions f : A → B: domain, co-domain, image, range; the vertical line test and natural domain
- 05Injective (one-to-one), surjective (onto) and bijective functions; the horizontal line test
- 06Even (f(−x) = f(x)), odd (f(−x) = −f(x)) and periodic (f(x+T) = f(x)) functions
- 07Composition (g ∘ f)(x) = g(f(x)); order matters; range of f must sit in domain of g
- 08Inverse functions: only bijections invert; f⁻¹(f(x)) = x; graph reflected in y = x; f⁻¹(x) ≠ 1/f(x)
Proof by induction: the sum of the first n odd numbers
- +1State the proposition and the base case. Let P(n) be the statement Σ from i = 1 to n of (2i − 1) = n². Base case P(1): the left side is 2(1) − 1 = 1 and the right side is 1² = 1, so P(1) is true.
- +1State the induction hypothesis. Assume P(k) holds for some natural number k, that is, 1 + 3 + … + (2k − 1) = k². This is what we are allowed to use.
- +1Prove the induction step P(k) ⇒ P(k+1). Add the next odd term, 2(k+1) − 1 = 2k + 1, to both sides: 1 + 3 + … + (2k − 1) + (2k + 1) = k² + (2k + 1) = k² + 2k + 1.
- +1Recognise the perfect square and conclude. k² + 2k + 1 = (k + 1)², which is exactly P(k+1). Since P(1) is true and P(k) ⇒ P(k+1) for every k, by the principle of mathematical induction P(n) is true for all natural numbers n. □
Key terms
- Mathematical induction
- A proof method for statements P(n) about all natural n: prove the base case P(1), then prove the induction step P(k) ⇒ P(k+1). Both together give P(n) for all n (the domino principle).
- Induction hypothesis
- The assumption that P(k) holds for a particular k, made in order to prove P(k+1). It is the only thing you may assume in the induction step.
- Telescoping sum
- A sum whose terms cancel in pairs, e.g. Σ 1/(i(i+1)) = Σ (1/i − 1/(i+1)) = 1 − 1/(n+1) = n/(n+1).
- Injective (one-to-one)
- A function with f(a) = f(b) ⇒ a = b; its graph meets every horizontal line at most once. Distinct inputs give distinct outputs.
- Surjective (onto)
- A function whose range equals its co-domain: every element of the co-domain is hit. Its graph meets every horizontal line at least once.
- Bijective
- A function that is both injective and surjective — its graph meets every horizontal line exactly once. Only bijections have inverse functions.
Induction & Functions FAQ
Why isn't checking lots of cases the same as a proof by induction?
Checking n = 1, 2, 3, … only verifies finitely many cases, but a 'for all natural n' statement has infinitely many. Induction closes that gap: the induction step proves that truth at any k forces truth at k+1, so once the base case starts the chain, every natural number follows like falling dominoes. That single implication does the work of infinitely many checks.
How do I tell if a function is injective, surjective or bijective?
Injective means no two inputs share an output — algebraically f(a) = f(b) ⇒ a = b, graphically every horizontal line is met at most once. Surjective means the range fills the whole co-domain — every horizontal line is met at least once. Bijective is both at once, so every horizontal line is met exactly once, and only then does an inverse exist. Restricting the domain or co-domain can turn a non-bijection into one (for example x² on [0, ∞)).
Is f⁻¹(x) the same as 1/f(x)?
No — this is a classic MTH1020 trap. f⁻¹ is the inverse function, which undoes f (so f⁻¹(f(x)) = x), whereas 1/f(x) is the reciprocal. Only bijective functions have an inverse, and you find it by writing y = f(x) and solving for x in terms of y; the graph of y = f⁻¹(x) is the reflection of y = f(x) in the line y = x.
Can Sia check my induction proofs?
Sia can walk through the structure of an induction proof with you — confirming your base case, that your induction hypothesis is stated correctly, and that the induction step genuinely uses it — and it can re-explain why a telescoping sum collapses. It explains the method and checks your reasoning step by step on your own practice questions; it does not complete graded assessment for you, and Monash academic-integrity rules apply.
Exam move
Because MST1 is sat in the Week-2 applied class, get induction fluent fast: rehearse the four canonical results (Σ(2i−1) = n², Σ1/(j(j+1)) = n/(n+1), n³−n divisible by 3, 11ⁿ−1 divisible by 10) until you can write the base case, hypothesis and step from memory in full sentences. For functions, practise deciding injective/surjective/bijective both algebraically and with the horizontal line test, and drill composition order and inverse-finding (write y = f(x), solve for x). Keep a note of the two classic traps — assuming what you are proving in the induction step, and confusing f⁻¹ with 1/f. When a step won't click, ask Sia to re-explain that line a different way and set you a fresh induction target in the same style.
Working through Induction & Functions in MTH1020? Sia is AskSia’s AI Mathematics tutor — ask any MTH1020 Induction & Functions question and get a clear, step-by-step explanation grounded in how MTH1020 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
