MYTUTOR SUBJECT ANSWERS

257 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...

7 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

82 SUBJECT SPECIALISTS

£20 /hr

Luke B.

Degree: Mathematics (Masters) - Sheffield University

Subjects offered:Further Mathematics , Maths+ 3 more

Further Mathematics
Maths
.STEP.
.MAT.
-Personal Statements-

“I am a fun, engaging and qualified tutor. I'd love to help you with whatever you need, giving you the support you need to be the best you can be!”

£20 /hr

Gwen W.

Degree: Chemistry and Physics (Bachelors) - St. Andrews University

Subjects offered:Further Mathematics , Maths

Further Mathematics
Maths

“Hi, I'm Gwen! I have a great interest and enthusiasm for maths and would love to use this to help you reach your full potential in exams.”

£20 /hr

Sam A.

Degree: Mathematics (Bachelors) - York University

Subjects offered:Further Mathematics , Maths+ 1 more

Further Mathematics
Maths
Biology

“An enthusiastic and engaging undergrad mathematician (University of York, MMath), whose lessons are focused for the student, and never the teacher.”

About the author

Andrew D. A Level Maths tutor, GCSE Maths tutor, A Level Further Math...
£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

How does proof by mathematical induction work?

Can you express 3 + 4j in polar form?

How do you prove by induction?

Express (2x-1)/(x-1)(2x-3) in partial fractions.

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

mtw:mercury1:status:ok