HL · Proof & systems 1 · Proof by induction: sums of series

Module 11 of 46Lesson 1 of 6 · HL · Proof & systems 1 · Proof by induction: sums of series

Proof by induction, contradiction & counterexample; systems of linear equations · Essential understanding 1

Proof by induction: sums of series

IB AA AHL 1.15with Prof. Kitso

💻 Using the TI-Nspire CX Student Software on a laptop

The screens in these notes are drawn exactly as the Student Software shows them. The keypad on the left of the software works like the handheld — click its keys with the mouse.
menu: click menu on the on-screen keypad (or Documents Toolbox ▸ 🔧). The menu numbers and letters are the same as in these notes.
enter = Enter · tab = Tab (next box) · esc = Esc · del = Backspace.
Powers: type ^ (Shift+6), the power, then press → to come back down before typing more. x² = ^2 then →.
Fraction: type / · √: type sqrt( · π: type pi · eˣ: type exp( · store: type :=. For EE (×10ⁿ) and i, click them on the keypad.
New page: Ctrl+I (or the Insert menu) · change page: Ctrl+← / Ctrl+→ · graph entry line: Ctrl+G · var: Ctrl+L.
Radian / Degree: click Settings in the status bar at the bottom of the window. The mode (RAD or DEG) shows in the top bar.
IB exam mode (Press-to-Test): everything in these notes works on the non-CAS TI-Nspire with the IB exam settings. In exam mode there are no dot-product, cross-product, unit-vector or eigenvalue keys and no Diff Eq graphs — the notes show the allowed way (type the components, use polyRoots on the characteristic equation, do Euler steps on a Calculator page).
If you type nDeriv(, the software shows it as centralDiff( — it is the same command.

The big idea: Mathematical induction proves a statement for every positive whole number without checking them one by one. You show it is true for the first number, then show that if it works for one number it must work for the next. Like a line of dominoes, the whole line then falls.

By the end of this lesson you can:

explain why induction works and write the four-part structure in the right order
prove a formula for a sum $\sum_{r=1}^{n}$ by induction
write the base case, the assumption, the step to $k+1$ and the concluding sentence correctly
use a proved formula in a “hence” question

🧑🏾 Imagine this…

A very long line of dominoes. You want to be sure every domino falls.

You only need two facts. (1) The first domino falls (push it).
(2) If any one domino falls, it knocks over the next one.

You do not need to test the 1000th domino. Facts (1) and (2) already guarantee it falls. Induction is exactly this, with a maths statement instead of a domino.

Statement

P(n)

the claim you want to prove, written with

n

in it, e.g. “the sum of the first

n

odd numbers is

n^2

”.

Base case

check that the statement is true for the first value of

n

(usually

n=1

Inductive hypothesis

the assumption “suppose

P(k)

is true for some positive integer

k

”. It is the only thing you may use in the step.

Inductive step

using the assumption, show that

P(k+1)

is true.

\sum_{r=1}^{n}

“add up the terms for

r=1, 2, \dots, n

”. The last term is the

n

th term.

Conclusion

one sentence that gathers the base case and the step and says the result holds for all

n \in \mathbb{Z}^+

★ The four-part structure (use it every time)

1. Base case. Show $P(1)$ is true: work out the left side and the right side and show they are equal.
2. Assume. Write: “Assume $P(k)$ is true for some $k \in \mathbb{Z}^+$ ”, and write what that says.
3. Step. Write down what you need to show for $n=k+1$ (the target). Then start from the left side of $P(k+1)$ , use the assumption, and tidy until it matches the target.
4. Conclude. “ $P(1)$ is true, and if $P(k)$ is true then $P(k+1)$ is true. So $P(n)$ is true for all $n \in \mathbb{Z}^+$ by mathematical induction”

★ The trick for sums

To go from $k$ terms to $k+1$ terms you add one more term: $\displaystyle\sum_{r=1}^{k+1} f(r) = \sum_{r=1}^{k} f(r) + f(k+1)$ .
Replace the first part by the assumed formula, then factorise (take out the common factor) rather than expanding everything. Always keep the target $P(k+1)$ in view.

⚠️ Mistakes that lose marks

Never write “assume true for $n=k+1$ ”. You may assume $n=k$ only. Showing $k+1$ is the job of the step.
Do not start with the answer and work both sides until they “match”. Start from the left side of $P(k+1)$ and finish at the right side.
The final sentence is worth a mark. It must mention the base case and the step, and say “for all $n \in \mathbb{Z}^+$ ”.

💡 Command terms

Prove / show that / use mathematical induction: the method is compulsory and every line of working earns marks. Hence: you must use the result you have just proved, not start again.

🧪 Try it yourselfPut the proof in order

Quick checks on the structure, before you write your own proofs.

Worked examples

Example 1.1The sum of the first n odd numbers

Prove by induction that

\displaystyle\sum_{r=1}^{n}(2r-1) = n^2

for all

n \in \mathbb{Z}^+

🧠 Think it through

Odd numbers: 1, 3, 5, … The $r$ th term is $2r-1$ . The claim is “1 + 3 + … + (2n − 1) = n²”.
Base case first, then assume for $k$ , then add the $(k+1)$ th term, which is $2(k+1)-1$ .

✍️ By hand
Base case : LHS ; RHS . So  is true. (M1)
Assume  is true for some : . (M1)
Step (): target is .
 (M1)
 (A1)
Conclude.  is true, and if  is true then  is true. So  is true for all  by mathematical induction. (R1)

✅ Answer Proved. The structure (base case, assume

k

, show

k+1

, conclude) is what the marks are for.

Check with numbers first if you like: 1 + 3 + 5 + 7 = 16 = 4². Checking is not a proof, but it tells you the formula is sensible.

Example 1.2A sum with a product inside

Prove by induction that

\displaystyle\sum_{r=1}^{n} r(r+1) = \dfrac{n(n+1)(n+2)}{3}

for

n \in \mathbb{Z}^+

🧠 Think it through

The next term to add is $(k+1)(k+2)$ .
After adding, both pieces share the factor $(k+1)(k+2)$ . Take it out instead of expanding.

✍️ By hand
Base case : LHS ; RHS . True. (M1)
Assume true for : . (M1)
Target for : .
 (M1)
 (A1)
Conclude.  is true, and if  is true then  is true. So  is true for all  by mathematical induction. (R1)

✅ Answer Proved.

Spot the pattern: the target is the formula with every

n

replaced by

k+1

. Write it down before you start the step and you will always know where you are heading.

Example 1.3A fraction sum

Prove by induction that

\displaystyle\sum_{r=1}^{n}\dfrac{1}{r(r+1)}=\dfrac{n}{n+1}

for

n \in \mathbb{Z}^+

🧠 Think it through

The next term is $\dfrac{1}{(k+1)(k+2)}$ . You need a common denominator $(k+1)(k+2)$ .
The top turns into $k(k+2)+1=(k+1)^2$ , which cancels one $(k+1)$ .

✍️ By hand
Base case : LHS ; RHS . True. (M1)
Assume . (M1)   Target: .
 (M1)
 (A1)
Conclude.  is true, and if  is true then  is true. So  is true for all  by mathematical induction. (R1)

✅ Answer Proved.

Why the formula is believable:

\dfrac{1}{r(r+1)}=\dfrac1r-\dfrac1{r+1}

, so most terms cancel (a “telescoping” sum). Induction still gets the full marks if the question says “use induction”.

Example 1.4A sum with powers of 2

Prove by induction that

\displaystyle\sum_{r=1}^{n} r\cdot 2^{r-1}=(n-1)2^{n}+1

for

n \in \mathbb{Z}^+

🧠 Think it through

Check the start: $n=1$ gives one term, $1\cdot2^0=1$ .
The new term is $(k+1)2^{k}$ . Both parts contain $2^k$ : collect them.

✍️ By hand
Base case : LHS ; RHS . True. (M1)
Assume . (M1)   Target: .
 (M1)
 (A1)
Conclude.  is true, and if  is true then  is true. So  is true for all  by mathematical induction. (R1)

✅ Answer Proved.

Because

2^k\cdot 2=2^{k+1}

, the final tidy-up is just a power law. This is the same step you used in the Exponents & logs unit.

Example 1.5Sum of cubes, then “hence”

(a) Prove by induction that

\displaystyle\sum_{r=1}^{n} r^3=\left[\dfrac{n(n+1)}{2}\right]^2

for

n\in\mathbb{Z}^+

.
(b) Hence find

11^3+12^3+\dots+20^3

🧠 Think it through

Part (a): the new term is $(k+1)^3$ . Take out the common factor $(k+1)^2$ .
Part (b): “hence” means use (a). The sum from 11 to 20 is (sum to 20) − (sum to 10).

✍️ By hand
(a) Base case : LHS ; RHS . True. (M1)
Assume . (M1)   Target: .
 (M1)
 (A1)
Conclude.  is true, and if  is true then  is true. So  is true for all  by mathematical induction. (R1)
(b) 

🔢 On your TI-Nspire CX II

Check part (b) on the Calculator page: sum the cubes directly with the seq template.

✅ Answer (a) Proved. (b) 41 075.

Paper 2 tip: after any “hence” answer, the GDC can confirm it in one line. The GDC check is not a substitute for the proof.

Challenge questions

⭐ Challenge 1.6Factorials in a sumPaper 1 style

Prove by induction that

\displaystyle\sum_{r=1}^{n} r\cdot r! = (n+1)!-1

for all

n\in\mathbb{Z}^+

✏️ Try it on paper and on your calculator first. Then check.

Show the full solution

🧠 Think it through

Base case: $1\cdot1!=1$ and $2!-1=1$ .
In the step you will need $(k+1)!=(k+1)\,k!$ and $(k+2)!=(k+2)(k+1)!$ .
After adding $(k+1)(k+1)!$ , factorise $(k+1)!$ .

✍️ By hand
Base case : LHS ; RHS . True.
Assume . Target: .
.
Conclude with the standard sentence.

✅ Answer Proved (check:

1+4+18=23=4!-1

⭐ Challenge 1.7Spot the pattern, then prove itPaper 3 style

Let

S_n=\dfrac{1}{1\cdot3}+\dfrac{1}{3\cdot5}+\dots+\dfrac{1}{(2n-1)(2n+1)}

(a) Find $S_1, S_2, S_3, S_4$ as fractions.
(b) Write down a conjecture for $S_n$ in terms of $n$ .
(c) Prove your conjecture by induction.
(d) Hence find the exact value of $\dfrac{1}{21\cdot23}+\dfrac{1}{23\cdot25}+\dots+\dfrac{1}{39\cdot41}$ , and say what $S_n$ approaches as $n$ grows large.

✏️ Try it on paper and on your calculator first. Then check.

Show the full solution

🧠 Think it through

Work out the first four values and look at numerators and denominators: $\dfrac{1}{3}$ , $\dfrac{2}{5}$ , $\dfrac{3}{7}$ , $\dfrac{4}{9}$ .
Conjecture, then prove. The step needs $(2k+1)(2k+3)$ as the common denominator.
Part (d): the required sum is $S_{20}-S_{10}$ (terms 11 to 20).

✍️ By hand
(a) .
(b) Conjecture: .
(c) Base case :  and . True. Assume . Target: .
.
Conclude with the standard sentence.
(d) Terms 11 to 20 .
As  grows, .

🔢 On your TI-Nspire CX II

Check with the GDC: list the first terms, and the part (d) value.

✅ Answer (a)

\dfrac{1}{3}

\dfrac{2}{5}

\dfrac{3}{7}

\dfrac{4}{9}

. (b)

S_n=\dfrac{n}{2n+1}

. (c) Proved. (d)

\dfrac{10}{861}

;

S_n\to\dfrac12

The route pattern → conjecture → proof is the heart of Paper 3. The data finds the formula; induction is what makes it certain.

Next: Lesson 2 · Induction: divisibility, inequalities, derivatives & sequences

IB DP Mathematics: Analysis and Approaches (AA) — SL and HL HL · Proof & systems 1 · Proof by induction: sums of series

IB DP Mathematics: Analysis and Approaches (AA) — SL and HL

Proof by induction: sums of series

Worked examples

Challenge questions