Induction Proof Problem

**uconn711** · October 25th 2007, 04:34 PM

I'm trying to prove using induction that 5^n-2^n is divisible by 3 for all values of n. I'm used to using induction to get k+1 within an expression that verifies a given formula, and have never used it to try and get to an answer divisible by 3.

So far I have 1 in the truth set because 5^1-2^1=5-2=3
And with a value k in the truth set
5^(k+1)-2^(k+1)=5(5^k)-2(2^k)
but don't know how i can further manipulate this or if i'm even on the right track.

If anyone could show me where to go from here i would be very grateful.

**Opalg** · October 26th 2007, 12:24 AM

Originally Posted by uconn711

I'm trying to prove using induction that 5^n-2^n is divisible by 3 for all values of n. I'm used to using induction to get k+1 within an expression that verifies a given formula, and have never used it to try and get to an answer divisible by 3.

So far I have 1 in the truth set because 5^1-2^1=5-2=3
And with a value k in the truth set
5^(k+1)-2^(k+1)=5(5^k)-2(2^k)
but don't know how i can further manipulate this or if i'm even on the right track.

Start by writing down what it means to say that k is in the truth set: 5^k-2^k is a multiple of 3, or in other words 5^k-2^k=3p, for some integer p.

Now you can write that as 5^k = 2^k +3p. Substitute that expression for 5^k into the right-hand side of the equation 5^(k+1)-2^(k+1)=5(5^k)-2(2^k), and see where that leads you.

**Soroban** · October 26th 2007, 11:14 AM

Hello, uconn711!

Use induction to prove: . $5^n-2^n$ is divisible by 3 for all values of $n.$

Verify $S(1)\!:\;\;5^1 - 2^1 \:=\:3$ . . . True!

Assume $S(k)$ is true: . $5^k - 2^k \:=\:3a$ .for some integer $a$ .

Add $4\!\cdot\!5^k - 2^k$ to both sides;

. . $\underbrace{5^k + 4\!\cdot\!5^k} - \underbrace{2^k - 2^k} \:=\:3a + 4\!\cdot\!5^k - 2^k$
. . $(1 + 4)\!\cdot\!5^k - 2\!\cdot\!2^k \;=\;3a + \overbrace{3\!\cdot\!5^k + 5^k} - 2^k$

. . $5\!\cdot\!5^k - 2^{k+1} \;=\;3\left[a + 5^k\right] + \underbrace{5^k - 2^k}_{\text{This is }3a}$

Hence: . $5^{k+1} - 2^{k+1} \;=\;3\left[a + 5^k\right] + 3a \;=\;3\left[2a + 5^k\right]$ . . . a multiple of 3

Therefore: . $S(k+1)$ is true.
. . The inductive proof is complete.

**uconn711** · October 26th 2007, 01:15 PM

Ah, I had to think through that a couple times, but that method actually makes alot of sense; thanks alot!

**Plato** · October 26th 2007, 03:24 PM

I like this approach.
If $5^N - 2^N = 3m$ then take a look at
$\begin{array}{rcl} 5^{N + 1} - 2^{N + 1} & = & 5^{N + 1} - 5\left( {2^N } \right) + 5\left( {2^N } \right) - 2^{N + 1} \\ & = & 5\left( {\underbrace {5^N - 2^N }_{3m}} \right) + 2^N \left( {\underbrace {5 - 2}_3} \right) \\ \end{array} $

Thread: Induction Proof Problem

LinkBack

Thread Tools

Display

Induction Proof Problem

Similar Math Help Forum Discussions

Problem with proof by mathematical induction

Induction Proof Problem (for set union)

Extremely difficult induction proof problem

Mathemtical Induction Proof (Stuck on induction)

Confused by Induction Proof Problem

Search Tags