Nagwa uses cookies to ensure you get the best experience on our website. Learn more about our Privacy Policy.

Start Practicing

Worksheet: Proving Divisibility by Mathematical Induction

Q1:

Natalie wants to prove, using induction, that 𝑓 ( 𝑛 ) = 2 βˆ’ 3 3 𝑛 𝑛 is divisible by 5 for all integers 𝑛 β‰₯ 1 .

First, she needs to check the base case when 𝑛 = 1 . Substitute 𝑛 = 1 into the expression and determine the result when it is divided by 5.

Natalie then makes the assumption that 𝑓 ( π‘˜ ) = 2 βˆ’ 3 3 π‘˜ π‘˜ is divisible by 5. She then needs to show that 𝑓 ( π‘˜ + 1 ) = 2 βˆ’ 3 3 ( π‘˜ + 1 ) π‘˜ + 1 is divisible by 5. To do this, she considers the difference 𝑓 ( π‘˜ + 1 ) βˆ’ 𝑓 ( π‘˜ ) . Write this difference in the form π‘Ž 2 βˆ’ 𝑏 3 3 π‘˜ π‘˜ .

  • A 𝑓 ( π‘˜ + 1 ) βˆ’ 𝑓 ( π‘˜ ) = 7 ο€Ή 2  βˆ’ 2 ο€Ή 3  3 π‘˜ π‘˜
  • B 𝑓 ( π‘˜ + 1 ) βˆ’ 𝑓 ( π‘˜ ) = 9 ο€Ή 2  βˆ’ 4 ο€Ή 3  3 π‘˜ π‘˜
  • C 𝑓 ( π‘˜ + 1 ) βˆ’ 𝑓 ( π‘˜ ) = 9 ο€Ή 2  βˆ’ 2 ο€Ή 3  3 π‘˜ π‘˜
  • D 𝑓 ( π‘˜ + 1 ) βˆ’ 𝑓 ( π‘˜ ) = 7 ο€Ή 2  βˆ’ 4 ο€Ή 3  3 π‘˜ π‘˜
  • E 𝑓 ( π‘˜ + 1 ) βˆ’ 𝑓 ( π‘˜ ) = 4 ο€Ή 2  βˆ’ 4 ο€Ή 3  3 π‘˜ π‘˜

At this stage it is not clear whether 𝑓 ( π‘˜ + 1 ) is divisible by 5. Natalie notices that she may be able to substitute 𝑓 ( π‘˜ ) into the expression. By writing 7 ο€Ή 2  3 π‘˜ as 5 ο€Ή 2  + 2 ο€Ή 2  3 π‘˜ 3 π‘˜ , rewrite the expression for 𝑓 ( π‘˜ + 1 ) βˆ’ 𝑓 ( π‘˜ ) to incorporate 𝑓 ( π‘˜ ) .

  • A 𝑓 ( π‘˜ + 1 ) βˆ’ 𝑓 ( π‘˜ ) = 5 ο€Ή 2  + 𝑓 ( π‘˜ ) π‘˜
  • B 𝑓 ( π‘˜ + 1 ) βˆ’ 𝑓 ( π‘˜ ) = ο€Ή 2  + 2 𝑓 ( π‘˜ ) 3 π‘˜
  • C 𝑓 ( π‘˜ + 1 ) βˆ’ 𝑓 ( π‘˜ ) = 5 ο€Ή 2  + 2 𝑓 ( π‘˜ ) 3 π‘˜
  • D 𝑓 ( π‘˜ + 1 ) βˆ’ 𝑓 ( π‘˜ ) = 5 ο€Ή 2  + 𝑓 ( π‘˜ ) 3 π‘˜
  • E 𝑓 ( π‘˜ + 1 ) βˆ’ 𝑓 ( π‘˜ ) = 5 ο€Ή 2  + 2 𝑓 ( π‘˜ ) π‘˜

Natalie rearranges the equation 𝑓 ( π‘˜ + 1 ) = 5 ο€Ή 2  + 3 𝑓 ( π‘˜ ) 3 π‘˜ . She then comes to the following conclusion: If the assumption is correct that the expression is divisible by 5 when 𝑛 = π‘˜ , then we have shown that the expression is divisible by 5 when 𝑛 = π‘˜ + 1 . As we have shown that the expression is divisible by 5 when 𝑛 = 1 , we have proved by mathematical induction that the expression is divisible by 5 for all integers 𝑛 β‰₯ 1 .

Is Natalie’s conclusion correct?

  • ANo
  • BYes