Worksheet: Mathematical Induction

In this worksheet, we will practice applying the mathematical induction method to prove a summation formula.

Q1:

David has read in a textbook that 𝑟=𝑛(𝑛+1)2.David wants to prove this using induction.

First, he starts with the basis step substituting 𝑛=1 into each side of the equation. He calculates that the left-hand side, 𝑟, equals 1. Calculate the value of the right-hand side, and, hence, determine if the basis is true.

  • A1, true
  • B1, false

David assumes that the summation formula is true when 𝑛=𝑘 giving him that 𝑟=𝑘(𝑘+1)2. For the induction step, he needs to show that 𝑟=(𝑘+1)(𝑘+2)2. Using the fact that=+(𝑘+1), substitute in David’s assumption and simplify the result to find an expression for 𝑟.

  • A(𝑘+2)2
  • B(𝑘+1)(𝑘+2)2
  • C(𝑘+1)(𝑘+2)
  • D(𝑘+2)2

David then makes the following conclusion:

If our assumption is correct for 𝑛=𝑘, we have shown that the summation formula is correct when 𝑛=𝑘+1. Therefore, as we have shown that the summation formula is true when 𝑛=1, by mathematical induction, the formula is true for all natural numbers 𝑛.

Is David’s conclusion correct?

  • AYes
  • BNo

Q2:

Charlotte is trying to prove the summation formula 𝑟=𝑛(𝑛+1)(2𝑛+1)6.

She has checked that the basis is correct, has assumed that 𝑟=𝑘(𝑘+1)(2𝑘+1)6, and is trying to show that 𝑟=(𝑘+1)(𝑘+2)(2𝑘+3)6.

Charlotte knows that she needs to express 𝑟 in terms of her assumption for the 𝑟, but she cannot quite remember the method. Determine which of the following is correct.

  • A𝑟=𝑟+(𝑘+1)=𝑘(𝑘+1)(2𝑘+1)6+(𝑘+1)
  • B𝑟=𝑟+1=𝑘(𝑘+1)(2𝑘+1)6+1
  • C𝑟=𝑟+(𝑟+1)=𝑘(𝑘+1)(2𝑘+1)6+(𝑟+1)
  • D𝑟=𝑟+(𝑘)=𝑘(𝑘+1)(2𝑘+1)6+(𝑘)

Q3:

Natalie wants to prove, using induction, that 𝑓(𝑛)=23 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 𝑓(𝑘)=23 is divisible by 5. She then needs to show that 𝑓(𝑘+1)=23() is divisible by 5. To do this, she considers the difference 𝑓(𝑘+1)𝑓(𝑘). Write this difference in the form 𝑎2𝑏3.

  • A𝑓(𝑘+1)𝑓(𝑘)=7223
  • B𝑓(𝑘+1)𝑓(𝑘)=9243
  • C𝑓(𝑘+1)𝑓(𝑘)=7243
  • D𝑓(𝑘+1)𝑓(𝑘)=9223
  • E𝑓(𝑘+1)𝑓(𝑘)=4243

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 72 as 52+22, rewrite the expression for 𝑓(𝑘+1)𝑓(𝑘) to incorporate 𝑓(𝑘).

  • A𝑓(𝑘+1)𝑓(𝑘)=2+2𝑓(𝑘)
  • B𝑓(𝑘+1)𝑓(𝑘)=52+2𝑓(𝑘)
  • C𝑓(𝑘+1)𝑓(𝑘)=52+2𝑓(𝑘)
  • D𝑓(𝑘+1)𝑓(𝑘)=52+𝑓(𝑘)
  • E𝑓(𝑘+1)𝑓(𝑘)=52+𝑓(𝑘)

Natalie rearranges the equation 𝑓(𝑘+1)=52+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?

  • AYes
  • BNo

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