Induction, sums and inequalities: VCE Specialist Mathematics Units 3 & 4

1. Why induction proves an infinite family

A statement P(n) may depend on an integer index n: a sum formula, a divisibility claim or an inequality. Mathematical induction proves P(n) for every integer n from a specified starting value n₀. It needs two logically different ingredients. First, establish P(n₀) directly. Second, prove that whenever P(k) is true for an arbitrary integer k ≥ n₀, P(k + 1) must also be true. The first ingredient starts the argument; the second carries it forward without an upper limit.

The inductive assumption is conditional. You are not claiming the entire theorem is already true. You temporarily assume just P(k) and use that assumption to derive the next case. The implication P(k) ⇒ P(k + 1) is proved for arbitrary k. Starting from the independently verified base case, repeated use establishes every later integer case. A step that jumps from k to k + 2 would leave every second case uncovered unless another starting case were supplied.

Both pieces are indispensable. A correct base case with no step proves only one case. A valid step without a true base case proves only that truth would propagate if it ever began. The range also matters. If the first true case is n = 4, do not conclude the result holds for every positive integer. State “for every integer n ≥ 4” at the start and at the end.

2. Read a partial sum or product precisely

The notation Σ_r=1ⁿ a_r means a₁ + a₂ + ⋯ + a_n. The index r runs through the terms; n determines where the finite sum stops. To move from n = k to n = k + 1, keep the first k terms and add a_k+1. Do not add a_k again. Writing the new final term explicitly is often the most important line in a sum proof.

Similarly, Π_r=1ⁿ b_r means b₁b₂⋯b_n. The next product is the old product multiplied by b_k+1. State any values that would make a denominator zero. Factorials are an example: (k + 1)! = (k + 1)k!, because factorial notation denotes a finite product. It does not distribute over addition.

When searching for a formula, compute several exact terms and look for structure. A table might suggest a quadratic expression for a sum or a rational expression for a product. This is conjecture formation, not proof. Once a candidate F(n) is found, the induction step often reduces to checking that F(k) + a_k+1 = F(k + 1), or its product counterpart. These identities explain why the formula matches the recurrence.

3. Telescoping explains cancellation directly

A telescoping sum has terms that cancel after each summand is expressed as a difference. For example, 1/[(r + 1)(r + 2)] = 1/(r + 1) − 1/(r + 2). This identity follows by putting the two fractions over a common denominator. Summing from r = 1 to n leaves 1/2 − 1/(n + 2), because every middle reciprocal appears once positively and once negatively.

The endpoints depend on the exact starting and finishing indices. Write the first two terms and the final term before cancelling. A change in lower limit changes the surviving first contribution. Telescoping is a direct proof for arbitrary n; induction can verify the same identity through its recurrence. If a question specifies induction, presenting only cancellation does not meet the requested method.

Products can telescope too. In Π_r=1ⁿ(r + 2)/(r + 1), factors 3 through n + 1 cancel, leaving (n + 2)/2. Cancellation here removes common nonzero factors in a product. It does not license cancelling separate terms across an addition sign. Expanding several factors makes the structure and the nonzero condition visible.

4. Use an algorithm to investigate, then prove

A finite loop can compare a recurrence with a candidate closed form. Here a running total tests the arithmetic-sum identity from the first example. The total is initialised once, and the loop adds exactly one new term on each pass. Equality is checked with integer arithmetic, avoiding a false mismatch caused by decimal rounding. The output records the first failed case if one is found.

INPUT positive integer N
S ← 0
FOR n FROM 1 TO N
    S ← S + 4 × n − 1
    IF S ≠ n × (2 × n + 1) THEN
        OUTPUT n, S, "counterexample"
        STOP
    END IF
END FOR
OUTPUT "No counterexample among the tested cases"

The assignment arrows, indented selection and inclusive counting loop follow the VCAA pseudocode conventions. FROM 1 TO N includes both endpoints. STOP means exit the entire algorithm, so the final message is reached only after every requested case passes.

The loop is useful for checking a conjecture or finding an implementation error. It is not an induction proof because it stops at N. To trace it, record n, the newly added term, S and the proposed formula. After the first three passes, S is 3, 10 and 21. If S were reset to zero inside the loop, the program would test individual terms instead of partial sums. Algorithm design therefore requires the same attention to quantities and indices as the proof.

When technology is allowed, a symbolic system can simplify the difference between the derived k + 1 expression and the target. A zero result checks an algebraic identity, but the mathematical write-up must still state the inductive assumption and explain why it applies. For inequalities, a system may need assumptions such as k ≥ 0; omitting them can make a correct comparison undecidable or invalid over a larger domain.

5. Avoid the three most common gaps

First, verify the base case numerically on both sides. “Clearly true” can hide a wrong starting index. Second, state the hypothesis for k, rather than writing the whole theorem for all n as an assumption. Third, end the step with the expression required at k + 1. A page of algebra that stops one line early may not show the necessary connection.

For a divisibility claim, show the final multiplier is an integer. For an inequality, name the sign condition that preserves or reverses its direction. For a product, include the new factor rather than a new summand. If a conjecture fails at one permitted value, stop trying to prove it and revise the statement. A valid counterexample is decisive even when a thousand earlier tests succeeded.