Proof of the Addition Principle by InductionDate: 07/18/99 at 19:08:07 From: Thomas Subject: Proof of the Addition Principle by Induction The Addition Principle states that If there are r1 different objects in the first set, r2 objects in the second set, and rm objects in the mth set, and if different sets are disjoint, then the number of ways to select an object from one of the m sets is r1 + r2 + ... + rm. I tried to prove this by induction, but I cannot seem to get it to make sense. One more question: How can I prove by induction that: ( 2^(3n) - 1) is divisible by 7, for all values of n greater than 0. Date: 07/19/99 at 05:55:19 From: Doctor Anthony Subject: Re: Proof of the Addition Principle by Induction The total number of objects is r1 + r2 + ..... + rm = N (say) With N objects to choose from, the number of ways of choosing one object is C(N, 1) = N and this corresponds with what you are asked to prove. Now for your second question, Let f(n) = 2^(3n) -1. We must show f(n) = M(7), where M(7) means ' is a multiple of 7 ' First test if true for n = 1 (f(1) = 2^3 - 1 = 8-1 = 7 Yes, correct. Now, assume it is true for n = k, that is f(k) = 2^(3k) - 1 = M(7) Then, f(k + 1) = 2^(3k + 3) - 1 = 2^3 x [2^(3k) -1] + 2^3 - 1 = 2^3 x M(7) + 7 = M(7) Therefore if f(k) = M(7), then f(k + 1)= M(7). But f(1) = M(7), therefore f(2) = M(7), and if true for n = 2, it will be true for n = 3 and so on to all positive integers n. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/