Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)


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{equation*} 1,2,3,4,1,2,3,4,5,1,2,3,4,5,2,3,4,5,6,2,3,4,5,6,1,2,3,4,5,2,3,4,5,6,\dots, \end{equation*} 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 loop—with 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.

Zori was losing her patience and was especially grumpy today “I don't see any value to any of this stuff. Who's going to pay me to find greatest common divisors?” Dave said “Nobody.” Alice said, “But maybe there are some principles here that have practical application.” Carlos joined in, saying “I think the basic principles behind establishing that a computer program does what you intend have a lot to do with induction and recursion.” Bob said “I don't understand. When I write a program, I just pay attention to details and after just a few corrections, they always work.” Alice was brutal “Maybe that's because you don't do anything complicated.” Carlos was more gentle “Big software projects might have hundreds of thousands of lines of code, and pieces of the final product might be written by different groups of programmers at different moments in time. Establishing correctness can be a very difficult task.” Zori's ears perked up as she thought she saw something in this last bit of conversation that might be a way to earn a salary.