Proof by Mathematical Induction (Discrete Mathematics)
Free printable Discrete Mathematics worksheet with genuine induction problems on summation formulas (sum of the first n integers, odd numbers, squares, and powers of 2): base cases, inductive steps, and numeric verification, all computed by real summation.
✓ Answer key checked by math, never wrong
Discrete Mathematics · Math worksheet
Name
Date
Math
Proof by Mathematical Induction
Each claim P(n) is a summation formula. Verify the base case by computing both sides at n = 1. For the inductive step, assume P(k) (the inductive hypothesis), add the (k + 1)-th term to both sides, and simplify to the formula at n = k + 1. The numeric checks here mirror exactly the algebra of the written proof.
- 1.Consider the claim P(n): 1 + 2 + ... + n = n(n + 1)/2, for all integers n ≥ 1 (the sum of the first n positive integers). Verify the base case n = 1: what value do the left side and the right side each take?
- 2.For the claim P(n): 1 + 2 + ... + n = n(n + 1)/2: compute the left side for n = 6 by adding the terms directly, and confirm it matches the formula.
- 3.In the inductive step for P(n): 1 + 2 + ... + n = n(n + 1)/2, we assume P(k) and add the next term k + 1 to reach n = k + 1. For k = 5: what is the value of the added term, and what is the new total?
- 4.Consider the claim P(n): 1 + 3 + 5 + ... + (2n - 1) = n², for all integers n ≥ 1 (the sum of the first n odd numbers). Verify the base case n = 1: what value do the left side and the right side each take?
- 5.For the claim P(n): 1 + 3 + 5 + ... + (2n - 1) = n²: compute the left side for n = 6 by adding the terms directly, and confirm it matches the formula.
- 6.In the inductive step for P(n): 1 + 3 + 5 + ... + (2n - 1) = n², we assume P(k) and add the next term (2(k + 1) - 1) to reach n = k + 1. For k = 7: what is the value of the added term, and what is the new total?
- 7.Consider the claim P(n): 1² + 2² + ... + n² = n(n + 1)(2n + 1)/6, for all integers n ≥ 1 (the sum of the first n squares). Verify the base case n = 1: what value do the left side and the right side each take?
- 8.For the claim P(n): 1² + 2² + ... + n² = n(n + 1)(2n + 1)/6: compute the left side for n = 6 by adding the terms directly, and confirm it matches the formula.
- 9.In the inductive step for P(n): 1² + 2² + ... + n² = n(n + 1)(2n + 1)/6, we assume P(k) and add the next term (k + 1)² to reach n = k + 1. For k = 8: what is the value of the added term, and what is the new total?
- 10.Consider the claim P(n): 1 + 2 + 4 + ... + = - 1, for all integers n ≥ 1 (the sum of the first n powers of 2, starting at 2⁰). Verify the base case n = 1: what value do the left side and the right side each take?
- 11.For the claim P(n): 1 + 2 + 4 + ... + = - 1: compute the left side for n = 9 by adding the terms directly, and confirm it matches the formula.
- 12.In the inductive step for P(n): 1 + 2 + 4 + ... + = - 1, we assume P(k) and add the next term to reach n = k + 1. For k = 8: what is the value of the added term, and what is the new total?
- 13.An induction proof of "P(n) for all integers n ≥ 1" has two parts. After proving the base case P(1), what exactly must the inductive step establish?
- a) For every k ≥ 1, if P(k) holds then P(k + 1) holds
- b) P(k + 1) holds for one particular k
- c) P(k) holds for every k ≥ 1
- d) If P(k + 1) holds then P(k) holds
Made with ChalkBee · chalkbee.com