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

SC
Answered by Shayantan C. Further Mathematics tutor

6539 Views

See similar Further Mathematics A Level tutors

Related Further Mathematics A Level answers

All answers ▸

Use algebra to find the set of values of x for which mod(3x^2 - 19x + 20) < 2x + 2.


How do you sketch the graph of y=(x-1)/(x+1)?


find an expression for the sum of the series of 1 + 1/2cosx + 1/4cos2x +1/8cos3x + ......


Using z=cos(θ)+isin(θ), find expressions for z^n-1/z^n and z^n+1/z^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