Discrete Math - The MKD Remix

Let’s examine a conjecture about a certain type of polygonal number, namely, square numbers.

Consider the image that shows 16 colored disks arranged as a square. By starting at the lower left corner of the square and grouping disks of the same color, we can count the total number of disks in the figure as follows. \begin{equation} \begin{aligned} 1 {} & = 1^{2} \\ 1 + 3 {} & = 4 = 2^{2} \\ 1 + 3 + 5 {} & = 9 = 3^{2} \\ 1 + 3 + 5 + 7 {} & = 16 = 4^{2} \\ \end{aligned} \end{equation}

Notice that the sum of the odd integers on the left-hand side of each equation is equal to the square of the number of odd integers on the left-hand side of the equation. This means that the predicate \[P(n)\text{: "The sum of the first } n \text{ positive odd integers is equal to } n^{2} \text{."}\] is a True statement for the natural numbers \(n \in \{ 1, 2, 3, 4 \},\) that is, each of the following four propositions is True:

In the following code snippet, function \(P\) implements the predicate used in this example. Recall that the predicate’s output is a proposition - the output is just a string of symbols and does not indicate whether the proposition is True or False.

Next, consider this second image, which shows how you could change the first image to one that can be used to prove that \(P(5)\) is True.
It’s easy to show that the proposition \(P(5)\) is True because you can just write out and verify that \(1 + 3 + 5 + 7 + 9 = 25 = 5^{2}.\) The goal here is to relate the proposition \(P(5)\) to the "preceding" proposition \(P(4),\) in a way similar to what was done for sequences of numbers in a recurrence relation.

Notice that the second image shows that, given the square arrangement of disks that has 4 disks along each side, we can construct a square arrangement that has 5 disks along each side by inserting 4 new disks above the top row, 4 new disks in a column to the right of the rightmost column, and 1 new disk in the upper right corner to completes the square arrangement.

In fact, there is nothing special about the number 4 in the previous paragraph: If \(k\) is any positive natural number and we have a \(k \times k\) square arrangement of disks, we can enlarge it to a \((k+1) \times (k+1)\) square arrangement of disks by inserting \(k\) disks above, \(k\) disks to the right, and \(1\) disk in the upper right corner of the \(k \times k\) square to complete the \((k+1) \times (k+1)\) square. Algebraically, we can account for the total number of disks in the \((k+1) \times (k+1)\) square by writing \[ k^{2} + k + k + 1 = (k+1)^{2} \] which is True for any natural number \(k\) (Just simplify the left-hand side and expand the right-hand side of the equation to see that the equation must be True.)

Based on this second image, we can make a conjecture that \(P(n)\) must be True for every positive natural number \(n.\) We now need to prove this conjecture.

Notice that if we combine the propositions

then we can build a proof for all the integers up to and including any value of \(n \in \mathbb{N}\) that we want.

For example, to prove \(P(1,\!000,\!000),\) we could start by asserting that \(P(1)\) is True, then apply the conditional \(P(k) \rightarrow P(k+1)\) along with the rule of inference modus ponens \(999,\!999\) times to prove that \(P(1,\!000,\!000)\) is True. This proof is finite - I never claimed that the proof would be short!

As an analogy, think of repeatedly applying modus ponens to the conditional as using a loop in code. We are just repeating the same argument \(( P(k) \land ( P(k) \rightarrow P(k+1) ) ) \rightarrow P(k+1)\) over and over again as the value of the variable \(k\) is incremented by 1 at the end of each loop iteration until we reach the value that we want to stop at. In the following code snippet, the user-defined function addTheOdds implements the computations used in this example’s argument. Notice how the Basis Step corresponds to validating the loop initialization and how the Induction Step corresponds to validating the output at the end of each loop iteration (assuming that the values were correct at the start of that loop iteration.) You can change the value of \(n\) in the code to confirm the truth value of \(P(n)\) for any integer you’d like, assuming you have enough time and computing resources.

