Discussion

The group was debating the value of combinatorial proofs versus formal proofs by induction. Xing said that he actually preferred to do a proof by induction, as a combinatorial proof, it could be argued, wasn't really a proof. Dave mumbled Combinatorial proofs can always be made rigorous. They went back and forth for a while and then Alice said But the professor never explained that weird sequence \[\begin{aligned}\end{aligned}\] did he?

Dave was on a roll. He asked, Who has change for a dollar? but nobody understood why he would derail an argument over proofs when everybody had already paid for the coffee. Alice was more to the point You know Dave, sometimes I just don't understand why you say the things you do. Dave smiled (maybe it was more of a smirk) It's about making change. The terms in this sequence are the fewest number of coins required to make change. Bob said I don't get it. Dave continued The term \(a_n\) is the fewest number of U.S. coins required to total to \(n\) cents. Now everyone groaned, everyone except Carlos, who thought that at least this time, Dave was really clever.

Well, said Bob, that takes care of the strange sequence, but I still don't see any difference between induction and recursion. Dave couldn't keep quiet No one does. Xing thought differently and said In many programming languages, you try to avoid recursion, preferring to use loops instead. Otherwise, you wind up overloading the stack. As just one example, you can compute the greatest common divisor \(d\) of \(m\) and \(n\), as well as find \(a\) and \(b\) so that \(d=am+bn\) using a loopwith very little storage. The recursive approach discussed previously, with the inherent back tracking at the end, isn't really necessary. Yolanda was impressed with Xing's extensive programming experience and knowledge, but Alice was less so.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.