Skip to main content
Logo image

Applied Combinatorics

Section 3.3 The Meaning of Statements

Have you ever taken standardized tests where they give you the first few terms of a sequence and then ask you for the next one? Here are some sample questions. In each case, see if you can determine a reasonable answer for the next term.
  1. \(\displaystyle 2,5,8,11,14,17,20,23,26,\dots\)
  2. \(\displaystyle 1,1,2,3,5,8,13,21,34,55,89,144,233,377,\dots\)
  3. \(\displaystyle 1,2,5,14,42,132,429,1430,4862,\dots\)
  4. \(\displaystyle 2,6,12,20,30,42,56,72,90,110,\dots\)
  5. \(\displaystyle 2,3,6,11,18,27,38,51,\dots\)
Pretty easy stuff! OK, now try the following somewhat more challenging sequence. Here, we’ll give you a lot more terms and challenge you to find the next one.
\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*}
Trust us when we say that we really have in mind something very concrete, and once it’s explained, you’ll agree that it’s “obvious.” But for now, it’s far from it.
Here’s another danger lurking around the corner when we encounter formulas like
\begin{equation*} 1+2+3+\dots+n = \frac{n(n+1)}{2} \end{equation*}
What do the dots in this statement mean? In fact, let’s consider a much simpler question. What is meant by the following expression:
\begin{equation*} 1+2+3+\dots+6 \end{equation*}
Are we talking about the sum of the first six positive integers, or are we talking about the sum of the first \(19\) terms from the more complicated challenge sequence given above? You are supposed to answer that you don’t know, and that’s the correct answer.
The point here is that without a clarifying comment or two, the notation \(1+2+3+\dots+6\) isn’t precisely defined. Let’s see how to make things right.
First, let \(f:\posints\longrightarrow\posints\) be a function. Set
\begin{equation*} \sum_{i=1}^1 f(i) = f(1) \end{equation*}
and if \(n>1\text{,}\) define
\begin{equation*} \sum_{i=1}^n f(i) = f(n)+\sum_{i=1}^{n-1}f(i) \end{equation*}
To see that these two statements imply that the expression \(\sum_{i=1}^nf(i)\) is defined for all positive integers, apply the Well Ordered Property to the set of all positive integers for which the expression is not defined and use the recursive definition to define it for the least element.
So if we want to talk about the sum of the first six positive integers, then we should write:
\begin{equation*} \sum_{i=1}^6 i \end{equation*}
Now it is clear that we are talking about a computation that yields \(21\) as an answer.
A second example: previously, we defined \(n!\) by writing
\begin{equation*} n! = n\times (n-1)\times (n-2)\times\dots\times3\times2\times 1 \end{equation*}
By this point, you should realize that there’s a problem here. Multiplication, like addition, is a binary operation. And what do those dots mean? Here’s a way to do the job more precisely. Define \(n!\) to be \(1\) if \(n=1\text{.}\) And when \(n>1\text{,}\) set \(n! = n(n-1)!\text{.}\)
Definitions like these are called recursive definitions. They can be made with different starting points. For example, we could have set \(n!=1\) when \(n=0\text{,}\) and when \(n>0\text{,}\) set \(n!=n(n-1)!\text{.}\)
Here’s a code snippet in SageMath, which is based on Python, so this also works as Python code.
What is the value of sumrecursive(4)? (In order to make sure you understand how this recursive function works, calculate out sumrecursive(4) should be by hand before modifying the SageMath cell above.) Does it make sense to say that sumrecursive(n) is defined for all positive integers \(n\text{?}\) Did you recognize that this program provides a precise meaning to the expression:
\begin{equation*} 2+3+6+11+18+27+38+51+\dots +(n^2-2n+3) \end{equation*}