Data Structures – 390 Assignment #7 Due: Wednesday November 29
Proof by Induction
Lab Objectives
 Become familiar with rigorous mathematical proof and in particular with induction
Problem Description
 Assume that you have a sorted array of n elements. Prove that a binary search of an array of n elements is less or equal than log n
 Prove by induction that the sum 2^{0}+2^{1}+2^{2}+2^{3}+...+2^{h is equal to 2h+11}
 The recursive solution of the Towers of Hanoi problem which starts with n disks on peg A, requires than n1 pegs are moved to peg B, then the last remaining on A is moved to peg C and then the n1 disks from B are moved to C. Thus the number of steps S(n) for the n pegs is S(n) = 2S(n1) +1. Prove by induction that S(n)=2^{n}1.
 Prove that the above recursive solution for the Towers of Hanoi problem is optimal in the sense that any other algorithm cannot do better than S(n).
