Proof by Induction


by Caldus
Tags: induction, proof
Caldus
Caldus is offline
#1
Mar23-04, 05:10 PM
P: 106
How would I go about proving that 8^n - 3^n (n >= 1) is divisible by 5 using mathematical induction? I tried this but I do not think it is right:

First, prove that 8^1 - 3^1 is divisible by 5. 8^1 - 3^1 = 5, which is divisible by 5.

Second, prove that 8^(k+1) - 3^(k+1) is divisible by 5 if k = n. Notice that 8^(k+1) - 3^(k+1) =

8*(8^k) - 3^k(3). Based on the induction hypothesis, we already know that 8^k - 3^k is divisible by 5. So we end up with 24*(8^k - 3^k), which is always divisible by 5 because the term inside the parenthesis is already divisible by 5. Multiplying that by any number will not change the fact that it is divisible by 5.

Am I right here? Thanks.
Phys.Org News Partner Mathematics news on Phys.org
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Chen
Chen is offline
#2
Mar23-04, 05:20 PM
Chen's Avatar
P: 1,006
How did you figure this:
[tex]8*8^k - 3*3^k = 24(8^k - 3^k)[/tex]
?? You were doing fine up until that point. What you need to do is this:
[tex]8*8^k - 3*3^k = 5*8^k + 3*8^k + 3*3^k = 5*8^k + 3(8^k - 3^k)[/tex]
Caldus
Caldus is offline
#3
Mar23-04, 07:36 PM
P: 106
OK, I'm having trouble with this one as well. Can someone help me?

1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = (n(2n - 1)(2n + 1))/3

Chen
Chen is offline
#4
Mar24-04, 01:36 AM
Chen's Avatar
P: 1,006

Proof by Induction


[tex]1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = \frac{n(2n - 1)(2n + 1)}{3} = \frac{4n^3 - n}{3}[/tex]

So for [tex]k = n + 1[/tex]:
[tex]1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 + (2n + 1)^2 = \frac{(n + 1)(2n + 1)(2n + 3)}{3}[/tex]
[tex]\underline{1^2 + 3^2 + 5^2 + ... + (2n - 1)^2} + (2n + 1)^2 = \frac{4n^3 + 12n^2 + 11n + 3}{3}[/tex]
We already know it's true for [tex]n[/tex] so you can replace the underlined part:
[tex]\frac{4n^3 - n}{3} + (2n + 1)^2 = \frac{4n^3 - n}{3} + 4n^2 + 4n + 1 = \frac{4n^3 + 12n^2 + 11n + 3}{3}[/tex]
Multiply by 3:
[tex]4n^3 - n + 12n^2 + 12n + 3 = 4n^3 + 12n^2 + 11n + 3[/tex]
QED.
recon
recon is offline
#5
Mar24-04, 02:30 AM
recon's Avatar
P: 406
I have seen a beautiful geometrical way of deriving the sum of cubes of numbers, i.e. 1^3 + 2^3 + ... + n^3 = (1+2+...n)^2.

I wonder if there are simple ways of deriving [tex]1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = \frac{n(2n - 1)(2n + 1)}{3}[/tex]
Chen
Chen is offline
#6
Mar24-04, 05:44 AM
Chen's Avatar
P: 1,006
You can prove this:
[tex]1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = \frac{n(2n - 1)(2n + 1)}{3}[/tex]
With a bit of geometry, yes. If you draw squares with a side of 1, 3, 5, etc., one below the other, you can find the sum of their areas with a bit of manipulation, but it's not exactly simple (the idea is simple, the equations are a bit big though).
Bonk
Bonk is offline
#7
Oct14-04, 01:30 PM
P: 1
I have a problem:
Knowing that [tex]1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n + 1)(2n + 1)}{6}[/tex]and that [tex]1^3 + 2^3 + 3^3 + ... + n^3 = \frac{n^2 (n + 1)^2 } {4}[/tex], calculate [tex]1^4 + 2^4 + 3^4 + ... + n^4[/tex].
Please, help me!


Register to reply

Related Discussions
proof by induction: help General Math 4
Induction Proof Set Theory, Logic, Probability, Statistics 3
Proof by induction Calculus & Beyond Homework 4
another induction proof Precalculus Mathematics Homework 5
Proof by Induction Calculus & Beyond Homework 5