Proof of the Addition Principle by Induction

Date: 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/