How does proof by mathematical induction work?

Mathematical induction is a way of proving statements in maths. The principle is quite similar to dominoes (not pizza, the game) - if you push the first one, the second one will be pushed over, pushing the third one and so on. 

There are 3 stages to induction. The first stage is to prove that the base case, n = 1 is true (essentially the first domino). The second stage involves you assuming the case n = k is true. The final stage involves you using the assumption above to show that the case n = k + 1 is also true (essentially you're showing that if you push the kth domino, the (k + 1)th domino will also be pushed over).

Here is an example of proof by induction being applied:

For any positive integer n, 1 + 2 + 3 + ... + n = n(n + 1)/2.

Let P(n) be the assumption that 1 + 2 + 3 + ... + n = n(n + 1)/2. Consider the base case, n = 1:

Left-hand side = 1. Right-hand side = 1(1 + 1)/2 = 1
As LHS = RHS, P(1) is true.

Assume that P(k) is true i.e. 1 + 2 + 3 + ... + k = k(k + 1)/2. Consider P(k + 1) [remember we have to use P(k) somewhere here]

1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) (using P(k))
Taking a factor of (k + 1) from the RHS:
k(k + 1)/2 + (k + 1) = (k + 1)[k/2 + 1] = (k + 1)(k + 2)/2 = (k + 1)((k + 1) + 1)/2 i.e. P(k + 1) is true.

Therefore, as P(1) is true and P(k) true implies P(k + 1) is true, by the principle of mathematical induction, 1 + 2 + 3 + ... + n = n(n + 1)/2

Shayantan C. A Level Maths tutor, A Level Further Mathematics  tutor,...

2 years ago

Answered by Shayantan, an A Level Further Mathematics tutor with MyTutor

Still stuck? Get one-to-one help from a personally interviewed subject specialist


£20 /hr

Praveenaa K.

Degree: Mathematics (Masters) - Bristol University

Subjects offered:Further Mathematics , Science+ 4 more

Further Mathematics
-Personal Statements-

“Top tutor from the renowned Russell university group, ready to help you improve your grades.”

£26 /hr

Scott R.

Degree: PGCE Secondary Mathematics (Other) - Leeds University

Subjects offered:Further Mathematics , Maths

Further Mathematics

“I am currently completing 2 PGCEs in Leeds. I have always had a passion for maths and my objective is to help as many as possible reach their full potential.”

£20 /hr

John W.

Degree: Mathematics (Masters) - St. Andrews University

Subjects offered:Further Mathematics , Maths

Further Mathematics

“I've done a broad range of maths learning and tutoring over the years, now continuing this on to university I'm sure I'll be able to help you out!”

About the author

Shayantan C.

Currently unavailable: until 09/06/2017

Degree: MMath (Bachelors) - Warwick University

Subjects offered:Further Mathematics , Maths+ 5 more

Further Mathematics
-Personal Statements-

“Hello everyone - the name is Shay, and I'm doing a maths degree at the University of Warwick. I did my A-Levels last year (Maths, Further Maths, Economics, Chemistry and French) and should be able to help with A-Level Maths, Further M...”

You may also like...

Posts by Shayantan

How does proof by mathematical induction work?

What is the difference between competitiveness and contestability?

Other A Level Further Mathematics questions

Given that abc = -37 + 36i; b = -2 + 3i; c = 1 + 2i, what is a?

Prove that 1/(tanx) + tanx = 1/sinxcosx

How do I find the inverse of a 3x3 matrix?

Find the complex number z such that 5iz+3z* +16 = 8i. Give your answer in the form a + bi, where a and b are real numbers.

View A Level Further Mathematics tutors

We use cookies to improve your site experience. By continuing to use this website, we'll assume that you're OK with this. Dismiss