# Induction question

1. Feb 2, 2006

### Kamataat

Prove by induction that $$2^{2^n}+1$$ always ends in 7 for all n > 1 (true for n = 2).

I couldn't figure out anything to do with the last digit being 7, so I looked the case that $$2^{2^n}$$ ends in 6 for all n > 1, which is also true for n = 2.

Suppose it's true for n = k:

$$2^{2^{k+1}}=2^{2^k\cdot 2}=(2^{2^k})^2$$

Now, since by assumption $$2^{2^k}$$ ends in 6, its 2nd power also ends in 6 since 6x6=36. Hence $$2^{2^n}+1$$ ends in 7 for all n > 1.

Correct or not?

- Kamataat

2. Feb 2, 2006

### HallsofIvy

Staff Emeritus
Yes, that's perfectly good. Obviously n+ 1 will end in 7 if and only if n ends in 6.

You could, just as easily, say "Suppose $2^{2^k}+1$ ends in 7 for some k. Then $2^{2^k}$ ends in 6. Therefore, $2^{2^{k+1}}= (2^{2^k})^2$ also ends in 6 and so $2^{2^{k+1}}+ 1$ ends in 7".

Last edited: Feb 2, 2006
3. Feb 2, 2006

### Benny

I think what you've done is correct. Here is how I would set it out. I'm not sure if it's correct though.

Base case, assume true for n = so that $2^{2^k } \equiv 6\left( {\bmod 10} \right)$

Using the hypothesis:

$$2^{2^{\left( {k + 1} \right)} } \equiv 2^{2\left( {2^k } \right)} \equiv \left( {2^{2^k } } \right)^2 \equiv \left( 6 \right)^2 \equiv 6\left( {\bmod 10} \right)$$

I think the result follows from that.

4. Feb 2, 2006