Question

If n >= 1 is an integer, prove that 2^(2n) - 1 is divisible by 3. Is there a formal way to prove this or can I just demonstrate it by plugging in n = 1,2,3,etc?

Answer 1

Proving by "plugging in" would involve an infinite number of cases.

Answer 2

try using induction

Answer 3

My problem is the only induction I know is plugging examples in!

Answer 4

OK, how did this happen: 4(2^(2n) - 1 + 1) - 1 = 4 - 1?

Answer 5

let it put it up again,
\[ 2^{2n + 2} - 1 = 4 \cdot2^{2n} - 1 = 4 (2^{2n} - 1 + 1)- 1\]
you know 3 divides 2^(2n) - 1 from assumption of induction.
\[ 4 (2^{2n} - 1) + 4 - 1 = 4 \cdot (2^{2n }-1) + 3 \]
since 3 divides both terms, it divides the whole thing.

Answer 6

also notice that
\[ 2^{2n} = 4^n = (3 + 1)^n = 3 \times (\text{something}) + 1 \]
you can use this to show that the reminder is 1

Answer 7

When I assume what I'm trying to prove to be true, what are the things I must do to make the whole argument valid?

Answer 8

do you know how to use induction?

Answer 9

this is my first problem in induction? Semester started this week.

Answer 10

avoiding induction, I will give another way,
\[f(n)= 4^n-1 \] the values of the sum of the digits of f(n) takes a function represented by g(n): \[3n+1 \]thus 3n+1-1 is divisible by 3

Answer 11

Oh!!
first put few values of n to show that it is true like, n=1,2,3 ... up to some number 'k'
if it holds for k+1 assuming it holds for k, then it holds for any finite number.

Answer 12

@Ahmad1 seeing that made me remember
\[ 4^n - 1 = (4 - 1)\cdot (1 + 4 + 4^2 + \dots + 4^{n-1})\]
it holds trivially

Answer 13

I don't understand this "the values of the sum of the digits of f(n) takes a function represented by g(n):3n+1"

Answer 14

@Ahmad1 what did I miss?

Answer 15

that is just another way of looking at the problem
4^n -1 = 3k
4^n = 3k + 1 for some integer k

Answer 16

Oh I see. I get it now. Thanks everybody.

Answer 17

have seen this theorem?
http://en.wikipedia.org/wiki/Fermat's_little_theorem

Answer 18

nope and I don't know modular arithmetic.