Concept
How can induction prove that (ab)ⁿ equals aⁿbⁿ?
Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1
"You learned in middle school that (ab)ⁿ = aⁿbⁿ. Prove this by mathematical induction. Solution: Let P(n) be the proposition that (ab)ⁿ = aⁿbⁿ.\n\n1. base case. We prove that P(1) is true simply by plugging it in. Setting n = 1 we have (ab)¹ = a¹b¹, so ab = ab.\n\n2. inductive step. We now must prove that P(k) ⇒ P(k + 1). Put another way, we assume P(k) is true, and then use that assumption to prove that P(k + 1) is also true.\n\nLet’s be crystal clear where we’re going with this. Assuming that P(k) is true means we can count on the fact that (ab)ᵏ = aᵏbᵏ. What we need to do, then, is prove that P(k + 1) is true, which amounts to proving that (ab)ᵏ⁺¹ = aᵏ⁺¹bᵏ⁺¹. Now we know by the very definition of exponents that (ab)ᵏ⁺¹ = ab(ab)ᵏ. Adding in our inductive hypothesis then lets us determine: (ab)ᵏ⁺¹ = ab(ab)ᵏ = ab · aᵏbᵏ = a · aᵏ · b · bᵏ = aᵏ⁺¹bᵏ⁺¹.\n\n3. conclusion. Therefore, ∀ n ≥ 1 P(n)."
Related Ideas
- How does the weak form of mathematical induction work?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How do you express a claim so it can be proved by induction?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- When is the strong form of mathematical induction useful?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- Why can mathematical induction be understood as proof by recursion?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What is a direct proof?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What is a proof?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What are axioms and theorems?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- Why is constructing mathematical proofs an essential skill?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1