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.