Suppose you want to use the principle of mathematical induction to prove that 1 + 2 + 22 + 23 + 23 + ... + 2n = + 2n+1 - 1 for all positive integers n. Which of these is the correct implication p(k) -> P(k+1) to be used in the inductive step?

• 1 + 2 + 22 + 23 + + 2k = 2k+1 - 1 -> 1 + 2 + 22 + 23 + 24 + + 2k + 2k+1 - 1
• 1 + 2 + 22 + 23 + + 2k = 2k+1 - 1 -> 1 + 2 + 22 + 23 + + 2k + 2k+1 = 2k+1 - 1 + 2k+1
• 2k -> 2k+1 - 1
• 1 + 2 + 22 + 23 + + 2k = 2k+1 - 1 -> 1 + 2 + 22 + 23 + + 2k + 2k+1 = 2k+2 - 1 Correct