Since we can now, in principle, build a proof of \(P(n)\) for any value of \(n \in \mathbb{N}\) that we could choose, we apply the rule of inference universal generalization to conclude that \((\forall \in \mathbb{N})P(n).\) That is, we have proven the proposition \[ \text{"For every positive natural number } n \text{, the sum of the first } n \text{ positive odd integers is equal to } n^{2} \text{."}\] Another way to look at this is to define \(s(n)\) to be the number of disks in a \(n \times n\) square arrangement of disks. We have shown that \(s(1) = 1\) and that \(s(k+1) = s(k) + 2k + 1\) for every positive natural number value of \(k,\) and have concluded that \(s(n) = n^{2}\) for every positive natural number \(n.\)

We will prove the following proposition using mathematical induction.

Notice first that since this needs to proven for any graph with any finite number of vertices and edges, it is a good candidate for proof by mathematical induction.

Which number should be one we use for induction?

So, to prove the theorem, let \(n\) represent the number of edges in a graph and let \(P(n)\) be the predicate \[P(n)\text{: "The sum of the degrees of the vertices for a graph with } n \text{ edges is equal to } 2 \cdot n \text{."}\] We will prove that \((\forall n \in \mathbb{N})P(n).\)

Basis Step: \(P(0)\) is the proposition "The sum of the degrees of the vertices for a graph with \(0\) edges is equal to \(2 \cdot 0.\)" since a graph with 0 edges is just a collection of isolated vertices, and each of the isolated vertices has degree 0, the sum of the degrees of the vertices must also be 0, which is 2 times the number of edges. This means that \(P(0)\) is True, and the Basis has been established.

Induction Step: First, we assume that the induction hypothesis \(P(k)\) is True for some positive natural number \(k\).

Secondly, we will prove that the conditional \(P(k) \rightarrow P(k+1)\) must be True, which means we can use modus ponens (or the equivalent tautology \(( P(k) \land ( P(k) \rightarrow P(k+1) ) ) \rightarrow P(k+1)\)) to show that \(P(k+1)\) is also True.

For the natural number \(k,\) the predicate \(P(k)\) is the proposition "The sum of the degrees of the vertices for a graph with \(k\) edges is equal to \(2 \cdot k.\)

Suppose that we have a graph with \(k\) edges. We insert one new edge \(e\) into the graph. There are, essentially, two possible cases to consider.

Notice that any graph with \(k+1\) edges can be built up this way from a graph that had \(k\) edges. So, using the fact that \(2 \cdot k + 2 = 2 \cdot (k+1),\) we have proven that "The sum of the degrees of the vertices for a graph with \(k+1\) edges is equal to \(2 \cdot (k + 1).\) That is, we have proven that \(P(k) \rightarrow P(k+1)\).

Conclusion Step: We have proven both the Basis Step and the Induction Step. Therefore, we can use universal generalization to conclude that \((\forall n \in \mathbb{N})P(n),\) which translates to "For all natural umber \(n,\) the sum of the degrees of the vertices for a graph with \(n\) edges is equal to \(2 \cdot n.\)"

Q.E.D.

Let \(P(n)\) be the predicate \[P(n)\text{: "The } n\text{th positive odd integer is equal to } 2n-1 \text{."}\] We will prove that \((\forall n \in \mathbb{N}_{>0})P(n),\) that is, for all positive integers \(n.\)
Notice that you can find evidence for the conjecture that \(k\text{th}\) positive odd integer is \(2k - 1\) by making a table and finding an algebraic formula that matches the table. See this appendix if you don’t remember how to do this.

Basis Step: \(P(1)\) is the proposition "The \(1\)th positive odd integer is equal to \(2(1)-1.\)" This is True since \(2(1)-1 = 1\), in spite of the poor English, which should use "\(1\)st" instead of "\(1\)th."

Induction Step: First, we assume that the induction hypothesis \(P(k)\) is True for some positive natural number \(k\). That is, we assume that "The \(k\)th positive odd integer is equal to \(2k-1\)" is True for some positive natural number \(k.\)

Secondly, we will prove that the conditional \(P(k) \rightarrow P(k+1)\) must be True, which means we can use modus ponens (or the equivalent tautology \(( P(k) \land ( P(k) \rightarrow P(k+1) ) ) \rightarrow P(k+1)\)) to show that \(P(k+1)\) is also True.

