Question

Show that 2^2n-1 +1 is divisible by 3 for all n > 1.

Answer 1

The proof makes use of congruences as follows:

Explanation:

We can prove this result using congruences module 3. First of all we shall show that

`2^(2n-1)\equiv 2 \pmod{3}` for all
`n\in \mathbb{N}`. By induction we have

1. 
   `n=2`. For
   `n=2` we have
   `2^(4-1)=8\equiv 2 \pmod{3}`
2. Suppose that the statement is true for
   `n=k` and let's prove that it is also true for
   `n=k+1`. In fact,
   `2^(2(k+1)-1)=2^(2k-1+2)=2^(2k-1)2^(2)\equiv 2\cdot 2^(2)\equiv 8 \equiv 2 \pmod{3}`

Then induction we proved that
`2^(2n-1)\equiv 2 \pmod{3}` for all
`n>1`. Then

`2^(2n-1)+1\equiv 2+1\equiv 3\equiv 0 \pmod{3}`

From here we conclude that the expression
`2^(2n-1)+1` is divisible by 3.