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

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.

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/

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search