Mathematical Preliminaries for COMP372 Algorithms

Throughtout the courses in COMP272 and COMP372, we use quite often two most commonly used proof techniques: proof by contradiction and proof by mathemetical induction.

Proof by Contradition

To prove a statement by contradiction, we first assume that the statement is false, then we find a logical contradiction stemming from this assumption. If the logic used to find the contradiction is correct, then the only way to resolve the contradiction is to recognize that the assumption that the theorem is false must be incorrect, that is, to conclude that the statement must be true.

Example 1: To prove that there is no largest integer.

Proof: Let us prove it with Proof by contradiction.
Step 1: Contrary assumption: assume that the statement "there is no largest integer." is incorrect. That is, there is a largest integer, called it \(m\).
Step 2: Show this assumption leads to a contradiction: consider \(n = m + 1\). \( n \) is an integer as it is the sum of two integers. Also, \( n > m \). Thus, we have reached a contradiction. The only flaw in our reasoning is the initial assumption - the statement is false. Thus, we conclude that the statement is correct.

Proof by Mathematical Induction

Let \( T \) be a theorem to prove, and express \( T \) in terms of a positive integer parameter \( n \).
T is true for any \( n \leq c \), where c is some small constant, if:
1. Base case : \( T \) holds for \( n = c \), and
2. Induction step : If \( T \) holds for \( n-1 \), then \(T\) holds for \( n \).

An alternative formulation of the induction step is known as Strong induction.
The induction step for strong induction is:
2a. Induction step: if \(T \) holds for all \( k: c \leq k < n,\) then \( T \) holds for \( n. \) What makes mathematically induction so powerful is that we can take advantage of the assumption that \( T \) holds for all values less than \( n \) help us prove that \(T \) holds for \(n \). This is known as the induction hypothesis . Having this assumption to work with makes the induction step easier to prove than tackling the original theorem itself.

Example 2 To prove: The sum of the first \( n \) numbers is \( \frac{n(n+1)}{2} \).
Proof: The proof is by mathemetical induction.

1. Check the base case: For \( n = 1, \) the sum is simply 1. The formula states that for \( n =1 \), 1(1+1)/2 =1. Thus, the formula is correct for the base case.
2. State the induction hypothesis. The induction hypothesis is
\( \sum_{i=1}^{n-1} {i} = \frac{(n-1)[(n-1)+1]}{2} = \frac{(n-1)n}{2} \)
3. Use the assumption from the induction hypothesis for \(n-1\) to show that the result is true for \(n\).
Since \( \sum_{i=1}^{n} {i} = \sum_{i=1}^{n-1} {i} + n \), we have \( \sum_{i=1}^{n} {i} = \sum_{i=1}^{n-1} {i} + n = \frac{(n-1)n}{2} + n = \frac{n^2-n+2n}{2} = \frac{n(n+1)}{2} \)
Thus, by mathemetical induction,
\( \sum_{i=1}^{n} {i} = \sum_{i=1}^{n-1} {i} + n = \frac{n(n+1)}{2} \).

1.The following is the incomplete proof for the statement:

For all positive integers \( n, 2^n > n. \)
Proof: Let \( P\) be the set of all positive integers for which \( 2^n > n \) is true. Since \( 2^0 = 1 \) is true, \( 0 \in P \). Assume ___(1)_____ and \( k > 1 \). Then \( 2^{k-1} > k-1 \) is true and since \( 2^k = 2^{k-1}*2 > (k-1) * 2 = 2k -2 \) > ____(2)_____.
it follows \( k \in P \). Thus, for all \(k \in P, k-1 \in P \) implies \( k \in P \) is true and so by mathematical induction \(P = N \) as desired.

Please select the correct option of the following to fill the blanks (1) and (2).
\( k-1 \in P \), \( k \) \( k \in P \), \( 1 \) \( k-2 \in P \), \( k \) \( k+1 \in P \), \( k+1 \)

2. Fill the blanks (1) and (2) to the following proof by mathematical induction for the statement to complete it:

\(6^n + 4 \) is divisible by 5 , for \(n ≥ 0\).

Step 1:  Show it is true for \( n = 0: \) \(6^0 + 4 = 5\), which is divisible by .5
Step 2:  Assume that it is true for ___(1)____. That is, \( 6^{k-1} + 4 = 5M \), where \(M ∈ I\).
Step 3:  Show it is true for \( n = k\). That is, \(6^k + 4 = 5P \), where P ∈ I.

\( 6^k + 4 = 6*6^{k-1} + 4 = 6*[5M-4] + 4 = \) __(2)___, which is divisible by 5. That is \( P = 5M-4. \) Therefore it is true for \( n = k\), assuming that it is true for \( n = k - 1. \) Therefore, \(6^n + 4 \) is always divisible by 5.


\( n = 2\), \( 5*[6M-4] \) \( n = k-1\), \( 30M-24 \) \( n = k\), \( 5(M+4) \) \( n = k-1\), \( 5*[6M-4] \)

3. Fill the blank in the following proof by contradiction for the statement to complete it:

If \(ab\) is an even number, then \( a \) or \(b \) is even.

Proof:
Suppose \(a \) and \( b \) are odd. That is, \( a = 2k + 1 \) and \( b = 2m + 1 \) for some integers \( k \) and \( m \). Then
\( ab = (2k + 1)(2m + 1) = 4km + 2k + 2m + 1 = \) _____. Therefore \(ab \) is odd.

\( 2(2km + k + m) \) \( 2(2km + k) + 2m + 1 \) \( 2(2km + k + m) + 1 \) \( 4km + 2(k + m) + 1 \)

4. Fill the blanks in the following proof by contradiction for the statement to complete it:

Prove that \( \sqrt{2} \) is irrational.

Proof: Suppose that \( \sqrt{2} \) is not irrational. Then \( \sqrt{2} \) is equal to a fraction \( \frac{a}{b} \). Without loss of generality, assume \( \frac{a}{b} \) is _____ (otherwise we can reduce the fraction). So, \(2 = \frac{a^2}{b^2} \), \(2b^2 = a^2 \). Thus \( a^2\) is even, and as such \(a\) is even. So \(a = 2k\) for some integer \(k\), and \(a^2 = 4k^2\). We then have, \(2b^2 =4k^2 \) , \( b^2 = 2k^2 \). Thus \(b^2\) is even, and as such \( b \) is even. Since \( a \) is also even, we see that \( \frac {a}{b}\) is not in lowest terms, which is a contradiction. Thus \( \sqrt{2} \) is irrational. QED.
in lowest terms not in lowest terms the smallest value positive Submit

Your grade is: __