1
$\begingroup$

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?

  • 0
    Sorry, that was actually a typo; the original question only stated that n>0. I've corrected the question.2012-03-22

3 Answers 3

5

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

7

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

5

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.

  • 0
    Interesting, I hadn't thought to approach the proof that way. I'll give it a go; thanks!2012-03-22