Module 09: Weak Induction Proofs

Sequences

A sequence is an ordered list of numbers, often formed by a recognizable pattern. This pattern can typically be described by a formula. For instance, consider a sequence defined as a_n = 2n²+1 for n > 0. That formula describes a pattern like 3, 9, 19, 33, 51, and so on, where a₁ = 3, a₂ = 9, a₃ = 19 and so on.

A sequence can also be defined recursively in terms of its own previous values. A well-known example is the Fibonacci sequence, defined as F₀ = 0, F₁ = 1 and F_n = F_n-1 + F_n-2 for all n ≥ 2. In this sequence, each term is calculated as the sum of the two preceding terms, giving: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Summation

When we want to find the total sum of a group of terms in a sequence, we use summation notation, symbolized by the Greek letter sigma Σ. This allows us to express the sum of terms starting from an index m and ending at n, where m ≤ n. A summation that has m > n is called n empty summation and does not have any elements.The variable k often serves as the index, taking on each integer value from m to n, applying the formula for each value, and adding the results together.

So we have that the sum of all elements in a sequence a_m, a_m+1, a_m+2, ...., a_n-1, a_n is given by \(\sum\limits_{k=m}^n a_k\).

\(\sum\limits_{i=1}^{5} (2i + 1)\) = (2·1 + 1) + (2·2 + 1) + (2·3 + 1) + (2·4 + 1) + (2·5 + 1) = 3 + 5 + 7 + 9 + 11 = 35

\(\sum\limits_{i=2}^{6} 2i\) = (2·2) + (2·3) + (2·4) + (2·5) + (2·6)= 4 + 6 + 8 + 10 + 12 = 40

Think of how this relates to, for example, a universal quantifier. ∀x ∈ D, P(x) is like a collection of statements about each element in the set D connected together by ⋀: P(d₁) ⋀ P(d₂) ⋀ ... ⋀ P(d_n). A summation using Σ works similarly except that (1) it defines the set as a range of integer values from a low element (m above) to a high element (n above) and (2) it connects the body of the summation together with addition (+) rather than logical AND.

Product

Similarly, when multiplying the terms of a sequence instead of adding them, we use the product notation, represented by the Greek letter pi Π. As with summation, the index k moves from the starting point to the end point, but now the values are multiplied together instead of summed.

So we have that the product of all elements in a sequence a_m, a_m+1, a_m+2, ...., a_n-1, a_n is given by \(\prod\limits_{k=m}^n a_k\).

\(\prod\limits_{i=1}^{5} (2i + 1)\) = (2·1 + 1) · (2·2 + 1) · (2·3 + 1) · (2·4 + 1) · (2·5 + 1) = 3 · 5 · 7 · 9 · 11 = 10395

\(\prod\limits_{i=2}^{6} 2i\) = (2·2) · (2·3) · (2·4) · (2·5) · (2·6)= 4 · 6 · 8 · 10 · 12 = 23040

Last Term of Summation and Product

When working with either a summation or a product, it's sometimes useful to isolate the last term. This is done by reducing the upper limit of the summation or product by one and then explicitly including the final term outside of the notation. For example, if a summation goes from k=0 to 6, the term at k=6 can be written separately, and the summation can instead go up to k=5.

For example, \(\sum\limits_{i=2}^{6} 2i\) has the last term⁣, 2 · 6 = 12 so we can write this summation as 12 + \(\sum\limits_{i=2}^{5} 2i\), making the maximum value of k 5, instead of 6.

Mathematical Induction

Mathematical induction is a logical technique used to prove that a statement P(n) is true for all positive integers. It begins with verifying the statement for the smallest valid number, known as the base case. Then, assuming the statement holds for an arbitrary number n, the goal is to show it must also hold for the next consecutive number, n+1 (also known as weak induction). If both steps are successful, the truth of the statement for all such values follows, much like a line of dominos falling one after another once the first has been pushed.

Proving ∀n ∈ ℤ⁺, P(n):
    1. Prove P(n=1) is true
    2. Prove ∀n ∈ ℤ⁺, P(n) → P(n+1):
        2a. Assume P(n) is true
        2b. Prove P(n+1) is true

