1. ## Induction Proof Problem

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.

2. 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.

3. Hello, uconn711!

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

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

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

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

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

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

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

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

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

5. I like this approach.
If $\displaystyle 5^N - 2^N = 3m$ then take a look at
$\displaystyle \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}$