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