If the \(k\)th positive odd integer is equal to \(2k-1,\) then the \((k+1)\)th positive odd integer is obtained by adding \(2\) to \(2k-1,\) that is the \((k+1)\)th positive odd integer is equal to \((2k-1) + 2,\) which can be rewritten using algebra as \begin{equation} \begin{aligned} (2k-1) + 2 {} & = 2k - 1 + 2 \\ & = 2k + 2 - 1 \\ & = 2(k+1) - 1 \end{aligned} \end{equation}

We have proven that if \(k\)th positive odd integer is equal to \(2k-1\) then the \((k+1)\)th positive odd integer is equal to \(2(k+1)-1.\) That is, we have proven \(P(k) \rightarrow P(k+1)\).

Conclusion Step: We have proven both the Basis Step and the Induction Step. Therefore, we can use universal generalization to conclude that for all positive integers \(n,\) the \(n\)th positive odd integer is equal to \(2n-1.\)

Q.E.D.

Let \(P(n)\) be the predicate \[P(n)\text{: "The sum of the first } n \text{ positive odd integers is equal to } n^{2} \text{."}\] We will prove that \((\forall n \in \mathbb{N}_{>0})P(n).\)

Basis Step: \(P(1)\) is the proposition "The sum of the first \(1\) positive odd integers is equal to \(1^{2}.\)" If we allow a sum to have only one addend, then \(P(1)\) is True since \(1 = 1^{2}\), so \(P(1)\) can be used as the basis of our induction proof. If we want to be sure that there are least two addends in the sum, we can use \(P(2)\) as an additional basis. \(P(2)\) is the proposition "The sum of the first \(2\) positive odd integers is equal to \(2^{2}\)" which is True because \(1 + 3 = 2^{2}.\)

Induction Step: First, we assume that the induction hypothesis \(P(k)\) is True for some positive natural number \(k\).

Secondly, we will prove that the conditional \(P(k) \rightarrow P(k+1)\) must be True, which means we can use modus ponens (or the equivalent tautology \(( P(k) \land ( P(k) \rightarrow P(k+1) ) ) \rightarrow P(k+1)\)) to show that \(P(k+1)\) is also True.

Based on the formula for the \(k\text{th}\) positive odd integer, we can rewrite the sum of the first \(k\) positive odd integers \(1+3+...+(2k-1)\) using summation notation as \(\sum\limits_{i=1}^{k}(2i-1)\) and rewrite the predicate \(P(k)\) in algebraic form as \[ P(k): \sum\limits_{i=1}^{k}(2i-1) = k^{2}.\] Note that \(P(k)\) is still a proposition - it is stating that a certain equation holds.
A common error is to treat \(P(k),\) when written algebraically, as a function that gives numerical outputs, but this is incorrect. \(P(k)\) is still a predicate that gives propositions as outputs.

We can now prove that the conditional \(P(k) \rightarrow P(k+1)\) must be True using algebra. \begin{equation} \begin{aligned} \sum\limits_{i=1}^{k+1}(2i-1) {} & = \left(\sum\limits_{i=1}^{k}(2i-1)\right) + (2(k+1)-1) \\ & = k^{2} + (2(k+1)-1) \end{aligned} \end{equation} where we have substituted \(k^{2}\) for the sum \(\sum\limits_{i=1}^{k}(2i-1)\) based on the induction hypothesis.

Now we simplify this using algebra and show that it is the same as the right hand side. \begin{equation} \begin{aligned} \sum\limits_{i=1}^{k+1}(2i-1) {} & = k^{2} + (2(k+1)-1) \\ & = k^{2} + 2k + 2 - 1 \\ & = k^{2} + 2k + 1 \\ & = (k + 1)^{2}\\ \end{aligned} \end{equation}

We have proven that the equation \(1+3+...+(2k-1) = \sum\limits_{i=1}^{k}(2i-1) = k^{2}\) implies the equation \(1+3+...+(2k-1) + (2k+1) = \sum\limits_{i=1}^{k+1}(2i-1) = (k+1)^{2}\), that is, \(P(k) \rightarrow P(k+1)\).

