MYTUTOR SUBJECT ANSWERS

62 views

How do I use proof by induction?

Induction is an incredibly powerful form of proof. As such, it is essential to be able to call upon such a tool if you want to study any higher form of mathematics.

The basic structure of the method is as follows:

1. Show that the claim is true for a base case (usually n=0 or n=1, but it will work for higher numbers)

2. Assume that the claim holds true for some arbitrary value (we usually call this the n=kth case)

3. Prove that, given step 2, it holds true for the n=k+1th case

The idea of this is that if it is true for n=1, and you’ve shown that if it is true for n=some number then it is true for n=that number +1, then it must be true for n=2. If it is true for n=2, then it must be true for n=3 ==> true for n=4 ==> true for n=5 ==>… etc

Let’s work through an example: Show that the sum of the first n squares is equal to n(n+1)(2n+1)/6

1. Let n=1. The sum of the first n squares= the sum of the first 1 square=12=1. Now note that (1)(1+1)((2)(1)+1)/6 = (2)(3)/6 = 1. So our formula works for this particular case- it is true for the case that n=1.

2. Assume that the sum of the first k squares is k(k+1)(2k+1)/6

3. Consider the sum of the first k+1 squares. This is equal to the sum of the first k squares plus (k+1)2. Using step 2, we have that the sum of the first k squares is k(k+1)(2k+1)/6, so the sum of the first k+1 squares is (k(k+1)(2k+1)/6) + (k+1)2 = (k+1)((k(2k+1)/6)+(k+1))=(k+1)(k(2k+1)+6k+6)/6 = (k+1)(2k2+7k+6)/6 = (k+1)(2k+3)(k+2)/6. Note that this can now be written as (k+1)((k+1)+1)(2(k+1)+1)/6, which is in the form of n(n+1)(2n+1)/6 where n=k+1, so assuming step 2, we’ve proved that it is true for n=k+1.

Finally, since this formula is true for n=1, and given that we’ve shown that if it is true for n=k, then it is true for n=k+1, then it must be true for all integer values of n greater than or equal to 1. So, the sum of the first n squares is equal to n(n+1)(2n+1)/6.

All the induction proofs you’ll be asked to do follow this structure. The only difference between them is the algebraic manipulations.

Andrew D. A Level Maths tutor, GCSE Maths tutor, A Level Further Math...

2 months ago

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

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

68 SUBJECT SPECIALISTS

£24 /hr

Joe C.

Degree: Mathematics (Masters) - Bristol University

Subjects offered: Further Mathematics , Maths

Further Mathematics
Maths

“I'm a third year student at Bristol University studying a Masters Degree in Mathematics. I try to make my tutorials engaging, and tailor them to your individual needs so that we are working towards the grade you aspire to achieve! I'v...”

£24 /hr

Josh R.

Degree: Mathematics (Masters) - Warwick University

Subjects offered: Further Mathematics , Maths

Further Mathematics
Maths

“I study Maths at Warwick, I hope to be able to teach your child to love Maths and how to achieve top exam grades. ”

£20 /hr

Peter H.

Degree: Mathematics (Bachelors) - Durham University

Subjects offered: Further Mathematics , Physics+ 2 more

Further Mathematics
Physics
Maths
.STEP.

“About me: I am a Mathematics student at Durham University, and I am currently in my 3rd year. I would very much like to give assistance and help students of all abilities to reach the goals they aspire to in Maths and Physics, whether...”

MyTutor guarantee

About the author

£20 /hr

Andrew D.

Degree: Mathematics (Masters) - Warwick University

Subjects offered: Further Mathematics , Maths

Further Mathematics
Maths

“About me Hi, I'm Andrew. I'm currently going into my second year studying maths at the University of Warwick. I find maths incredibly fascinating, as my passion stems from the idea thatmaths is everywhere and is fundamental to underst...”

You may also like...

Posts by Andrew

How do I find the limit as x-->infinity of (4x^2+5)/(x^2-6)?

How do I rationalise the denominator of a fraction?

How do I solve an integration by substitution problem?

How do I use proof by induction?

Other A Level Further Mathematics questions

Integrate (x+4)/(x^2+2x+2)

if y = (e^x)^7 find dy/dx

Integrate cos(4x)sin(x)

Find arsinh(x) in terms of x

View A Level Further Mathematics tutors

Cookies:

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

mtw:mercury1:status:ok