The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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   
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.