Conclusion Step: We have proven both the Basis Step and the Induction Step. Therefore, we can use universal generalization to conclude that \(1+3+...+(2n-1) = \sum\limits_{i=1}^{n}(2i-1) = n^{2}\) for all positive integers \(n\).

Q.E.D.

Let \(P(n)\) be the predicate \[P(n): 2^{n} < n!\] We will prove that \((\forall n \in \mathbb{N}_{\geq 4})P(n).\)

Basis Step: First notice that the propositions \(P(0),\) \(P(1),\) \(P(2),\) and \(P(3)\) are all False! This is why we must use \(P(4)\) as the basis. \(P(4)\) is the proposition \(2^{4} < 4!\) which is a True statement since \(16 < 24.\)

Induction Step: First, we assume that the induction hypothesis \(P(k)\) is True for some positive natural number \(k\). In this context we can assume \(k \geq 4.\)

Secondly, we will prove that the conditional \(P(k) \rightarrow P(k+1)\) must be True, which means we can use modus ponens (or the equivalent tautology \(( P(k) \land ( P(k) \rightarrow P(k+1) ) ) \rightarrow P(k+1)\)) to show that \(P(k+1)\) is also True.

Assume that \(P(k)\) is True with \(k \geq 4,\) that is, \(2^{k} < k!.\) If we multiply both sides of the inequality by \(2\) we get \begin{equation} \begin{aligned} 2^{k+1} {} & = 2 \cdot 2^{k} \\ & < (k+1) \cdot 2^{k} \text{ (since \(k \geq 4,\) we must have \(k+1 > 5 >2\))}\\ & < (k+1) \cdot k! \text{ by the induction hypothesis} \end{aligned} \end{equation}

Notice that the expression on the last line is equal to \((k+1)!,\) so we have shown that \((2^{k} < k!) \rightarrow (2^{k+1} < (k+1)!)\) as long as \(k \geq 4.\) That is, we’ve proven that \(P(k) \rightarrow P(k+1)\).

Conclusion Step: We have proven both the Basis Step and the Induction Step. Therefore, we can use universal generalization to conclude that for all positive integers \(n \geq 4\), \(2^{n} < n!\)

Q.E.D.

Set up the proof of the following statement.

The minimal number of moves needed to solve the Towers Of Hanoi puzzle with \(n\) discs is \(2^{n}-1.\)

What is the predicate \(P(n)\)?

What value of \(n\) is best to use in the Basis Step?

What is the Induction Hypothesis?

What property of the puzzle is used the key feature to proving the Induction Step? You can describe this in words or use an algebraic equation.

Recall that the Fibonacci numbers are defined by the following recurrence relation: \[f_{0}=0, \, f_{1}=1, \text{ and } f_{n} = f_{n-1} + f_{n-2} \text{ for } n \geq 2.\]

We will prove that the predicate \[P(n): f_{n} < \displaystyle \left( \frac{1+\sqrt{5}}{2} \right)^{n}\] is True for all natural numbers \(n.\) The proof will use strong induction because, for each \(n \geq 2,\) the value of \(f_{n}\) is defined in terms of both \(f_{n-1}\) and \(f_{n-2}.\)
The number on the right-hand side of the inequality is a famous constant called the golden ratio which is usually denoted by the lowercase Greek letter \(\phi\) ("phi"): \[ \phi = \frac{1+\sqrt{5}}{2} \] \(\phi\) is an irrational number whose first few digits are \(1.618 \ldots .\) Also, \(\phi\) is the positive solution of the equation \(x^{2} = x + 1,\) which is a fact that we will use in the proof. The other solution of \(x^{2} = x + 1\) is \(1 - \phi,\) a fact you can use when you attempt the Challenge question at the end of this example. \[ 1 - \phi = \frac{1-\sqrt{5}}{2} \] Notice that you can verify that \(\phi\) and \(1-\phi\) are the two roots of \(x^{2} - x - 1 = 0\) by using the quadratic formula.

Basis Step: In this case, we need to prove that the conjunction \(P(0) \land P(1)\) is True as our basis for strong induction.

Since \(P(0)\) and \(P(1)\) are True, you can use the tautology \(q \rightarrow ( r \rightarrow (q \land r) )\) to conclude that \(P(0) \land P(1)\) is True, too.

