When and how do I use proof by induction?

If you have a claim which says something about every element in a list of elements with each element depending on previous elements, induction might be a useful starting point. In your exams, that "list of elements" is probably going to be numbers that form a sequence, something like the Fibonnaci sequence (1,1,2=1+1,3=2+1,5=3+2,8=5+3,...), which is obviously a list of numbers, and obviously each number depends on the numbers prior to it (since the nth element is the sum of the previous two elements) or a series (which is just a sequence hidden in different notation), but the idea of listing things you want to prove something about in such a way that a thing in that list depends on the things before it is quite powerful; I still use that method in my degree for proving things about quite complex objects like certain types of compression codes, so it's a good tool to have at hand.

The reason listing things like this is useful is because induction relies on two things: that the claim is true for your first element; and that if the claim is true for all elements up to the nth element, then the claim is true for the (n+1)th element (which means it's true for the (n+2)th element, and the (n+3)th element, and so on). The way it's often described it like a chain of dominos: you tip over the first one by showing that the claim is true for the first element, and you show that the dominos all knock each other over by proving that truth up to n implies truth for n+1. 

SR
Answered by Steven R. Further Mathematics tutor

2701 Views

See similar Further Mathematics A Level tutors

Related Further Mathematics A Level answers

All answers ▸

find general solution to: x(dy/dx) + 2y = 4x^2


Find the determinant of matrix M. [3]


How do you calculate the derivative of cos inverse x?


Solve the second order ODE, giving a general solution: x'' + 2x' - 3x = 2e^-t


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