How does proof by mathematical induction work?

MYTUTOR SUBJECT ANSWERS

Answers / Further Mathematics / A Level / How does proof by mathematical induction work?

768 views

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

145 SUBJECT SPECIALISTS

Sophie H. A Level Maths tutor, GCSE Maths tutor

View profile

£24 /hr

Sophie H.

Degree: Mathematics (Masters) - Bristol University

Subjects offered:Further Mathematics , Maths

“I’ll help anyone finding maths hard. I still struggle now, it's not meant to be easy! Be at my tutorial or (c^2-a^2) <- a maths joke, I apologise.”

5.0

33 reviews | 70 completed tutorials

Save profile

Pankaj K. A Level Physics tutor, GCSE Physics tutor, A Level Maths tu...

View profile

£20 /hr

Pankaj K.

Degree: Physics (Bachelors) - Kings, London University

Subjects offered:Further Mathematics , Physics+ 1 more

“Positive, Dedicated, Motivating, Calm, Patient, Understanding, Professional, Organised, Experienced, Focused, Enthusiastic, Passionate”

MyTutor guarantee

| 1 completed tutorial

Save profile

Joe C. A Level Maths tutor, GCSE Maths tutor

View profile

£30 /hr

Joe C.

Degree: Mathematics (Bachelors) - Bristol University

Subjects offered:Further Mathematics , Maths

“Hi, I'm Joe, an experienced tutor and a University of Bristol graduate with a first class Degree in Mathematics.”

5.0

87 reviews | 181 completed tutorials

Save profile

See more A Level Further Mathematics tutors

About the author

View profile

£22 /hr

Shayantan C.

Degree: MMath (Bachelors) - Warwick University

Subjects offered:Further Mathematics , Maths+ 5 more

“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...”

5.0

1 review | 4 completed tutorials

Save profile

Version:	3.49.9
Build:	5f485a18d000
Time:	2017-09-20T16:11:15Z

MYTUTOR SUBJECT ANSWERS

How does proof by mathematical induction work?

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

145 SUBJECT SPECIALISTS

About the author

You may also like...

Posts by Shayantan

Other A Level Further Mathematics questions

One-to-one help is at your fingertips