Discrete Math Final: Question 10

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=

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.

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.)


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


    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)

  2. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: