# Induction Proof again :(

• Nov 20th 2007, 05:45 PM
Jimbobobo
Induction Proof again :(
http://img255.imageshack.us/img255/3518/aa2gc9.jpg

Hi all,
Once again I'm pretty stumped at this one.
3^3 = 27
3^4 = 81
3^5 =243
3^6 = 729
3^7 = 2187

Now these are the same practically. An even second to last digit and a seven as the last digit. So the pattern will loop. Just proving it seems a right pain! :( Any help at all would be appreciated.
• Nov 20th 2007, 11:41 PM
CaptainBlack
Quote:

Originally Posted by Jimbobobo
http://img255.imageshack.us/img255/3518/aa2gc9.jpg

Hi all,
Once again I'm pretty stumped at this one.
3^3 = 27
3^4 = 81
3^5 =243
3^6 = 729
3^7 = 2187

Now these are the same practically. An even second to last digit and a seven as the last digit. So the pattern will loop. Just proving it seems a right pain! :( Any help at all would be appreciated.

I can't see your linked image, and I doubt anyone else can either.

RonL
• Nov 21st 2007, 02:00 AM
Jimbobobo
Prove by induction that in the decimal form 3^n, the second from end digit is even.
• Nov 21st 2007, 05:44 AM
CaptainBlack
Quote:

Originally Posted by Jimbobobo
Prove by induction that in the decimal form 3^n, the second from end digit is even.

Base case n=3 then 3^3=27 and so it is true that the second least significant digit is even.

Suppose it true for some $k$, that is the second least significant digit is even.
Now $3^k$ is odd, and not divisible by $5$, so the least significant digit is one of:

$1,\ 3,\ 7,\ 9.$

Now the carry when these are multiplied by $3$ is even (either $0$ or $2$), and
$3$ times the second least significant digit of $3^k$ is even. Even plus an even is
even so the second least significant digit of $3^{3+1}$ is even, which
completes the induction step.

So we have proven that for all $n>2$ the second least significant digit is even.

RonL
• Nov 21st 2007, 08:17 AM
Soroban
Hello, Jimbobobo!

I have a slight variation of RonL's solution.

Quote:

Prove by induction that in the decimal form of $3^n$, the tens-digit is even.
We note that $3^n$ ends in: 1, 3, 7, or 9.

And $3^{n+1}$ ends in: 03, 09, 21, or 27.
. . Hence, there is a "carry" of either 0 or 2.

Verify $S(1)\!:\;\;3^1 \:=\:03$ . . . true!

Assume $S(k)\!:\;\;3^k$ has an even tens-digit.

. . This means that: . $3^k$ is of the form: . $10(even) + \{1,3,7,9\}$

. . Hence: . $3^k \:=\:10(even) + \{1,3,7,9\}$

Multiply by 3: . $3^{k+1} \;=\;3\left[10(even) + \{1,3,7,9\}\right]$

. . $\text{and we have: }\;3^{k+1} \;=\;\underbrace{10\!\cdot\!3(even)}_{\text{even}} + \underbrace{3\!\cdot\!\{1,3,7,9\}}_{\text{carry: 0 or 2}}$

$\text{Hence: }\;3^{k+1} \;=\;10\cdot\underbrace{[3(even) + \{0,2\}]}_{\text{even}} + \{1,3,7,9\}$

Therefore, $3^{k+1}$ has an even tens-digit.
. . The inductive proof is complete.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

I had this wild idea of using binary, but I got nowhere.

Consider: . $3 \:=\:11_2$

I thought that . $\left(11_2\right)^n$ would lead to a neat solution,
. . but I didn't find one.

Anyone care to give it a try?