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.

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

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.

• 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:

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.

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.