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.

AD
Answered by Andrew D. Further Mathematics tutor

3474 Views

See similar Further Mathematics A Level tutors

Related Further Mathematics A Level answers

All answers ▸

Find the 4th roots 6


How do you sketch the graph of y=(x-1)/(x+1)?


Given that z = a + bj, find Re(z/z*) and Im(z/z*).


A particle is moving in a straight line with simple harmonic motion. The period of the motion is (3pi/5)seconds and the amplitude is 0.4metres. Calculate the maximum speed of the particle.


We're here to help

contact us iconContact usWhatsapp logoMessage us on Whatsapptelephone icon+44 (0) 203 773 6020
Facebook logoInstagram logoLinkedIn logo

© MyTutorWeb Ltd 2013–2025

Terms & Conditions|Privacy Policy
Cookie Preferences