how do I prove the following for all postive integers n
3^(3n) + 2^(n+2) is divisible by 5
3/5 leaves a "remainder" of -2 upon division. (In more complicated "mathspeak" this means .)
Thus is going to leave a remainder of after division, where x is a positive integer. ( .)
And
Now, .
4/5 leaves a remainder of -1 upon division ( ), so leaves a remainder of .
So. Let's finally take a look at this.
divided by 5 will leave a remainder of
Let's do this case by case.
If n is even then
If n is doubly even (ie n = 4x) then .
Now, 16 leaves a remainder of 1 upon division by 5, so
leaves a remainder of upon division by 5. So is divisible by 5 if n is doubly even.
If n is even, but not doubly even then . Then
Dividing this by 5 leaves a remainder of . So is divisible by 5 if n is even but not doubly even.
Thus is divisible by 5 if n is even.
If n is odd then n = 2x + 1:
As in the last case (where n was even but not doubly even) is divisible by 5.
Thus is divisible by 5 if n is odd.
Thus is divisible by 5 for all n.
-Dan
Ah, okay. I just noticed that the title of the original post is "mathematical induction." So let's try this:
n = 0:
is manifestly divisible by 5.
Now assume that the statement is true for some given value of n. We wish to show it is true for n + 1.
Now let , so according to our supposition x is a whole number. Then
So
As both terms are multiples of 5, so is the difference.
Thus the theorem is also true for n + 1 if it is true for some n.
Since it is true for n = 0, it is true for n = 1, thus also for n = 2, etc.
(This is not only faster than my previous method, but easier to understand. )
-Dan
Hello, polymerase!
VerifyProve by induction: . is divisible by 5.
. . . . . true!
Assume is true
. . for some integer . . [1]
We want to show that: . is divisible by 5.
Add to both sides of [1]
. .
We have: .
. . . . . . . . .
. . . . . . . . .
Therefore: . is divisible by 5.
The inductive proof is complete.
.