Induction Step: First, we assume as the induction hypothesis that \[P(i) \text { is True for all positive natural numbers } i \leq k \] where we can assume that the integer \(k\) is greater than or equal to \(2\) (since the cases where \(k < 2\) were already dealt with in the Basis Step.) That is, we assume that the single proposition \(P(0) \land P(1) \land \cdots \land P(k)\) is True, where \(k\) is some integer greater than or equal to 2.

Secondly, we will prove that the conditional \(( P(0) \land P(1) \land \cdots \land P(k) ) \rightarrow P(k+1)\) must be True, which means we can use modus ponens to show that \(P(k+1)\) is also True.

If the inequality \(f_{i} < \phi^{i}\) is True for each \(i \leq k,\) then \begin{equation} \begin{aligned} f_{k+1} {} & = f_{k} + f_{k-1} \\ & < \phi^{k} + \phi^{k-1} \text{ by the induction hypothesis} \\ & \leq \phi^{k-1} \cdot (\phi + 1) \text{ by algebra} \\ & \leq \phi^{k-1} \cdot \phi^{2} \text{ since } \phi^{2} = \phi + 1 \\ & \leq \phi^{(k-1)+2} \text{ using one of the laws of exponents} \\ & \leq \phi^{k+1} \end{aligned} \end{equation}

