How does proof by mathematical induction work?

Mathematical induction is a way of proving statements in maths. The principle is quite similar to dominoes (not pizza, the game) - if you push the first one, the second one will be pushed over, pushing the third one and so on. There are 3 stages to induction. The first stage is to prove that the base case, n = 1 is true (essentially the first domino). The second stage involves you assuming the case n = k is true. The final stage involves you using the assumption above to show that the case n = k + 1 is also true (essentially you're showing that if you push the kth domino, the (k + 1)th domino will also be pushed over).Here is an example of proof by induction being applied: For any positive integer n, 1 + 2 + 3 + ... + n = n(n + 1)/2. Let P(n) be the assumption that 1 + 2 + 3 + ... + n = n(n + 1)/2. Consider the base case, n = 1: Left-hand side = 1. Right-hand side = 1(1 + 1)/2 = 1 As LHS = RHS, P(1) is true.Assume that P(k) is true i.e. 1 + 2 + 3 + ... + k = k(k + 1)/2. Consider P(k + 1) [remember we have to use P(k) somewhere here] 1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) (using P(k)) Taking a factor of (k + 1) from the RHS: k(k + 1)/2 + (k + 1) = (k + 1)[k/2 + 1] = (k + 1)(k + 2)/2 = (k + 1)((k + 1) + 1)/2 i.e. P(k + 1) is true.Therefore, as P(1) is true and P(k) true implies P(k + 1) is true, by the principle of mathematical induction, 1 + 2 + 3 + ... + n = n(n + 1)/2

Related Further Mathematics A Level answers

All answers ▸

Find the volume of revolution about the x-axis of the curve y=1/sqrt(x^2+2x+2) for 0<x<1


Integrate tan(x) wrt x


Solve x^2+8x-5=0 using completing the square


Using a Suitable substitution or otherwise, find the differential of y= arctan(sinxcosx), in terms of y and x.


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