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

2809 Views

See similar Further Mathematics A Level tutors

Related Further Mathematics A Level answers

All answers ▸

A parabola with equation y^2=4ax for constant a is translated by the vector (2,3) to give the curve C. The curve C passes through the point (4,7), what is the value of a?


Find the general solution to the differential equation d^2x/dt^2 + 5 dx/dt + 6x = 4 e^-t


Find the eigenvalues and eigenvectors of the matrix M , where M{2,2} = (1/2 2/3 ; 1/2 1/3) Hence express M in the form PDP^-1 where D is a diagonal matrix.


Prove by mathematical induction that 11^n-6 is divisible by 5 for all natural numbers n


We're here to help

contact us iconContact ustelephone icon+44 (0) 203 773 6020
Facebook logoInstagram logoLinkedIn logo

© MyTutorWeb Ltd 2013–2025

Terms & Conditions|Privacy Policy
Cookie Preferences