Question Video: Using Induction to Prove Divisibility

Video Transcript

Natalie wants to prove, using induction, that 𝑓 of 𝑛 equals two to the three 𝑛 power minus three to the 𝑛 power is divisible by five for all integers when 𝑛 is greater than or equal to one. First, she needs to check the base case when 𝑛 equals one. Substitute 𝑛 equals one into the expression and determine the result when it is divided by five.

Before we do that, it’s helpful to know what induction means here. It means we’re going to move from a specific case outward to a more general case. Our specific case is when 𝑛 equals one. Is it true that this expression is divisible by five when 𝑛 equals one? So, we substitute one in place of 𝑛, and we’ll have two cubed minus three. Two cubed equals eight. Eight minus three equals five. We wanted to know if our function when 𝑛 equals one was divisible by five. 𝑓 of one equals five. Five divided by five equals one. When we substitute 𝑛 equals one into the expression and determine the result, we get one. 𝑓 of one is divisible by five. Now, we want to take this specific case and move to something more general.

Natalie then makes the assumption that 𝑓 of 𝑘 equals two to the three 𝑘 power minus three to the 𝑘 power is divisible by five. She then needs to show that 𝑓 of 𝑘 plus one equals two to the three times 𝑘 plus one power minus three to the 𝑘 plus one power is divisible by five. To do this, she considers the difference 𝑓 of 𝑘 plus one minus 𝑓 of 𝑘. Write this difference in the form 𝑎 times two to the three 𝑘 power minus 𝑏 times three to the 𝑘 power.

𝑓 of 𝑘 equals two to the three 𝑘 power minus three to the 𝑘 power. 𝑓 of 𝑘 plus one equals two to the three times 𝑘 plus one power minus three to the 𝑘 plus one power. We need to subtract 𝑓 of 𝑘 from 𝑓 of 𝑘 plus one. We can simplify this by regrouping the powers with the same bases. Two to the three times 𝑘 plus one power minus two to the three 𝑘 power. We’re subtracting here because 𝑓 of 𝑘 is being subtracted from 𝑓 of 𝑘 plus one.

Now, we’ll group the base three terms together, negative three to the 𝑘 plus one power plus three to the 𝑘 power. We add plus three 𝑘 because we were subtracting a negative. In our exponents, we can distribute this three. Three times 𝑘 plus one becomes three 𝑘 plus three. Based on our power rules, we know that 𝑥 to the 𝑎 plus 𝑏 power is equal to 𝑥 to the 𝑎 power times 𝑥 to the 𝑏 power. We can rewrite two to the three 𝑘 plus three power as two to the three 𝑘 power times two to the third power.

We’ll bring down our next term, two to the three 𝑘 power. And then, we’ll rewrite three to the 𝑘 plus one power as three to the 𝑘 power times three to the first power, and then bring down our three to the 𝑘 power. From here, we recognize some like terms. When we factor out two to the three 𝑘 power, we have two to the three 𝑘 power times two cubed minus one. We also need to factor out three to the 𝑘 power.

We’ll factor out a positive three to the 𝑘 power, which will be multiplied by negative three to the first power plus one. To further simplify, we’ll solve two cubed minus one. Two cubed equals eight. And eight minus one equals seven. We can also simplify negative three to the first power plus one. Negative three to the first power equals negative three, plus one equals negative two.

Remember, the form we’re looking for looks like this. 𝑎 times two to the three 𝑘 power minus 𝑏 times three to the 𝑘 power. If we rearrange our equation, we have seven times two to the three 𝑘 power minus two times three to the 𝑘 power. We found that 𝑎 equals seven and 𝑏 equals two. We’re saying that 𝑓 of 𝑘 plus one minus 𝑓 of 𝑘 equals seven times two to the three 𝑘 power minus two times three to the 𝑘 power. To make some space, we’ll move that expression up.

At this stage, it is still not clear whether 𝑓 of 𝑘 plus one is divisible by five. Natalie notices that she may be able to substitute 𝑓 of 𝑘 into the expression. By writing seven times two to the three 𝑘 power as five times two to the three 𝑘 power plus two times two to the three 𝑘 power, rewrite the expression for 𝑓 of 𝑘 plus one minus 𝑓 of 𝑘 to incorporate 𝑓 of 𝑘.

Starting with what we originally found for 𝑓 of 𝑘 plus one minus 𝑓 of 𝑘, we want to rewrite seven times two to the three 𝑘 power as five times two to the three 𝑘 power plus two times two to the three 𝑘 power. Bring down the subtract two times three to the 𝑘 power. And then, we notice something. We have a factor of two for the last two terms. If we factor out that two, we can rewrite this part of the expression as two times two to the three 𝑘 power minus three to the 𝑘 power. And we should recognize this. Two to the three 𝑘 power minus three to the 𝑘 power equals 𝑓 of 𝑘.

So, we bring down our five times two to the three 𝑘 power. And then, we rewrite the expression as five times two to the three 𝑘 power plus two times 𝑓 of 𝑘. We can now say that 𝑓 of 𝑘 plus one minus 𝑓 of 𝑘 equals five times two to the three 𝑘 power plus two times 𝑓 of 𝑘. We’ll bring that expression up.

Natalie rearranges the equation so 𝑓 of 𝑘 plus one equals five times two to the three 𝑘 power plus three times 𝑓 of 𝑘. She then comes to this conclusion. If the assumption is correct that the expression is divisible by five when 𝑛 equals 𝑘, then we have shown that the expression is divisible by five when 𝑛 equals 𝑘 plus one. As we have shown that the expression is divisible by five when 𝑛 equals one, we have proved by mathematical induction that the expression is divisible by five for all integers when 𝑛 is greater than or equal to one. Is Natalie’s conclusion correct?

At this point, we need a little more space. Natalie took our expression 𝑓 of 𝑘 plus one minus 𝑓 of 𝑘 equals five times two to the three 𝑘 power plus two times 𝑓 of 𝑘. And then, she added 𝑓 of 𝑘 to both sides of the equation, which left us with 𝑓 of 𝑘 plus one is equal to five times two to the three 𝑘 power plus three times 𝑓 of 𝑘. We already know that 𝑓 of 𝑘 is divisible by five, so we can say that 𝑓 of 𝑘 is a multiple of five. And three times a multiple of five will always produce a multiple of five.

Our other term in 𝑓 of 𝑘 plus one is being multiplied by five. And any integer multiplied by five will be a multiple of five. 𝑓 of 𝑘 plus one is equal to a multiple of five plus a multiple of five, which will always result in a multiple of five and will, therefore, be divisible by five. This shows us that yes, Natalie is correct. We moved from our specific case, 𝑛 equals one, to the general case, where 𝑛 equals 𝑘 plus one, to prove divisibility by five.