Worked Proofs and Proof Critiques for Induction

Worked Proofs and Proof Critiques for Induction

CPSC 121, Sections 202 and BCS, 2008-2009W2

Worked Proof: Introductions for a Group of Size n

Definitions: An “introduction” is one person saying hello to one other person.

Theorem: For a group of n people to introduce themselves requires n(n-1) introductions.

Proof:

Base case:A group of 1 person requires no introductions. So, when n = 0: 0 = 1*0 = 1(1-1).

Induction hypothesis: Assume that a group of k people requires k(k-1) introductions (for an arbitrary integer k ≥ 1).

Inductive step:Under this assumption, we need to prove that a group of k+1 people takes (k+1)((k+1)-1) introductions.

Consider a group of k+1 people. Remove one person from the group. What remains is a group of k people, who can introduce themselves by the induction hypothesis using k(k-1) introductions. To finish with the group of k+1, the remaining person must greet and be greeted by each of the k people, for 2k additional introductions.

So, k+1 people take:

k(k-1) + 2k= k2 - k + 2k

= k2 + k

= (k+1)k

= (k+1)((k+1)-1).

This concludes our inductive proof. Therefore a group of size n takes n(n-1) introductions.

Worked Proof: Maximum Nodes Per Height for a Binary Tree

Definitions:Let a binary tree be a “root” node with 0 to 2 children and all of its children’s nodes. Let the height of a binary tree be the longest path from the root node to a node with no children. Let n(h) be the maximum number of nodes in a binary tree of height h.

Theorem: n(h) = 2h+1 - 1.

Proof:

Base case:A binary tree of height 0 is a single node. So, n(0) = 1 = 2- 1 = 21 - 1 = 20 + 1 - 1.

Induction hypothesis: Assume that n(k) = 2k+1 - 1 (for an arbitrary integer k ≥ 0).

Inductive step:Under this assumption, we need to prove that n(k+1) = 2(k+1)+1 - 1.

Consider a binary tree of height k+1. There are three cases for this tree:

(1)No children, but then its height would be 0, which contradicts the assumption that k ≥ 0 (and so k + 1 ≥ 1). So, this case cannot occur.

(2)One child, but then the tree could have more nodes by adding a second child; thus, this is not the tree of height k+1 with the maximum number of nodes. So, this case is not relevant.

(3)Two children. Then, to have the maximum number of nodes, each child’s height must be k (else, we could increase the number of nodes by adding a new (great-great-great...grand) child to the bottom of the child’s tree and increasing its height). Further, for the whole tree to have the maximum number of nodes, each child must have the maximum number of nodes for a tree of height k (else, we could replace it with such a tree and again increase the number of nodes without changing the whole tree’s height). Thus, the number of nodes in the whole tree is the number in each child tree plus the root node 2*n(k) + 1. By the induction hypothesis, we know n(k) = 2k+1 - 1. Then:

n(k+1)= 2*n(k) + 1

= 2*(2k+1 - 1) + 1

= 2*2k+1 - 2 + 1

= 21+k+1 - 1

= 2(k+1)+1 – 1

This concludes our inductive proof. Therefore the maximum number of nodes in a binary tree of height h is 2h+1 - 1.

Proof Critique: All Horses Are the Same Colour

What’s wrong with this proof? Anything?

Theorem: All horses are the same colour.

Proof:

Base case:All horses in any group of one horse are obviously the same colour.

Induction hypothesis: Assume that all horses in any group of size k are the same colour (for an arbitrary integer k ≥ 1).

Inductive step:Under this assumption, we need to prove that all horses in any group of horses of size k+1 are the same colour.

Consider an arbitrary group of k+1 horses.

Remove any one horse from it. What remains is a group of k horses, which are all the same colour by the induction hypothesis. Only the set-aside horse may be a different colour.

Now, return the horse to the group and remove a different horse. Again, the remaining horses are all the same colour, but from the previous step we already know that this time the set-aside horse is also the same colour. Therefore, all horses in any group of size k+1 are the same colour.

This concludes our inductive proof. Therefore all horses in any group of any size are the same colour, i.e., all horses are the same colour.

Worked Proof: Binary Search

Definitions: A listahas a length len(a). The elements in the list in order are number 0, 1, 2, ..., len(a) - 1.

Theorem: We can correctly search a sorted list of names by binary search:

Algorithm to search a list a of length len(a) for the name n:

If len(a) is 0, the name was not found; otherwise, check the element len(a)/2 and:

(1)If element len(a)/2 is the one sought; report it, and we’re done.

(2)If element len(a)/2 is larger than the one sought, repeat the algorithm on the list of elements 0, ..., len(a)/2 - 1.

(3)Otherwise (element len(a)/2 is smaller than the one sought), repeat the algorithm on the list of elements len(a)/2 + 1, ..., len(a) - 1.

Proof:

Base case:A list of length 0 contains no names; so, the algorithm correctly reports failure.

Induction hypothesis: Assumethat we can correctly search a sorted list of names of any integer length 0 ≤ k < n, where n is an integer ≥ 1, by binary search.

Inductive step:Under this assumption, we need to prove that we can correctly search a sorted list of names of length n by binary search.

Since n > 0, the algorithm will check on element n/2 . Since 0 < n, 0 < n/2 < n; so, 0 ≤ n/2 < n, and the list does contain such an element.

There are then three cases:

(1)The algorithm finds the name sought, in which case it correctly reports it.

(2)Element n/2 is too large. Since the list is sorted, the name sought has an index smaller than n/2 , and the algorithm proceeds on the list of those elements (0, ..., n/2 - 1) with a length of n/2. We know 0 ≤ n/2 < n (i.e., the list’s length is in the range covered by our induction hypothesis); so, the algorithm operates correctly.

(3)If element n/2 is too small, the algorithm proceeds on the right portion of the list, with n - n/2 - 1 elements (all but the first n/2 elements and element n/2). We know 0 ≤ n/2 ≤ n - 1; so,0 ≤ n - (n - 1) - 1 ≤ n - n/2 - 1, andn - n/2 - 1 ≤ n - 1 < n (i.e., the list’s length is in the range covered by our induction hypothesis). Thus, the algorithm operates correctly.

This concludes our inductive proof. Therefore, we can correctly search a sorted list of names by binary search.

Proof Critique: All Integers Greater than or Equal to Two Are Even

What’s wrong with this proof? Anything?

Theorem: All integers greater than or equal to two are even.

Proof:

Base case: There exists an integer k=1 such that 2*k = 2. Therefore, two is even.

Induction hypothesis:Assume that all integers k where 2 ≤ k < n are even (for an arbitrary integer n 2).

Inductive step:Under this assumption, we need to prove that n is even.

Consider the number n.

n = (n-2)+2

By the induction hypothesis, n-2 is even. So, there is an integer k’ such that n-2 = 2*k’.

n = 2*k’ + 2 = 2*(k’ + 1)

k’ + 1 is also an integer.

Therefore n+1 is even.

This concludes our inductive proof. Therefore all integers greater than or equal to two are even.