Proving Divisibility: Mathematical Induction & Examples

An error occurred trying to load this video.

Try refreshing the page, or contact customer support.

Coming up next: What is a Matrix?

You're on a roll. Keep up the good work!

Take Quiz Watch Next Lesson
 Replay
Your next lesson will play in 10 seconds
  • 0:04 Divisibility
  • 1:28 Mathematical Induction
  • 2:38 Examples
  • 5:08 Lesson Summary
Save Save Save

Want to watch this again later?

Log in or sign up to add this lesson to a Custom Course.

Log in or Sign up

Timeline
Autoplay
Autoplay
Speed Speed
Lesson Transcript
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.

In this lesson, we'll review divisibility, mathematical induction, and the steps of mathematical induction. We'll then look at how to prove divisibility using mathematical induction through an example.

Divisibility

Suppose you and four of your friends go in on a lottery ticket with a winning prize of $1000. Low and behold, you end up winning, so you need to split up the $1000 between the five of you. To figure out each person's take, you divide 1000 by 5.

1000 / 5 = 200

Each of you gets a nice whole dollar amount of $200. This is because 5 divides into 1000 evenly. Mathematically speaking, we would say that 1000 is divisible by 5 or that 5 divides 1000.

In general, if we divide a number, a, by a number, b, and we get a whole number, m, then we say that a is divisible by b or that b divides a. That is,

  • If a / b = m or a = b * m, where m is a whole number, then a is divisible by b or b divides a.

This definition of divisibility also applies to mathematical expressions. If a mathematical expression A is divisible by a number b, then A = b * m, where m is a whole number.

This fact, along with mathematical induction, proves itself extremely useful in the process of proving divisibility. Wait, mathematical what? Mathematical induction is a method of proof that we can use to prove divisibility. Let's take a look at this technique.

Mathematical Induction

Mathematical induction is a proof technique that is based around the following fact:

  • In a well-ordered set (or a set that has a first element and the elements in the set are ordered, like the natural numbers), if a property is true for n and n + 1, where n is any element in the set, then it is true for all the elements in the set.

The process of proving statements through mathematical induction has three steps:

  1. Base step: Prove the statement is true for the first element in the set
  2. Assume the statement is true for an element k in the set
  3. Show the statement is true for the element k + 1 in the set

These three steps will show that a property is true for k, and k + 1, where k is any element in a set, so it proves that the property is true for all the elements in the set.

We can use mathematical induction, along with our facts about divisibility to prove that an expression is divisible by a number from a well-ordered set. What we'll find is that the third step is the trickiest, but once you've practiced this process a few times, it gets easier. Speaking of which, let's do that!

Examples

Suppose we want to show that 9n is divisible by 3, for all natural numbers, n. We can use mathematical induction to do this.

The first step (also called the base step) would be to show that 9n is divisible by 3 for n = 1, since 1 is the first natural number.

  • 91 = 9 and 9 = 3 * 3. Since 91 = 3 * 3, and 3 is a whole number, our definition of divisibility gives that 91 is divisible by 3. This proves our base step.

That wasn't so bad! On to the next step!

Step two is to assume that the statement is true for a natural number k. That is, we assume that 9k is divisible by 3. Therefore, by the definition of divisibility, we have that:

  • 9k = 3 * m, where m is a whole number

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