Table of Contents   |   Proof Methods   |   Glossary

---

Induction: Practice Problems

The following exercises have 3 diff

It would be good if you can try and solve the problems yourself or choose a hypothesis and a statement and see if you've chosen correctly. <elaborate>

Some of the problems are also related to other topics in algorithms.  

Basic Exercises

Forming the Proposition

Given the following problem statement, state the Inductive Proposition that you're trying to solve.

Prove that the Tower of Hanoi algorithm is correct for any m disks.  (See also Recursion and Recurrences)

Prove that for a number n that is greater than or equal to 3, if n distinct points on a circle are connected in consecutive order with straight lines, then the interior angles of the resulting polygon add up to (n - 2) * 180. (Velleman, p. 254)

---

Verify the Base Case

Forming the Inductive Hypothesis

Practice Proofs

1. Using Induction, prove the following identity is true

The Proposition:

The Base case: is true for n = 1.

	Inductive Hypothesis	Inductive Step
A
B
C

Advanced Problems

Prove that the basic Bubblesort algorithm is correct.

Given G = (V, E) be an undirected graph, and suppose a Breadth First Search is run on G from a given source vertex s in V., the distance from