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.

Related Further Mathematics A Level answers

All answers ▸

If a car of mass 1000kg travels up a slope inclined at 5 degrees at a speed of 20 meters per second calculate the power output of the car's engine (assuming a resistive force due to friction of 500N)


Write (1+2i) /(2-i) in form x+iy


The set of midpoints of the parallel chords of an ellipse with gradient, constant 'm', lie on a straight line: find its equation; equation of ellipse: x^2 + 4y^2 = 4


Write sin(4x) in terms of sin and cos.


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–2024

Terms & Conditions|Privacy Policy