# How Would You Prove This?

The most mundane question on my number theory final turned out to be the most interesting. I asked my students to prove the following.

Theorem.  For any odd positive integer n, $$3^n + 1$$ is divisible by 4.

Try to come up with as many proofs of this as you can.  I will present four below.  The proofs themselves are not so interesting as what they say about the mind of the mathematician at work.  This innocent problem turned out to be a sort of mathematical Rorschach test.  Feel free to post any alternate proofs in the comments.

Proof 1 (induction).  The base case n=1 clearly holds, as $$3^1 + 1 = 4$$.

Now assume $$3^{2k-1} + 1= 4m$$ for some positive integer m.  We must show that $$3^{2k+1}+1$$ is expressible as four times an integer.

\begin{eqnarray*}
3^{2k+1}+1 &=& 3^2 3^{2k-1}+1 \\
&=& 3^2( 3^{2k-1}+1-1)+1 \\
&=& 3^2 (4m-1)+1 \\
&=& 4\times 3^2m-3^2+1 \\
&=& 4\times (3^2 m -2)
\end{eqnarray*}  QED

Proof 2 (binomial theorem).  Let $$C(n,b) = \frac{n!}{b! (n-b)!}$$ represent the coefficient of $$x^k$$ in the expansion of $$(x+1)^n$$ as promised by the binomial theorem.  For our proof, the main properties of C(n,b) we will need are C(n,0)=1 and C(n,1)=n.  We will apply the theorem with x=2.

\begin{eqnarray*}
1+3^{2k+1} &=& 1+(2+1)^{2k+1} \\
&=& 1+ C(2k+1,0)+C(2k+1,1)\times 2+ C(2k+1,2)\times 2^2+\cdots\\
& & +C(2k+1,2k+1)\times 2^{2k+1} \\
&=& 1+ C(2k+1,0)+C(2k+1,1)\times 2+ 4( C(2k+1,2)+\cdots\\
& &+C(2k+1,2k+1)\times 2^{2k-1})\\
&=& 1+1+(2k+1)\times 2 +4\times \mathrm{\ some\ integer} \\
&=& 4+4k+4\times \mathrm{\ some\ integer}, \\
\end{eqnarray*}

which is clearly divisible by 4. QED

Proof 3 (congruences).

Let k be a non-negative integer.

\begin{eqnarray*} 3^{2k+1}+1& =& (3^2)^k \times 3+1\\
&\equiv& 1^k \times 3 +1 \mathrm{\ (mod\ 4)}  \\
&\equiv& 3+1 \mathrm{\ (mod\ 4)} \\
&\equiv& 0 \mathrm{\ (mod\ 4)}  \end{eqnarray*}

So 3 raised to any odd positive power is congruent to 0 modulo 4, i.e. is divisible by 4.

QED

Proof 4 (by cases).  There are four possible remainders on division by 4: 0,1,2, and 3.   $$3^{2k-1} + 1$$ is clearly even, leaving only 0 and 2 as possibilities.

Suppose for contradiction that  $$3^{2k-1} + 1$$ is congruent to 2 modulo 4.

\begin{eqnarray*} 3^{2k+1}+1& \equiv&2 \mathrm{\ (mod\ 4)} \\
3^{2k+1}&\equiv& 1 \mathrm{\ (mod\ 4)}  \\
3\times (3^{2})^k&\equiv& 1 \mathrm{\ (mod\ 4)} \\
3\times 1^k&\equiv& 1 \mathrm{\ (mod\ 4)} \\
3&\equiv& 1 \mathrm{\ (mod\ 4)}.
\end{eqnarray*}

The last step is clearly a contradiction.The only remaining possibility is that  $$3^{2k-1} + 1$$ is congruent to 0 modulo 4. QED

Proof 1 is the reason I put this problem on my final.  I was looking for a result that could be proved with a fairly straightforward induction argument.  I did not specify that induction could or should be used, however.  About half of the students who attempted this one used induction.  Inductive arguments have an elegance to them, capturing the recursive structure of a result, but they can obscure some algebraic features.

I wanted to explore what other options might be available.  Proof 2 is the first non-induction argument I found, which struck me funny.  The statement must have triggered some memory from my discrete math teaching days where this cute trick of using the binomial theorem to convert powers of 3 into powers of 2 came up a lot.  Unsurprisingly, no students did it this way.

The reason it’s odd that it was my go-to proof — besides it being a somewhat obscure trick — is that I had just spent two months teaching students about modular arithmetic.  Proof 3 emerged after I recognized that Proof 2 was a little weird and there should be a fairly straightforward application of modular arithmetic.  Some students came up with Proof 3, or something very much like it.

