Proof by InductionDate: 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/ |
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/