Could you explain to me how proof by induction works?

Let's run through an example: proving by induction that n^2 = 1 + 3 + ... + (2n-1) for all integers n>0. Remember that when asked to use induction to prove a statement, you first need to show that the statement is true in what is called the 'base case', the smallest value n can take. Here the base case is n=1; substituting into the statement gives 1^2 = 1, which is true. The next step is to assume the statement is true for n=k, and from that assumption show that it is also true for n=k+1. So our assumption is: k^2 = 1 + 3 + ... + (2k-1). Our aim is to reach the same expression, but with a (k+1) in every place there is a k. So a good place to start is expanding (k+1)^2 = k^2 + 2k + 1. We can then use our assumption to substitute in the expression for k^2: (k+1)^2 = 1 + 3 + ... + (2k-1) + 2k + 1. We're almost done. We need to get a (k+1) in the final term, so try: (k+1)^2 = 1 + 3 + ... + (2k-1) + (2(k+1)-1) = 1 + 3 + ... + (2(k+1)-1) which is exactly what we wanted. So we know that if the statement is true for n=k, it's true for n=k+1. But remember we have shown that this is true for n=1. So it must be true for n=2. And then also for n=3. And so on... we say that by induction, the statement is true for all integers n>0.

Related Further Mathematics A Level answers

All answers ▸

Prove that matrix multiplication is not commutative.


Why am I learning about matrices? What are they?!


Prove that sum(k) from 0 to n is n(n+1)/2, by induction


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