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 20+21+22+23+...+2h is equal to 2h+1-1
  • The recursive solution of the Towers of Hanoi problem which starts with n disks on peg A, requires than n-1 pegs are moved to peg B, then the last remaining on A is moved to peg C and then the n-1 disks from B are moved to C. Thus the number of steps S(n) for the n pegs is S(n) = 2S(n-1) +1. Prove by induction that S(n)=2n-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).