Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

While learning about various forms of mathematical proofs, my teacher presented an example question suitable for proof by exhaustion:

Prove that all $2^n$ end in 2, 4, 6 or 8 ($n\in\mathbb{Z},n>0$)

I have made an attempt at proving this, but I cannot complete the proof without making assumptions that reduce the rigour of the answer.

All positive integral powers of two can be represented as one of the four cases ($k\in\mathbb{Z},k>0$, same for $y$):

  • $2^{4k}=16^k=10y+6$
  • $2^{4k+1}=2*16^k=10y+2$
  • $2^{4k+2}=4*16^k=10y+4$
  • $2^{4k+3}=8*16^k=10y+8$

The methods of proving the four cases above were similar; here is the last one:

$8*16^k=8*(10+6)^k$

Using binomial expansion,

$8*(10+6)^k=8*\sum\limits_{a=0}^k({k \choose a}10^k6^{k-a})$

All of the sum terms where $a\neq0$ end in zero, as they are a multiple of $10^k$, and therefore, a multiple of 10. The sum term where $a=0$ is $6^k$, because ${k\choose0}=10^0=1$. Therefore, the result of the summation ends in six.

Assuming that all positive integral powers of six end in six, and eight multiplied by any number ending in six ends in eight, all powers of two of the form $2^{4k+3}$ end in eight.

That conclusion doesn't seem very good because of the two assumptions I make. Can I assume them as true, or do I need to explicitly prove them? If I do need to prove them, how can I do that?

share|improve this question
2  
It is not true, since $n\ge 0$ explicitly allows $n=0$ and $2^0$ ends in $1$. –  Henning Makholm Mar 22 '12 at 12:47
    
Sorry, that was actually a typo; the original question only stated that $n>0$. I've corrected the question. –  Delan Azabani Mar 22 '12 at 21:42

3 Answers 3

up vote 5 down vote accepted

You do need to prove them.

  • If $6^n=10k+6$, then $6^{n+1}=60k+36= (6k+3)10+6$, which also has $6$ in the units digit. Use induction.
  • If $n=10k+8$, then $6n=60k+48=(6k+4)10+8$, which also has $8$ in the units digit.

There is an easier way of "exhaustion" in my opinion: proof by contradiction. For example, assume that $2^n=10k$. This would mean that $5|2^n$ (five divides the power of two), an impossibility, so no power of two can end in $0$. For the rest (units digits 1, 3, 5, 7, 9), show that even numbers (that is, the multiples of two) are closed under addition and subtraction (for example $2n-2m=2(n-m)$), so if e.g. $2^n=10k+1$, then we would expect $2^n-2(5k)$ to be even, but 1 is not a multiple of 2.

share|improve this answer
    
Thanks for the answer! If I do prove the two assumptions, is my proof otherwise valid? –  Delan Azabani Mar 22 '12 at 11:53
2  
@Delan: Note that, since you need induction to prove the statement about $6^n$, you might as well use induction on the original problem, which allows a far simpler proof. –  joriki Mar 22 '12 at 11:53
    
Interesting, I hadn't thought to approach the proof that way. I'll give it a go; thanks! –  Delan Azabani Mar 22 '12 at 11:54

If the decimal expansion of $2^n$ is $$10^m d_m + 10^{m-1} d_{m-1} +\cdots + 10d_1 + d_0$$ where $0\leq d_i \leq 9$ (ie the $d_i$ are the digits of the expansion), then we can write $$2^n=10k+d_0$$ where $$k=10^{m-1}d_m + 10^{m-2}d_{m-1}+\cdots + d_1$$

Therefore, $d_0=2^n-10k$, implying that $d_0$ is even (why?), and hence $d_0\in \{0,2,4,6,8\}$. The argument given by anon knocks out the possibility that $d_0=0$ (no power of 2 can be a multiple of 10). Thus, $d_0\in \{2,4,6,8\}$.

share|improve this answer

Hint $\ $ mod $10,\:$ the powers of $\:2\:$ repeat in a cycle of length $4,\:$ starting with $2,\:$ since

$$\rm 2^{K+4} = 2^K(1+15) = 2^K + 30\cdot2^{K-1}\equiv\: 2^K\ \ (mod\ 10)\quad for\quad K\ge 1$$

Now it suffices to prove by induction that if $\rm\:f:\mathbb N\to \mathbb N = \{1,2,3\ldots\}\:$ then

$$\rm f(n+4)\: =\: f(n)\ \ \Rightarrow\ \ f(n)\in \{f(1),\:f(2),\:f(3),\:f(4)\}$$

Informally: once a cyclic recurrence begins to loop, all subsequent values remain in the loop.

Similarly, suppose there are integers $\rm\:a,b,\:$ such that $\rm\: f(n+2)\ =\: a\:f(n+1) + b\:f(n)\:$ for all $\rm\:n\ge 1.\:$ Show that $\rm\:f(n)\:$ is divisible by $\rm\:gcd(f(1),f(2))\:$ for $\rm\:n\ge 1$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.