# Thread: mathematical induction

1. ## mathematical induction

how do I prove the following for all postive integers n

3^(3n) + 2^(n+2) is divisible by 5

2. Originally Posted by polymerase
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 $3 \equiv -2 (mod 5)$.)

Thus $3^x$ is going to leave a remainder of $(-2)^x$ after division, where x is a positive integer. ( $3^x \equiv (-2)^x (mod 5)$.)

And
$(-2)^{3n} = (-1)^{3n}2^{3n} = (-1)^n2^{3n}$

Now, $2^{n + 2} = 4 \cdot 2^n$.

4/5 leaves a remainder of -1 upon division ( $4 \equiv -1 (mod 5)$), so $4 \cdot 2^n$ leaves a remainder of $-1 \cdot 2^n$.

So. Let's finally take a look at this.
$3^{3n} + 2^{n+2}$ divided by 5 will leave a remainder of
$(-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
$(-1)^n2^{2n} - 1 = 2^{2n} - 1$

$= \left ( 2^n \right ) ^2 - 1^2 = (2^n + 1)(2^n - 1)$

If n is doubly even (ie n = 4x) then $2^n - 1 = 2^{4x} - 1 = 16^x - 1$.
Now, 16 leaves a remainder of 1 upon division by 5, so
$16^x - 1$ leaves a remainder of $1^x - 1 = 0$ upon division by 5. So $2^n - 1$ is divisible by 5 if n is doubly even.

If n is even, but not doubly even then $n = 4x + 2$. Then
$2^n + 1 = 2^{4x + 2} + 1 = 4 \cdot 2^{4x} + 1$

$= 4 \cdot 16^x + 1$
Dividing this by 5 leaves a remainder of $-1 \cdot 1^x + 1 = -1 + 1 = 0$. So $2^n + 1$ is divisible by 5 if n is even but not doubly even.

Thus $3^{3n} + 2^{n+2}$ is divisible by 5 if n is even.

If n is odd then n = 2x + 1:
$(-1)^n2^{2n} - 1 = -(2^{2n} + 1)$

$= -(2^{2(2x + 1)} + 1) = -(2^{4x + 2} + 1)$

$= -(4 \cdot 2^{4x} + 1) = -(4\cdot 16^x + 1)$

As in the last case (where n was even but not doubly even) $4 \cdodt 16^x + 1$ is divisible by 5.

Thus $3^{3n} + 2^{n+2}$ is divisible by 5 if n is odd.

Thus $3^{3n} + 2^{n+2}$ is divisible by 5 for all n.

-Dan

3. Originally Posted by polymerase
how do I prove the following for all postive integers n

3^(3n) + 2^(n+2) is divisible by 5
Ah, okay. I just noticed that the title of the original post is "mathematical induction." So let's try this:

n = 0:
$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.

$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 $5x = 3^{3n} + 2^{n + 2}$, so according to our supposition x is a whole number. Then
$3^{3n} = \left ( 5x - 2^{n + 2} \right )$

So
$3^{3(n + 1)} + 2^{(n + 1) + 2} = 27 \left ( 5x - 2^{n + 2} \right ) + 2 \cdot 2^{n + 2}$

$= 27 \cdot 5x - 27 \cdot 2^{n + 2} + 2 \cdot 2^{n + 2} = 27 \cdot 5x + (-27 + 2) 2^{n + 2}$

$= 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

4. So basically to prove this we only insert values for n?

But that doesnt seem right. I dont think it will always work just because it worked in a few circumstances.

5. Originally Posted by janvdl
So basically to prove this we only insert values for n?

But that doesnt seem right. I dont think it will always work just because it worked in a few circumstances.
You find one specific value of n that works, then show that the theorem works for n + 1 also. (Which then implies it works for all whole numbers greater than or equal to n by the Principle of Mathematical Induction.)

-Dan

6. Originally Posted by topsquark
You find one specific value of n that works, then show that the theorem works for n + 1 also. (Which then implies it works for all whole numbers greater than or equal to n by the Principle of Mathematical Induction.)

-Dan
Oh ok. Would you mind giving me the Principle of Mathematical Induction? And maybe a very short explanation? Or does it just involve substituting n with values?

7. Try this for starters. There are a variety of examples on this site and the web in general.

-Dan

8. Hello, polymerase!

Prove by induction: . $3^{3n} + 2^{n+2}$ is divisible by 5.
Verify $S(1)$

. . $3^3 + 2^3\:=\:27 + 8 \:=\:35$ . . . true!

Assume $S(k)$ is true

. . $3^{3k} + 2^{k+2} \;=\;5a$ for some integer $a$. . [1]

We want to show that: . $3^{3k+3} + 2^{k+3}$ is divisible by 5.

Add $26\!\cdot\!3^{3k} + 2^{k+2}$ to both sides of [1]

. . $3^{3k} + 26\!\cdot\!3^{3k} + 2^{k+2} + 2^{k+2} \;= \;5a + 26\!\cdot\!3^{3k} + 2^{k+2}$

We have: . $27\!\cdot\!3^{3k} + 2\!\cdot\!2^{k+2} \;= \;5a + 25\!\cdot\!3^{3k} + 3^{3k} + 2^{k+2}$

. . . . . . . . . $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}$

. . . . . . . . . $3^{3k+3} + 2^{k+3} \;=\;10a + 25\!\cdot\!3^{3k} \;=\;5\left(2a + 5\!\cdot\!3^{3k}\right)$

Therefore: . $3^{3k+3} + 2^{k+3}$ is divisible by 5.

The inductive proof is complete.
.

9. Originally Posted by ThePerfectHacker
What does this have to do with Mathematical Induction? I'm afraid you've lost me.

-Dan

10. Originally Posted by topsquark
What does this have to do with Mathematical Induction? I'm afraid you've lost me.

-Dan
induction is used in the fifth post on the page, the post by TPH that starts off talking about the Well-Ordered principle. it's hard to relate the specific example to the problem here, but it may serve as a model of how induction is used

11. Originally Posted by Jhevon
induction is used in the fifth post on the page, the post by TPH that starts off talking about the Well-Ordered principle
Ah! Thank you.

-Dan