We have proven that if \(f_{i} < \phi^{i}\) is True for each natural number \(i \leq k,\) then \(f_{k+1} < \phi^{k+1}\) must also be True. That is, we have proven \(( ( P(0) \land P(1) \land \cdots \land P(k) ) \rightarrow P(k+1)\).

Conclusion Step: We have proven both the Basis Step and the Induction Step. Therefore, we can use universal generalization to conclude that for all natural numbers \(n,\) \(f_{n} < \phi^{n}.\)

Q.E.D.

Every positive integer \(n\) that is greater than or equal to \(2\) is either a prime number or can be written as a product of two or more prime numbers.

Let \(P(n)\) be the predicate \[P(n) \text{: "} n \text{ is either prime or the product of two or more primes."}\] We will prove that \((\forall n \in \mathbb{N}_{\geq 2})P(n),\) that is, each positive integer \(n \geq 2\) is either a prime or a product two or more prime numbers.

Basis Step: \(P(2)\) is True since \(2\) is a prime number. In this case, we could use only \(P(2)\) as the basis, but it is easy to prove \(P(3)\) and \(P(4)\) are True since \(3\) is prime and \(4 = 2 \cdot 2\) is a product of two primes.

Induction Step: First, we assume as the induction hypothesis that \[P(i) \text { is True for all positive natural numbers } i \text{ such that } 2 \leq i \leq k \] where we can assume that the integer \(k\) is greater than or equal to \(4\) (since the cases where \(k \in \{ 2, 3, 4 \}\) were already dealt with in the Basis Step.) That is, we assume that the single proposition \(P(2) \land P(3) \land \cdots \land P(k)\) is True, where \(k\) is some integer greater than or equal to 4.

Secondly, we will prove that the conditional \(( P(2) \land P(3) \land \cdots \land P(k) ) \rightarrow P(k+1)\) must be True, which means we can use modus ponens to show that \(P(k+1)\) is also True.

There are two cases: Either \(k+1\) is prime or it is not prime (that is, it is composite.)

In either case, we have shown that \(P(k+1)\) must be True. We have proven that if \(P(i)\) is True for each natural number \(i\) with \(2 \leq i \leq k,\) then \(P(k+1)\) must also be True. That is, we have proven \(( ( P(2) \land P(3) \land \cdots \land P(k) ) \rightarrow P(k+1)\).

Conclusion Step: We have proven both the Basis Step and the Induction Step. Therefore, we can use universal generalization to conclude that for all natural numbers \(n > 2,\) \(n\) is either a prime number or a product of two or more prime numbers.

Q.E.D.

The code below implements integer division for positive integers a and b.

Click on the "Next" button to step through the code.

If \(a\) and \(b\) are integers such that \(a > b > 0\) and the integers \(q\) and \(r\) satisfy \[ a = q \cdot b + r \text{ and } 0 \leq r < b \] then the set of positive integers that divide both \(a\) and \(b\) is the same as the set of positive integers that divide both \(b\) and \(r.\)

Notice that \(q\) is the quotient and \(r\) is the remainder that result when doing a long division of \(a\) by \(b.\)

Also notice that we can rewrite the equation \(a = q \cdot b + r\) in the equivalent form \(r = a - q \cdot b.\)

We can now prove the lemma.

So we have two subsets, each of which is a subset of the other, which means that the two sets must be equal. That is, the set of positive integers that divide both \(a\) and \(b\) is equal to the set of positive integers that divide both \(b\) and \(r;\) more plainly, the two set descriptions define the same set.

Q.E.D.

The Euclidean Algorithm correctly computes the greatest common divisor (g.c.d.) of the two positive integers \(a\) and \(b.\)

We use mathematical induction on the number of times \(n\) we must compute a new remainder (that is, the number \(n\) of iterations of the code block inside the loop), and prove that the algorithm computes the correct g.c.d. no matter what the value of \(n\) is.

Let \(P(n)\) be the predicate "If the loop executes \(n\) times, then the last nonzero remainder is the g.c.d. of the two initial inputs." We will prove that \((\forall n \in \mathbb{N})P(n)\) is True.

Basis Step: Notice that the number of iterations of the loop is \(n=0\) if and only if the value of \(r = a\%b\) is equal to \(0\), which is True if and only if \(b\) divides \(a.\) This means that the "last nonzero remainder" is \(b,\) and \(b\) is the greatest common divisor of \(a\) and \(b,\) which means that \(P(0)\) is True.

We can also prove that \(P(1)\) is True in case the proof of \(P(0)\) is unsatisfying. In the case when \(n=1,\) the loop executes \(1\) time, which means that \(a = q \cdot b + r\) and \(r\) is a nonzero divisor of \(b,\) so \(r\) is the g.c.d. of \(b\) and \(r,\) and we can use the lemma to conclude that \(r\) is also the g.c.d. of \(a\) and \(b.\) This proves that \(P(1)\) is True.

Induction Step: First, we assume that the induction hypothesis \(P(k)\) is True for some positive natural number \(k\).

Secondly, we will prove that the conditional \(P(k) \rightarrow P(k+1)\) must be True, which means we can use modus ponens (or the equivalent tautology \(( P(k) \land ( P(k) \rightarrow P(k+1) ) ) \rightarrow P(k+1)\)) to show that \(P(k+1)\) is also True.

Assume that \(P(k)\) is True for the positive integer \(k,\) that is, if the loop executes \(k\) times, then the last nonzero remainder is the g.c.d. of the two numbers we started with. We can assume \(k \geq 1\) since the cases when \(k \in \{ 0, 1 \}\) were proved in the Basis Step. Suppose that we have numbers \(a\) and \(b\) such that the loop executes \(k+1\) times in order to reach the last nonzero remainder: We need to prove that this last nonzero remainder is actually the g.c.d. of \(a\) and \(b.\) Now, notice that if we find the first remainder so that \(r = a - q \cdot b\) and \(0 < r < b,\) then the Euclidean Algorithm requires \(k\) loop iterations to find the last nonzero remainder for the pair of inputs \(b\) and \(r.\) That is , we know from the induction hypothesis that the last nonzero remainder for the initial values \(b\) and \(r\) is the g.c.d. of \(b\) and \(r.\) Now apply the lemma to conclude that the g.c.d. of \(a\) and \(b,\) computed after \(k+1\) loop iterations, is equal to the g.c.d. of \(b\) and \(r,\) computed after \(k\) loop iterations. Therefore, \(P(k+1)\) is True, too. This proves that \(P(k) \rightarrow P(k+1)\).

Conclusion Step: We have proven both the Basis Step and the Induction Step. Therefore, we can use universal generalization to conclude that for all natural numbers \(n,\) if the loop executes \(n\) times then the last nonzero remainder is the g.c.d. of \(a\) and \(b.\) That is, the Euclidean Algorithm correctly computes the g.c.d. of \(a\) and \(b\) no matter how many loop iterations are required to compute the last nonzero remainder.

Q.E.D.