The core idea of mathematical induction is similar to a domino effect. By proving that the first statement, P(1), is true, we effectively push the first domino. Then, we assume that if one statement, P(n), is true, the next one, P(n+1), must also be true, ensuring the entire chain continues to fall. Importantly, we are not directly proving P(n) in the inductive step, but rather showing that P(n) → P(n+1). What matters is that we are always proving the next consecutive case based on the one we assumed. Attempting to assume P(n+1) and prove P(n) would break the logic of induction.

Going back to our domino analogy: if you push one domino, the ones before it won't fall. Induction only works when the forward chain of implication is maintained. Consider what happens when we push domino 1 over, i.e., P(1) is true. Since we know ∀n ∈ ℤ⁺, P(n) → P(n+1), we know by our rule Universal Instantiation that P(1) → P(1+1). So, the second domino P(2) must also "fall". Then, universal instantiation also gives us P(2) → P(3), causing the third to fall, and so on.

There are two common approaches to induction, both of which are logically equivalent and usually yield similar proofs. However, depending on the problem, one method might be more convenient than the other. We might assume P(n) and prove P(n+1), or assume P(n-1) and prove P(n). In both cases, the base case remains the same; it must be the smallest value in the domain of the problem.

Base Case

In the base case, the variable n is replaced with the smallest value for which the statement should hold, similar to an existential proof. This part of the proof establishes that the statement is true at the starting point.

Induction Hypothesis (IH)

Now, we want to prove ∀n ∈ ℤ⁺, P(n) → P(n+1). The hypothesis is the part of the proof when we assume the left-hand side of the implication in a universal proof, as we saw in Module 7. In this part, we begin by restating the statement we aim to prove and assume it to be true for a specific case. At first, this may seem counterintuitive, almost as if we're assuming the conclusion in order to prove it. However, what we're actually doing is assuming that P(n) holds for a particular value (usually the previous one in the sequence), not for all values. This assumption forms the basis of the inductive step, allowing us to show that if P(n) is true, then P(n+1) must also be true.

Induction Step (IS)

The induction step uses the assumption that the statement holds for n to prove that it also holds for n+1. This step typically involves substituting the hypothesis into the equation and showing that it logically leads to the next case being true as well. Once this is shown, the conclusion is that the statement holds for all positive integers starting from the base case.

The same proof can be done using a different hypothesis. We are now proving ∀n ∈ ℤ⁺, P(n-1) → P(n).

We need our inductive step to prove the property P for every value except the base case value (or values). If we're proving P(n+1), we need n+1 to be able to take on every value except the base case value. That means we need n + 1 > 1, since the base case here is 1. If we subtract one from both sides of that inequality, we get n > 0 or equivalently, as we wrote it above, n ≥ 1. What if we wanted to prove P(n) based on P(n-1) instead? Well, then we need n rather than n+1 to take on every value except the base case values. So, we need n > 1. Notice how the change in bounds is entirely driven by where we're proving property P.

Recursion

The logic of induction also provides a foundation for writing recursive algorithms. In such algorithms, the base case stops the recursion, while the step that reduces the problem toward the base mimics the induction step. For example, the proof shown here before can help us to create a recursive algorithm to calculate that summation:

def P(n):
    if n=1:
        return 1
    else: 
        return P(n-1)+n

It is important to ensure that both the proof and the corresponding recursive algorithm account for each number in the sequence exactly once. In this case, we adopt the form P(n − 1) → P(n), and we are proving the statement for P(n). In this case, our base case is typically n=1, which becomes the stopping point of the recursion. All other values are handled through recursive calls, corresponding to the induction step. In the recursive code, this logic appears in the condition: the else branch only executes when n > 1, not when n ≥ 1.

To illustrate this, consider computing the value of P(3):

• The program begins with n=3, enters the else branch, and calls P(2).
• With n=2, it again enters the else and calls P(1).
• At n=1, it meets the base case, enters the if branch, and returns 1.
• The call for P(2) receives this value, adds 2, and returns 3.
• Then, the call for P(3) receives the result of P(2), adds 3, and returns 6.
• Thus, the final result is 6.

Read More

Epp, Susanna. Discrete Mathematics with Applications.

• 5th edition: 5.1 and 5.2

• 4th edition: 5.1 and 5.2

• 3rd edition: 4.1 and 4.2