Discrete Math Final: Question 10

December 13, 2010 in Exercises

10. Prove by induction that for all positive integers $n$ , one has $3 | 4^n - 1$ .

Proof: Let P(n) denote the proposition $3 | 4^n -1$ .

Base Case For n = 1, we have 3|4^1 – 1; P(1) is true.

Induction Step Assume for some $k \in {\Bbb Z}^+$ that P(k) is true: $3 | 4^k - 1$ . Then $4^k -1 = 3a$ for some integer a; rewrite this as $4^k = 3a + 1$ . We then have

$4^{k+1} - 1 =$
$4\cdot 4^k - 1 =$
$4\cdot(3a +1) - 1=$
$12a-3=$
$3(4a-1)\,.$

But $4^{k+1} - 1 = 3(4a -1)$ implies $3 | 4^{k+1}$ (i.e., P(k+1)). This completes the induction and the proof.

Remarks
My class saw variants on this problem… 6 | 7^n – 1 (\forall n \in Z^+) for example… in (i) a homework and (ii) a previous test. So they were pretty well-prepared for an induction problem of this type. (Know ye not this parable? and how then will ye know all parables?)

Here’s another, somewhat informal, proof of the same result:
$x^n - 1 = (x-1)\cdot(x^{n-1} + x^{n-2} + \dots + x^0)$
(as one sees by “multiplying out”… all but two terms “cancel”). Put 4 in for x; done. I call this proof “informal” because wherever there are dot-dot-dots, there’s generally an induction hiding somewhere if we want to get technical. Anyhow, I shared this proof with the class.

Also the (equally informal) “handshake problem” proof that $\sum_{i=1}^n i = {{n(n+1)}\over 2}$ . But, alas, I didn’t require induction proofs from them involving summations (“sigma” notation $\sum$ ). Another one of the many topics everybody seems to want their students to’ve already learned about somewhere else (in this case, Calc II most likely). It takes time to get students up to speed with summations. Different amounts of time for different students. I was something of a sigmaphobe myself as an undergrad. (I was even worse with “determinants” [another very useful algebraic gizmo that math departments don't want to teach much about explicitly...].)

The string of equations in my notes hitherto is a little different; rather than solve 4^k – 1 = 3a to get 4^k = 3a + 1, I’ve consistently used the trick of “adding 0″:
$4^{k+1} - 1 =$
$4\cdot 4^k - 1 =$
$4\cdot 4^k - 4 + 3=$
$4(4^k - 1) + 3=$
$4(3a) + 3=$
$3(4a + 1)\,.$
(We’ve “added -4 + 4″ in the third line to produce a “4^k -1″ in the code… but this is needlessly tricky and, I expect, threw a few students off the track. I got the “right” way from a student paper.)

Like this:

Be the first to like this post.

2 Replies

jd2718

December 19, 2010 at 4:13 pm

I used to get scolded for misordering my work, but I think it is all there (and I am hoping my bad tex works)

Jonathan

$3a + 1 = 4^k$
$4^{k+1} = 4^k \times 4$
$= (3a+1)4$
$= 12a + 4$
$= 12a + 3 + 1$
$= 3(4a+1) + 1$
$4^{k+1} - 1 = 3(4a+1)$

Reply
vlorbik

December 21, 2010 at 1:30 pm

perfectly clear (once it loads; it failed
altogether… then displayed about half…
and only now [after i'd checked the
source code!] showed all seven lines).

shove it into the appropriate
“induction template” and you’d've had
a perfect score on this one (with bonus
points for taking on the TeX).

if i want to quibble… and who *doesn’t*?…
i’d insist on some language (“recall that…”;
“so…”; “it follows that…” might do nicely)
to introduce each new left-hand-side.
failing this, an extra line between ‘em
would improve readability somewhat
in my opinion. none of this is “points-off”
stuff in the context (i had to make a
certain amount of fuss about “using
complete sentences”… usually in the
form of docking students for not using
sentences *at all*… in writing up proofs;
obviously no blame attaches for the
fragment at hand).

hmm. the net just ate a bunch of this comment.
posting while the getting’s good.

Reply