### Discrete Math Final: Question 10

**10.** Prove by induction that for all positive integers , one has .

**Proof:** Let P(*n*) denote the proposition .

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

**Induction Step** Assume for some that P(*k*) is true: . Then for some integer *a*; rewrite this as . We then have

But implies (*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:

(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 . But, alas, I *didn’t* require induction proofs from them involving summations (“sigma” notation ). 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”:

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

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

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.