1. Have a structure within which to organize your work.
1a. The left-hand column will be the same each time. Every teacher will have specific wording intended to describe the process. Additional comments like “Let n = 1” or “Assuming the base case is true for n = k, we will now show that the base case is true for k + 1 and therefore for all integers” will be redundant from problem to problem within the discrete classroom.
1b. By keeping the calculations aligned, it will be easier to follow the calculation steps.
2. Highlight specific information. Another organization tool is intended to identify what part of the Inductive Assumption (also called the Inductive Hypothesis) will be used to simplify calculations in the proof. Highlighting the terms can take several forms like underlining or enclosing in brackets.
3. Use the highlighted form. The Induction Step itself follows a predictable steps. The key is to employ strong algebra skills in order to manipulate the left side to look like a simplified right side!
Add (k + 1) to the 1 + 2 + 3 + … + k + (k + 1) = (k + 1)(k + 1 + 1) / 2
left side and replace
k with (k + 1) on the
right side
Replace the underlined k (k + 1) + (k + 1) = (k + 1)(k + 2)
section on the left. 2 2
Then do all that elementary Algebra on the left side…..
…..adding fractions k (k + 1) + 2(k + 1)
2
…..factor out common terms (k + 1)(k + 2) = (k + 1)(k + 2)
2 2
QED: the left side looks just
like the right side!
4. Recognize properties of exponents. 'Product' and 'Multiple' induction problems have unique applications. The objective is to pull out the divisor so multiplying it by anything else would prove divisibility. This strategy might require expanding an exponential and using the distributive property. Here’s an example:
Prove that 11^n - 4^n is ‘a multiple of 7’ (or is ‘divisible by 7’)
Initial Test Step Let n = 1
11^1 - 4^1 = 11 - 4 = 7 (true)
Assume true when 11^k - 4^k is a multiple of 7
n = k Therefore, 11^k - 4^k = 7x
and 11^k = 7x + 4^k
Prove true when 11^(k + 1) - 4^(k + 1) is a multiple of 7
n = k + 1
(11^k)(11^1) - (4^k)(4^1)
(7x + 4^k)(11^1) - (4^k)(4^1)
11(7x + 4^k) - (4^k)(4)
77x + [11(4^k) - 4(4^k)]
77x + (4^k)(11 - 4)
77x + (4^k)(7)
7 (11x + 4^k) QED
Often, classroom expectations include some description like “7 times any number is a multiple of 7.” Individual teachers will have a favored statement to use.
5. Partition integers. Sometimes it is useful to split up integers into the sum of two other numbers (called Partitioning - a favored activity in early elementary numeracy education). To use it requires recognizing that 9 can be written as (8 + 1) or (5 + 4). So when proving that something is divisible by or a multiple of 8 for example, split up 9 into (8 + 1) and use the distributive property. For example…
Given: 18^n -1 is divisible by 17
Initial Test Step Let n = 1
18 - 1 = 17 (true)
Assume true when 18^k -1 is divisible by 17
n = k
Prove true when 18^(k + 1) - 1 is divisible by 17
n = k + 1
(18^k)(18^1) - 1
18(18^k)-1
(17 + 1)(18^k) -1
17(18^k) + 1(18^k -1)
Now might come a lengthy description preferred by a teacher:
17(18^k) is obviously divisible by 17 AND
(18^k - 1) is assumed divisible by 17 AND the sum
of any multiples of 17 is divisible by 17. QED
6. Know how to use Pascal’s Triangle to expand higher power binomials. While it is possible to raise a binomial to a higher power through long hand distribution, Pascal will be a work saver. Be ready to recognize what is duplicated and look for ways to factor out the divisor. Watch this…
Prove that the sum of the cubes of any 3 consecutive, positive integers is divisible by 9.
Set up 3 consecutive, positive integers = x, x + 1, x + 2
Cubes = x^3, (x + 1)^3, (x + 2)^3
Base Case x^3 + (x + 1)^3 + (x + 2)^3 is divisible by 9
Initial Test Step Let x = 1
1^3 + 2^3 + 3^3 is divisible by 9 (true)
Assume true when
x = k k^3 + (k + 1)^3 + (k + 2)^3 is divisible by 9
Pascal Assistant: k^3 = k^3
(k + 1)^3 = (k^3 + 3k^2 + 3k + 1)
(k + 2)^3 = (k^3 + 6k^2 +12k + 8)
Prove true when
x = k + 1 (k + 1)^3 + (k + 2)^3 + (k + 3)^3 is divisible by 9
Pascal Assistant: (k + 3)^3 = (k^3 + 9k^2 + 81k + 27)
k^3 + (k + 1)^3 + (k + 2)^3 + 9k^2 + 81k +27
[k^3 + (k + 1)^3 + (k + 2)^3] + 9(k^2 + 9k + 3)
[assumed divisible by 9] obviously divisible
by 9
Well, proof by induction may never be ‘simple,’ but it IS predictable and relies on just a few well-known manipulations. Keep these keys in mind and the task will (eventually) become routine.
No comments:
Post a Comment