Proof by Induction

According to the principle of mathematical induction, to prove a statement that is asserted about every natural number n, there are two things to prove. What is the first?

• The statement is true for n = 1.
• The statement is true for n = k.
• The statement is true for n = k+1.

According to the principle of mathematical induction, to prove a statement that is asserted about every natural number n, there are two things to prove. What is the second?

• The statement is true for n = k+1.
• If the statement is true for n = k, then it will be true for its successor, k + 1.
• The statement is true for n = 1.
• The statement is true for n = k.

The second part (If the statement is true for n = k, then it will be true for its successor, k + 1) contains the induction assumption. What is it?

• If the statement is true for n = k, then it will be true for its successor, k + 1.
• The statement is true for n = k.
• The statement is true for n = k+1.

The sum of the first n odd numbers is equal to the n^th square. 
1 + 3 + 5 + 7 + . . . + (2n − 1) = n²

To prove this by mathematical induction, what will be the induction assumption?

• The statement is true for n = k:
  1 + 3 + 5 + 7 + . . . + (2k − 1) = k²
• The statement is true for n = 1:
  2x1 − 1 = 1²
• The statement is true for n = k + 1:
  1 + 3 + 5 + 7 + . . . + (2k − 1) + (2k + 1) = (k + 1)²

1 + 3 + 5 + 7 + . . . + (2n − 1) = n²
On the basis of this assumption,
[The statement is true for n = k:
1 + 3 + 5 + 7 + . . . + (2k − 1) = k²]
What must we show?

• The statement is true for n = 1:
  2x1 − 1 = 1²
• The statement is true for n = k:
  1 + 3 + 5 + 7 + . . . + (2k − 1) = k²
• The statement is true for n = k + 1:
  1 + 3 + 5 + 7 + . . . + (2k − 1) + (2k + 1) = (k + 1)²

Let S(n) = 2n − 1. Evaluate: 
a)  S(k)
b)  S(k + 1)

• a)  S(k)  = 2k − 1
  b)  S(k + 1) = 2n + 1
• a)  S(k)  = 2k + 1
  b)  S(k + 1) = 2k + 1
• a)  S(k)  = 2k − 1
  b)  S(k + 1) = 2k + 1