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

3479 Views

See similar Further Mathematics A Level tutors

Related Further Mathematics A Level answers

All answers ▸

how do I do proofs by induction?


Express f(x) = ln(x+1) as an infinite series in ascending powers of x up to the 3rd power of x


A spring with a spring constant k is connected to the ceiling. First a weight of mass m is connected to the spring. Deduce the new equilibrium position of the spring, find its equation of motion and hence deduce its frequency f.


Determine if these two vectors are perpendicular. a=[1,4,8], b=[0,6,-3]


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