Proof by Induction: Steps & Examples

Instructor: Laura Pennington

Laura received her Master's degree in Pure Mathematics from Michigan State University. She has 15 years of experience teaching collegiate mathematics at various institutions.

Mathematical induction is a method of proof that is often used in mathematics and logic. We will learn what mathematical induction is and what steps are involved in mathematical induction.

Mathematical Induction

Have you ever met someone who doesn't like Rice Krispies treats? I haven't, and I would be willing to bet that everyone likes them! Suppose we wanted to prove that everyone in the world likes Rice Krispies treats. We might start by saying that I like them, my mom likes them, my friend likes them, and so on. However, unless we asked every single person in the world if they liked these treats (a fairly impossible feat since someone new is born every second or so), it wouldn't actually be proven. Proving that it is true for a select population makes the likelihood that everyone likes them higher, but doesn't truly prove that the whole world likes them.

It's problems similar to these that we can prove using a method called mathematical induction. Mathematical induction is a form of proof used to prove a property about all of the elements in an infinite set. When we are dealing with a problem involving an infinite set, it would be impossible to prove something is true about that set by just proving it for individual cases. Therefore, we use mathematical induction.

When to Use Mathematical Induction

As mentioned, we use mathematical induction when we want to prove a property for an infinite number of elements. This is the main indicator that mathematical induction is a good method to use. There are a few questions involved in mathematical induction.

1.) Do we want to prove something for a set of elements that is infinite?

2.) Would it be easy to prove the property for the first element in the set?

3.) If we were to assume the property was true for the first k elements, can we use that to show that it is also true for the (k + 1)st element?

induction 2

If the answers to these questions are yes, then mathematical induction is definitely the way to go, and the good news is that by answering these questions, you have already basically performed the proof! For example, suppose we wanted to prove that the sum of the first n positive integers is equal to (n(n + 1)) / 2.

The sum of the first n positive integers is given by the formula

Sum of Integers Formula

The set of positive integers is an infinite set, so the answer to question 1 is yes. We could easily add up the first one, two, or three integers and make sure the formula holds, so the answer to question 2 is yes. Lastly, if we assume the property is true for the first k cases, can we use that to show it is true for the (k + 1)st case? If the answer to this is also yes, then that means our formula is true for all of the members of our infinite set. Why is this? Well, if we know that the formula is true for 3, then it must be true for 3+1 = 4. And if it is true for 4, then it must be true for 4+1 = 5. And so on to infinity. This is the key step in mathematical induction and will be easier to see when we go through the example below.

Steps in Mathematical Induction

Mathematical induction is based on the fact that if something is true for the first k terms, and we show it is true for the (k + 1)st term, then it is true for all terms in an infinite set. This fact leads us to the steps involved in mathematical induction.

1.) Show the property is true for the first element in the set. This is called the base case.

2.) Assume the property is true for the first k terms and use this to show it is true for the (k + 1)st term. This is called the induction step.

To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create an account
Support