4
$\begingroup$
  • First part of the task is just to show that $(4^n-1)$ actually is divisible by 3 for n=1,2,3,4. No problem.
  • Second step: is to show that $(4^n -1) = (2^n-1)(2^n+1)$ No problem, just algebra.

  • Third step is to explain that $(2^n-1)$,$2^n$,$(2^n+1)$ is three consecutive numbers. And that only one is divisible by three.
    $2^n$ has two as a factor and is not divisible by 3. It can't be even. That leaves $(2^n-1)$ and $(2^n+1)$. The one with 3 as a factor seems to be random dependent on n.

  • Fourth step, tie it all together.
    Now, I'm not sure if I'm suppose to dig deeper into which of them is actually divisible by 3. Or has 3 as a factor. But knowing that one of them at the time (dependent on n) has indeed 3 as a factor implies that, in respect to the second step, 3 is a factor of $(4^n -1)$.

Is this all there is to it? Keep in mind that this is a really beginners proof task, not very formal. It's slightly funny going back to high school math after being scared to death by logic and descrete math at university-level. I just expect everything thing to be super complex.

  • 1
    @Algific I would suggest that you add your proof as an answer to this post. Be as complete as possible.2012-11-22

6 Answers 6

0

You can prove it very quickly by induction

  1. the expression is true for $n=0$, $n=1$, $n=2$ (you can check by hand)
  2. if the expression is true for $n$, then the expression is true for $n+1$.

Proof : $4^{(n+1)}-1 = 4\cdot (4^n-1)+3$, the first term is divisble by $3$ (step 2) and the second ($3$) also.

  • 0
    For some basic information about writing math at this site see e.g. [here](http://meta.math.stackexchange.com/questions/5020/), [here](http://meta.stackexchange.com/a/70559/155238), [here](http://meta.math.stackexchange.com/questions/1773/) and [here](http://math.stackexchange.com/editing-help#latex).2012-11-22
11

$(4^n-1)=(4-1)(4^{n-1}+4^{n-2}+...+4^{0})$

  • 1
    I agree with Asaf. Actually I only had a very quick look at the question and I thought that this was his own attempt to prove that $3|4^n-1$.2012-11-22
10

Once you have show that $4^n-1=(2^n+1)(2^n-1)$, and one of the two factors is divisible by three, you have got that $3$ divides $4^n-1$.

If $2^n-1$ is divisible by three, write it as $3k$ then $4^n-1=3k(2^n+1)$ and therefore it is divisible by three (you should figure out how to write the argument in full).

The other case, where $2^n+1$ is the one divisible by three is symmetric, but you should write the details for that case as well, to practice your writing.

  • 0
    @Algific: Wait, you want to tell me that you asked here a question from a home exam??2012-11-23
2

If $n$ is a positive integer,

using congruence formula, $4\equiv 1\pmod 3\implies 4^n\equiv 1^n\pmod 3\implies 4^n-1\equiv1-1\pmod 3$

Alternatively using binomial expansion, $4^n- 1=(1+3)^n-1$ $=(1+\binom n13+\binom n23^2+\cdots+\binom n{n-1}3^{n-1}+3^n)-1$ $=\sum_{1\le r\le n}3^r$ is clearly divisible by $3$

1

One of any three consecutive numbers is divisible by $3$. Now, $2^n-1$, $2^n$, and $2^n+1$ are consecutive, and $3$ can't divide $2^n$, so it must divide one of the others and hence their product.

  • 0
    More generally, if x divides y, then x divides the product of y and anything else.2012-11-23
1

we can prove that $3|(4^n-1),n\geq 1$ using mathematical induction, for $n=1$ $3|(4^1-1)$ the statement is true. Suppose that statement is true for $n=k$ i.e $3|(4^k-1)$ now we prove for $n=k+1$ $4^{k+1}-1=4^k4-1=3\times 4^k+(4^k-1)=$ obviousley $3\times 4^k$ can be divided by $3$ and $4^k-1$ is divisible by $3$ by assumption.