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 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 )

- 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)!**

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:By the inductive hypothesis, P(i+j) is True which means that f(i+j) = p(i+j). Therefore: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).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.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.

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.