308-360 Tutorial #1

Induction Information
resources: www.cs.montana.edu/course_pages/courses_S99/223-defrance/lectures/induction

Induction proofs involve proving an implication

prove p is true (first step)
prove p implies q is true (second step)
therefore q is true
Theorem 1: First principle of mathematical induction
Let P(k) be a predicate. If:
(a) P(1) is true
(b) For any k>1, P(k-1) TRUE implies P(k) TRUE
Then: P(k) is TRUE for all k>=1.

Assume that you want to prove that for some statement P, P(n) is TRUE for all n starting with n=1. Then Principle (or Axiom) of Mathematical Induction states that for this purpose you should accomplish just two steps:
1. Prove that p(1) is TRUE.
2. Assume that P(k) is TRUE for some k. Derive from here that P(k+1) is also TRUE.
When induction can be used
When the theorem is of the form: n P(n) where the universe is the set of positive integers.
Many theorems say that P(n) is true for all positive integers.
Note about mathematical induction: It can be used only to prove something you have found out in some other way.

Weak Induction

P(n) true for all positive integers n
1. P(1) true
2. (k)[P(k) true implies P(k+1) true]

Strong Induction

1. P(1) true
2. For all K[P(r) true for all r, 1 < r < k] implies P(k+1) true

Another way to state strong induction:
1. The proposition P(1) is true
2. If [P(1) and P(2) and P(3) ...P(n) is true then P(n+1) is true P(n+1) is true

Difference between strong and weak induction

Strong- assume P is true for a range, between 1 and k
Weak - assume P is true for a single value k

It can be proved strong induction and weak induction are equivalent.

Weak Induction Proofs

Prove: The sum of the first n odd integers is n^2. 1 + 3 + 5 + . . . + 2n-1 = n^2
Basis: Prove for P(1), For n =1; 1 = 12
Inductive: Prove for P(n) implies P(n+1)
Assume P(n) 1 + 3 +5 + . . . + 2n-1 = n^2
Prove P(n+1) 1 + 3 +5 + . . . + 2n-1 + 2(n+1) -1 = (n+1)^2
Prove: for any positive integer n, 2n > n
Basis: Prove for P(1), For n = 1; 2(1) > 1
Inductive: Prove for P(n) implies P(n+1)
Assume P(n) 2n > n
Prove P(n+1) 2(n+1) > n+1

Strong Induction Proof

Prove: For every n >= 2, n is a prime number or the product of prime numbers.
Basis: Prove P(2) is either prime or the product of primes 2 is prime TRUE
Inductive: Prove P(n+1)
Prove: The number of paths from (0,0) to (i,j) determined by PathCount equals i+j choose i.
As stated in class, this can be proven directly or by using induction.

Excercise: Prove that the number of paths from (0,0) to (i,j) determined by PathCount equals i+j choose i.

Recursive algorithm for PathCount

f( 0, 0 ) = 1
f( 0, j ) = f( 0, j - 1 )
f( i, 0 ) = f( i - 1, 0)
f( i, j ) = f( i - 1, j) + f( i, j - 1 )
Background on chooses and factorials
• n choose k denotes the number of k-combinations of an n-set. A k-combination of an n-set S is simply a k-subset of S.
• A permutation of a finite set S is an ordered sequence of all the elements of S, with each element appearing exaclty once. n! permutations of a set of n elements.
• For every k-combination, there are exactly k! permutations of its elements, each of which is a distinct k-permutation of the n-set. Thus the number of k-combinations of an n-set is the number of k-permutations divided by k!.
• n choose k = n! / k!(n-k)!
Inductive Proof - CHANGED!!!
Let p(i,j) denote the number of paths from (0,0) to (i,j), p(i,j)=i+j choose i.
Let f(i,j) be the value calculated by the PathCount algorithm.
Let P(i+j) be the proposition that p(i,j)=f(i,j), where n=i+j.

Base Case

Case when i+j=0, i=j=0.
The number of paths from (0,0) to (0,0) is initialized to 1 by PathCount. So, f(0,0)=1.

By definition, p(0,0) = (0+0) choose 0 = 0!/0!0! = 1.

f(0,0) = p(0,0) = 1.

P(0) is True.
Inductive Step (assumption and step)

Assume that P(i+j) is True for all i, j where i+j <=n, 0 <= i <= n and 0 <= j <= m.

Prove P(i+j+1). So, look at f(i,j+1) and f(i+1,j). By the PathCount algorithm:
Case 1: If i = 0, f(i,j+1) = f(i,j).
Case 2: If i > 0, f(i,j+1) = f(i,j) + f(i-1,j+1).

Case 3: If j = 0, f(i+1,j) = f(i,j).
Case 4: If j > 0, f(i+1,j) = f(i+1,j-1) + f(i,j).
By the inductive hypothesis, P(i+j) is True which means that f(i+j) = p(i+j). Therefore:
Case 1: If i = 0:
Since i = 0, by the PathCount algorithm, f(i,j+1) = f(i,j) = ... = f(i,1) = f(i,0) = 1. By definition, p(i,j+1) = (i+j+1)!/i!(j+1)! = (j+1)!/(j+1)! = 1. So, f(i,j+1) = 1 = p(i,j+1) when i = 0, and therefore Case 1 is True.

Case 2: If i > 0:
f(i,j+1) = f(i,j) + f(i-1,j+1).

f(i,j+1) = f(i,j) + f(i-1,j+1)
f(i,j+1) = p(i,j) + p(i-1,j+1)
f(i,j+1) = (i+j)!/i!j! + (i+j)!/(i-1)!(j+1)!
f(i,j+1) = (i+j)!(i-1)!(j+1)!/i!j!(i-1)!(j+1)! + (i+j)!i!j!/i!j!(i-1)!(j+1)!
f(i,j+1) = (i+j)!(j+1)/i!(j+1)! + i(i+j)!/i!(j+1)!
f(i,j+1) = [(i+j)!(j+1) + i(i+j)!]/i!(j+1)!
f(i,j+1) = (i+j)!(j+1+i)/i!(j+1)!
f(i,j+1) = (i+j+1)!/i!(j+1)!
f(i,j+1) = (i+j+1) choose i
f(i,j+1) = p(i,j+1)

Since f(i,j+1) = p(i,j+1), Case 2 is True.

Case 3: If j = 0:
Since j = 0, by the PathCount algorithm, f(i+1,j) = f(i,j) = ... = f(1,j) = f(0,j) = 1. By definition, p(i+1,j) = (i+j+1)!/(i+1)!j! = (i+1)!/(i+1)! = 1. So, f(i+1,j) = 1 = p(i+1,j) when j = 0, and therefore Case 3 is True.

Case 4: If j > 0:
f(i+1,j) = f(i,j) + f(i+1,j-1)

f(i+1,j) = f(i,j) + f(i+1,j-1)
f(i+1,j) = p(i,j) + p(i+1,j-1)
f(i+1,j) = (i+j)!/i!j! + (i+j)!/(i+1)!(j-1)!
f(i+1,j) = (i+j)!(i+1)!(j-1)!/i!j!(i+1)!(j-1)! + (i+j)!i!j!/i!j!(i+1)!(j-1)!
f(i+1,j) = (i+j)!(i+1)/j!(i+1)! + j(i+j)!/j!(i+1)!
f(i+1,j) = [(i+j)!(i+1) + j(i+j)]!/j!(i+1)!
f(i+1,j) = (i+j)!(i+1+j)/j!(i+1)!
f(i+1,j) = (i+j+1)!/j!(i+1)!
f(i+1,j) = (i+j+1) choose (i+1)
f(i+1,j) = p(i+1,j)

Since f(i+1,j) = p(i+1,j), Case 4 is True.

As shown for all cases, P(i+j+1) is True. Therefore, P(i+j) is True for all i+j, 0 <= i <= n and 0 <= j <= m.
Direct Proof
Each step in the path can either be a right-move or a down-move. To arrive at (i,j), a path can consist of i down-moves and j right-moves. Therefore, each path consists of i+j steps.

Every path is a sequence of i+j steps S and i of these steps must be down-steps. A possible path defines i steps as down-moves and the remaining j steps as right-moves. A path can then be thought of as choosing an i element permutation of down-moves from i+j possible moves. The total number of i-element permutations from a set of size i+j is i+j choose i.

Find all the permutations of i steps from i+j steps to set as down-moves = (i+j)(i+j-1)(i+j-2)(i+j-3)...(i+j-i+1) = (i+j)!/j!. We don't want permuations, just combinations. Each i-combination has exactly i! permutations of its elements, so the number of i-combinations of the i+j set = (i+j)!/j!/i! = (i+j)!/j!i! = i+j choose i.