MathematicsChapter 7: Mathematical Induction and Binomial Theorem

Induction On Sums

Classic: 1+2+...+n = n(n+1)/2.

Learning objectives

State the main ideas and notation used in induction on sums.
Apply the rules of induction on sums in a clear, step-by-step solution.
Check signs, conditions, and the final answer for mathematical accuracy.

Definition

Classic: 1+2+...+n = n(n+1)/2. 1^2+...+n^2 = n(n+1)2n+16. Geometric 1+r+...+r^n-1 if the book asks. Pattern: Sk+1 = Sk + next term. Replace S_k by the formula from IH, then factor. Meaning: the algebra is 'add one more piece and it still matches the formula with n=k+1'.

Mathematical form

n = n(n+1)/2. 1²+...+n²

n=k+1

n = n(n+1)/2

Where / symbols

INDUCTION ON SUMS: Classic: 1+2+...+n = n(n+1)/2. 1^2+...+n^2 = n(n+1)(2n+1)/6. Geometric 1+r+...+r^{n-1} if the book asks. Pattern: S_{k+1} = S_k + next term. Replace S_k by the formula from IH, then factor. Meaning: the algebra is 'add one more piece and it still matches the formula with n=k+1'.
1. LINEAR SUM: P(n): sum = n(n+1)/2. IH: k(k+1)/2. Add k+1: [k(k+1)+2(k+1)]/2 = (k+1)(k+2)/2. That is P(k+1).
2. OTHER SUMS: Cubes, odds, 2^{n}-1, whatever the paper gives. Always isolate the extra term. Keep one extra = one line.

Relationship

S_k+1 = S_k + a_k+1

Overview

Add the next term:

Linear Sum

P(n): sum = n(n+1)/2. IH: k(k+1)/2. Add k+1: [k(k+1)+2(k+1)]/2 = (k+1)k+22. That is P(k+1).

Examples Add k+1 · Factor (k+1) · Match formula

Other Sums

Cubes, odds, 2ⁿ-1, whatever the paper gives. Always isolate the extra term. Keep one extra = one line.

Examples Write S_k + extra · Use IH on S_k · Tidy

WHAT — INDUCTION ON SUMS

RULE — 1. LINEAR SUM

P(n): sum = n(n+1)/2. IH: k(k+1)/2. Add k+1: [k(k+1)+2(k+1)]/2 = (k+1)k+22. That is P(k+1).

METHOD — 2. OTHER SUMS

Cubes, odds, 2ⁿ-1, whatever the paper gives. Always isolate the extra term. Keep one extra = one line.

WORKED EXAMPLE

Worked: 1+2+...+n = n(n+1)/2, the step. left for k+1 = k(k+1)/2 + (k+1) = (k+1) [k/2 + 1] = (k+1)k+22 right side of P(k+1)

How to answer a induction on sums question

Identify the given quantities, notation, and required result.
Choose the matching rule and write it before substitution.
Work one algebraic step at a time, keeping brackets and signs clear.
Check restrictions, simplify the result, and verify it where possible.

Worked example

1+2+...+n = n(n+1)/2, the step.
left for k+1 = k(k+1)/2 + (k+1)
= (k+1) [k/2 + 1]
= (k+1)k+22
right side of P(k+1)

In simple words

Do not assume P(k+1). Derive it from P(k) plus the new term.

Key points

S_k+1 = S_k + a_k+1
factor after you add
common denominator
one extra term

Exam preparation

Exam Focus

Quick revision

Revision Zone

Review the key facts, formulas and checks before you move on.