Proof 4 barely counts because it’s really just Proof 3 with more noise.   Once you whittle down to the one case you need to eliminate, you end up with a modular arithmetic argument not substantively different from what you need if you just prove it directly.  Yet it was the approach chosen by many of the weaker students. Most of the students who went with Proof 4 were unable to find the contradiction in the case to be eliminated.  I wonder if there are students who started looking at cases, did Proof 4 more or less as shown, but then realized in rewriting that they could drop all of the cases and just do Proof 3.

I think this points to a nice indicator of mathematical sophistication.  Many students love proofs by cases because the cases tend to be fairly straightforward individually.  More experienced mathematicians tend to avoid them.  One reason is that these proofs do not generalize well to larger numbers of cases; just imagine if this were a statement about divisibility by 100!   Another reason is that what a mathematician really wants from a proof is a deeper understanding of the problem.  Proofs by cases tend to fracture the problem into too many pieces to glean much insight.  In other words, they tend to be inelegant.  But elegance is an acquired appreciation.  And of course, there are many examples of Big Theorems such as the Four Color Theorem that are massive computer-driven case checks that have challenged mathematicians to reconsider what “proof” really means.

This was the final exam, the most summative of summative assessments, so I won’t be able to follow up, but I would love to probe the students who took the cases approach further.  Students are focused primarily on correctness — rightly so, perhaps — but they need to see what the argument really is.  They don’t need to see that Proof 3 is better, but they need to see why Proof 4 is basically the same.  A student who does not see the value in finding more than one solution is missing something important in his or her understanding of mathematics.

Bill Wood is a mathematics professor and tweets on math and other matters as @MathProfBill.

#### A request!

Thank you for reading! I want to keep in touch with my readers. If you are interested, please have a look here.

Do you enjoy this blog?
Consider supporting with a contribution! ## 9 thoughts on “How Would You Prove This?”

1. Andy Novocin

After about 10 seconds I had proof 3. Whenever anyone brings up modulo 4 I start looking for squares. Same whenever you want to prove something is always positive.

So in this case if we swap 3 for $x$ then the theorem becomes when is $x^n + 1$ divisible by 4, which will work for $x \equiv -1 \mod{4}$. In the same vein $x = -1$ is the positive/negative breaking point.

2. Nick Raffin

Here is another one.

Write 3^(2n+1)+1 in base 3 notation as 100…01. Similarly, write 4 as 11.

Then it is easy to see, though tedious to write down, that long division never leaves a remainder.

1. Bill Wood

I like this one! You’re right that it might be tedious sell, but this is definitely a different way of looking at it. Nice.

3. Nick Raffin

Sorry, in my posting, the expression 4 ( 3^(2n-1) ) should read 8 ( 3^(2n-1) ). Oh well…. typical non-professional waffle.

1. Bill Wood

Nice. This is basically the same as the induction argument in the post, but reorganized as a recurrence relation.

I wonder if this approach has some pedagogical value as a different way to think of induction. Students usually learn it in a way consistent with the proof I gave. But maybe we should emphasize more that there is an underlying sequence a_n behind any inductive argument. Your approach brings that to light, but it may also complicate things a bit.

4. Nick Raffin

Consider the sequence, a_n = 3^(2n+1) + 1, for n=0,1,2….

Then a_n – a_(n-1) = ( 3^(2n+1) + 1 ) – ( 3^(2n-1) + 1) = 4 ( 3^(2n-1) ).

The result then follows by induction, since a_0 = 4.

5. Bill Wood

Incidentally, Proofs 3 and 4 can be tightened if you observe that 3 = -1 (mod 4). Then 3^odd +1 = (-1)^odd+1 =-1+1 =0.

6. Bill Wood Post author

My problem with Proof 4 is that it’s not *really* a proof by cases in that it offers no real insight into the problem beyond the slicker Proof 3.

However, if there were a proof by cases that really got at the small size of the problem, I’d be quite happy. And there is something to be gleaned there, thinking of divisibility by four as something like being “super-even,” whereas congruent to 2 mod 4 is merely “even.”

So maybe we need Proof 5.

7. Manan Shah

Bill,

Should I feel shameful in saying that I liked Proof #4? I think proving by cases is a great way to start understanding a problem. To me it’s a giant set of “what if this …”, “what if that …” then eventually we start to see patterns and see how to group things and generalize.

I feel that using cases allows the “prover” to get a handle on what may feel like a large unwieldy problem by breaking it into smaller problems.

What say you?