6
$\begingroup$

I am confused as to how to solve this question.

For the Base case $n=1$, $(2^{2(1)} - 1)\,/\, 3 = 1$, base case holds

My induction hypothesis is: Assume $2^{2k} -1$ is divisible by $3$ when $k$ is a positive integer

So, $2^{2k} -1 = 3m$

$2^{2k} = 3m+1$

after this, I'm not quite sure where to go. Can anyone provide any hints?

$\endgroup$
2

6 Answers 6

9
$\begingroup$

Hint: If $2^{2k} - 1$ is divisible by $3$, then write

\begin{align*} 2^{2(k + 1)} - 1 &= 2^{2k + 2} - 1 \\ &= 4 \cdot 2^{2k} - 1 \\ &= 4 \cdot \Big(2^{2k} - 1\Big) + 3 \end{align*}

Do you see how to finish it up?


This technique is motivated by attempting to shoehorn in the term $2^{2k} - 1$, since that's the only piece we really know anything meaningful about.

$\endgroup$
2
  • $\begingroup$ Thank you, I can clearly see where I was going wrong. I kept ending up with 6m-1 and couldn't figure out how to get the answer I wanted. $\endgroup$
    – Sarah
    Jan 23, 2014 at 2:27
  • 1
    $\begingroup$ Note that this is a proof by induction. $\endgroup$
    – zz20s
    Jan 22, 2016 at 22:11
4
$\begingroup$

Note that $$\sum_{k=0}^{n-1} 4^k={4^n-1\over4-1}$$ is an integer.

$\endgroup$
1
  • $\begingroup$ Ha! Very nice, Christian. $\endgroup$ Jan 22, 2016 at 21:36
1
$\begingroup$

If we rewrite $2^{2k}-1$ in binary, we get the number $$2^{2k}-1=\underset{\text{$2k$-times}}{\underbrace{111111\dots11}}$$ consisting of $2k$ ones. (I.e., there are $k$ pairs of them.)

If this is not clear immediately, just notice that by adding one to the above number we get $$2^{2k}=1\underset{\text{$2k$-times}}{\underbrace{000000\dots00}}.$$

Now we can simply notice that this number can be obtained as the sum (written in binary) $$ \begin{align*} 110000\dots00&+\\ 1100\dots00&+\\ \dots&+\\ 11&=\\ 111111\dots11& \end{align*} $$ where each summand is multiple of $3=(11)_2$.

$\endgroup$
1
$\begingroup$

A Combinatorial/Algebraic-Geometric Solution

Consider the operation $*$ on $S:=\{0,1,2,3\}$ defined as follows:

  1. $*$ is commutative with identity $1$,
  2. $a*0=0=0*a$ for all $a\in S$,
  3. $2*2=3$, $3*3=2$, and $2*3=1=3*2$.

Now, the elements of $S^n\setminus\{\boldsymbol{0}\}$, where $\boldsymbol{0}:=(0,0,\ldots,0)$ with $n$ zeros, can be partitioned into subsets with $3$ elements of the form $\left\{\mathbf{v},2*\mathbf{v},3*\mathbf{v}\right\}$, where $\mathbf{v} \in S^n\setminus\{\boldsymbol{0}\}$. Here, we define $a*\mathbf{v}=\left(a*v_1,a*v_2,\cdots,a*v_n\right)$ if $\mathbf{v}=\left(v_1,v_2,\ldots,v_n\right) \in S^n$ and $a\in S$. The number of partitioning subsets is then $\frac{4^n-1}{3}=\frac{2^{2n}-1}{3}$, which must be an integer.

Remark: In fact, $S$ can be identified with $\mathbb{F}_4$ and $*$ is simply the usual multiplication on $\mathbb{F}_4$. The number $\frac{2^{2n}-1}{3}$ is precisely the number of elements of the projective space $\mathbb{PF}_4^{n-1}$.


An Algebraic Solution

Prove that the polynomial $\left(1+x+x^2+x^3\right)^n-1$ is divisible by $1+x+x^2$. As $1+x+x^2\in\mathbb{Z}[x]$ is monic and $\left(1+x+x^2+x^3\right)^n-1\in\mathbb{Z}[x]$, the quotient $\frac{\left(1+x+x^2+x^3\right)^n-1}{1+x+x^2}$ is a polynomial in $\mathbb{Z}[x]$. What happens when $x$ is substituted by $1$?


PS: I know that the OP asks for an inductive proof, but there are many interesting ways to overkill this problem. There is also a geometric solution, using the tiling of an $n$-dimensional hypercube of side length $4$ with tiles consisting of I-shaped $3$-blocks (I-shaped trominos) and one $1$-block (monomino), and this proof is inductive.

$\endgroup$
1
$\begingroup$

$$2^{2k} - 1 = (2^k)^2 - 1 = (2^k - 1) (2^k +1) $$

For any even number $2^k$, after divided by 3, there are two possible remainders, 1 or 2.

If the remainder of $2^k$ divided by 3 is 1, then $2^k - 1$ is divisible by 3.

If the remainder of $2^k$ divided by 3 is 2, then $2^k + 1$ is divisible by 3.

So no matter what remaider is, $(2^k - 1)(2^k +1)$, is divisible by 3, so as $2^{2k}$.

$\endgroup$
0
$\begingroup$

Here are a couple graphical demonstrations of induction for this problem, based on tiling square regions with L-shaped trominoes:

http://www.mathdemos.org/mathdemos/tromino/tromino.html https://www.math.hmc.edu/funfacts/ffiles/20002.4.shtml

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.