Drexel dragonThe Math ForumDonate to the Math Forum

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

Proof by Induction


Date: 06/15/99 at 16:40:02
From: Sara Bergman
Subject: Show by induction

Show by induction that  (4^n)-1  is divisible by 3 for all n >= 1.

So far so good...?
n = 1   Left = Right 

        n = p+1
(4^p+1)-1 = 3k (k = constant)
4*(4^p)-1 = 3k
After that...?


Date: 06/15/99 at 17:55:38
From: Doctor Anthony
Subject: Re: Show by induction

Suppose  f(n) =  4^n - 1  

Let M(3) stand for 'is a multiple of 3'

We must prove that f(n) = M(3) for all n >= 1.

Check that it is true for n = 1, i.e. 4^1 - 1 = 3 = M(3). So it's true 
for n = 1.

Assume it's true for n = k. That is, we assume  4^k - 1 = M(3).

Now consider n = k+1

   f(k+1) = 4^(k+1) - 1

          = 4*4^k + (-4 + 4) - 1

          = (4*4^k - 4) + 4 - 1

          = 4(4^k - 1) + 4 - 1

          = 4(4^k - 1) + 3

          = M(3) + M(3)

          = M(3)

So if f(k) is M(3), then so is f(k+1). Since f(1) is M(3), so then 
f(2) is also M(3). And if f(2) is M(3), then f(3) is M(3). And if f(3) 
is M(3), then f(4) is M(3), and so on to all positive integer values 
of n.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Discrete Mathematics

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-2013 The Math Forum
http://mathforum.org/dr.math/