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 $\displaystyle 3 \equiv -2 (mod 5)$.)
Thus $\displaystyle 3^x$ is going to leave a remainder of $\displaystyle (-2)^x$ after division, where x is a positive integer. ($\displaystyle 3^x \equiv (-2)^x (mod 5)$.)
And
$\displaystyle (-2)^{3n} = (-1)^{3n}2^{3n} = (-1)^n2^{3n}$
Now, $\displaystyle 2^{n + 2} = 4 \cdot 2^n$.
4/5 leaves a remainder of -1 upon division ($\displaystyle 4 \equiv -1 (mod 5)$), so $\displaystyle 4 \cdot 2^n$ leaves a remainder of $\displaystyle -1 \cdot 2^n$.
So. Let's finally take a look at this.
$\displaystyle 3^{3n} + 2^{n+2}$ divided by 5 will leave a remainder of
$\displaystyle (-1)^n2^{3n} - 2^n = 2^n \left ( (-1)^n2^{2n} - 1 \right )$
Let's do this case by case.
If n is even then
$\displaystyle (-1)^n2^{2n} - 1 = 2^{2n} - 1$
$\displaystyle = \left ( 2^n \right ) ^2 - 1^2 = (2^n + 1)(2^n - 1)$
If n is doubly even (ie n = 4x) then $\displaystyle 2^n - 1 = 2^{4x} - 1 = 16^x - 1$.
Now, 16 leaves a remainder of 1 upon division by 5, so
$\displaystyle 16^x - 1$ leaves a remainder of $\displaystyle 1^x - 1 = 0 $ upon division by 5. So $\displaystyle 2^n - 1$ is divisible by 5 if n is doubly even.
If n is even, but not doubly even then $\displaystyle n = 4x + 2$. Then
$\displaystyle 2^n + 1 = 2^{4x + 2} + 1 = 4 \cdot 2^{4x} + 1$
$\displaystyle = 4 \cdot 16^x + 1$
Dividing this by 5 leaves a remainder of $\displaystyle -1 \cdot 1^x + 1 = -1 + 1 = 0$. So $\displaystyle 2^n + 1$ is divisible by 5 if n is even but not doubly even.
Thus $\displaystyle 3^{3n} + 2^{n+2}$ is divisible by 5 if n is even.
If n is odd then n = 2x + 1:
$\displaystyle (-1)^n2^{2n} - 1 = -(2^{2n} + 1)$
$\displaystyle = -(2^{2(2x + 1)} + 1) = -(2^{4x + 2} + 1)$
$\displaystyle = -(4 \cdot 2^{4x} + 1) = -(4\cdot 16^x + 1)$
As in the last case (where n was even but not doubly even) $\displaystyle 4 \cdodt 16^x + 1$ is divisible by 5.
Thus $\displaystyle 3^{3n} + 2^{n+2}$ is divisible by 5 if n is odd.
Thus $\displaystyle 3^{3n} + 2^{n+2}$ 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:
$\displaystyle 3^{3 \cdot 0} + 2^{0 + 2} = 3^0 + 2^2 = 1 + 4 = 5$
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.
$\displaystyle 3^{3(n + 1)} + 2^{(n + 1) + 2} = 3^{3n + 3} + 2^{n + 3} = 27 \cdot 3^{3n} + 2 \cdot 2^{n + 2}$
Now let $\displaystyle 5x = 3^{3n} + 2^{n + 2}$, so according to our supposition x is a whole number. Then
$\displaystyle 3^{3n} = \left ( 5x - 2^{n + 2} \right ) $
So
$\displaystyle 3^{3(n + 1)} + 2^{(n + 1) + 2} = 27 \left ( 5x - 2^{n + 2} \right ) + 2 \cdot 2^{n + 2}$
$\displaystyle = 27 \cdot 5x - 27 \cdot 2^{n + 2} + 2 \cdot 2^{n + 2} = 27 \cdot 5x + (-27 + 2) 2^{n + 2}$
$\displaystyle = 27 \cdot 5x - 25 \cdot 2^{n + 2}$
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!
Verify $\displaystyle S(1)$Prove by induction: .$\displaystyle 3^{3n} + 2^{n+2}$ is divisible by 5.
. . $\displaystyle 3^3 + 2^3\:=\:27 + 8 \:=\:35$ . . . true!
Assume $\displaystyle S(k)$ is true
. . $\displaystyle 3^{3k} + 2^{k+2} \;=\;5a$ for some integer $\displaystyle a$. . [1]
We want to show that: .$\displaystyle 3^{3k+3} + 2^{k+3}$ is divisible by 5.
Add $\displaystyle 26\!\cdot\!3^{3k} + 2^{k+2}$ to both sides of [1]
. . $\displaystyle 3^{3k} + 26\!\cdot\!3^{3k} + 2^{k+2} + 2^{k+2} \;= \;5a + 26\!\cdot\!3^{3k} + 2^{k+2} $
We have: .$\displaystyle 27\!\cdot\!3^{3k} + 2\!\cdot\!2^{k+2} \;= \;5a + 25\!\cdot\!3^{3k} + 3^{3k} + 2^{k+2}$
. . . . . . . . . $\displaystyle 3^3\!\cdot\!3^{3l} + 2^{k+3} \;=\;\left(5a + 25\cdot3^{3k}\right) + \underbrace{\left(3^{3k} + 2^{k+2}\right)}_{\text{This is }5a} $
. . . . . . . . . $\displaystyle 3^{3k+3} + 2^{k+3} \;=\;10a + 25\!\cdot\!3^{3k} \;=\;5\left(2a + 5\!\cdot\!3^{3k}\right)$
Therefore: .$\displaystyle 3^{3k+3} + 2^{k+3}$ is divisible by 5.
The inductive proof is complete.
.