Use Mathematical Induction to prove that the computational complexity of the Tower of Hanoi algorithm below is 2^n - 1. Show each of the following steps: (a) verification for the base case, (b) statement of the induction hypothesis, (c) the induction step, and (d) deduction or conclusion based on the Mathematical Induction.

Tower of Hanoi code:

#include

using namespace std;

int m=0; // count number of moves in this global variable.

void tower(int n, int s, int f, int t){

if(n==0) return;

tower(n-1,s,t,f);

cout << "Move No. " << ++m << ": Move one top disk from " << s << " to " << f << " . ";

tower(n-1,t,f,s);

return;

}

void main( ) {

int n;

cout << "Enter number of entries n. ";

cin >> n;

if ( (n<=0) || (n>12) ) {

cout << "n out of bounds [ 1..12]. ";

return;

}

m = 0;

tower(n,1,2,3);

cout << " type any character to quit ";

char c;

cin >>c;

}

// ESE 344, SBU, Murali Subbarao

// Example of recursion

// GCD greatest common divisor program

#include

using namespace std;

int gcd(int m, int n) // function definition

{

if ((m <= 0) || (n <= 0)) return 0;

if (m%n == 0) return n;

else return gcd(n, m%n);

}

void main()

{

int m1, n1; char c;

do {

cout << " GCD : Enter two integers greater than or equal to 1 : ";

cin >> m1 >> n1;

cout << "GCD of " << m1 << ", " << n1 << " is : " << gcd(m1, n1) << endl << endl;

cout << "Another input pair ? Type y/n : ";

cin >> c;

cout << endl;

} while (c == 'y');

return;

}

// Binary search example.

// Prof. Murali Subbarao

#include

using namespace std;

#include // for rand(), srand()

#include // for time()

#include // for sqrt()

int countn = 0;

int BinarySearch(int a[], int l, int h, int k)

{ int mid;

countn++;

if(l>h) return -h;

mid= (l+h)/2;

if(k==a[mid]) return mid;

else if (k

else return BinarySearch(a,mid+1,h,k);

}

void sort(int a[], int n) {

int i,j;

//sort

for(i=0;i

int tmpmin=a[i];

for(j=i+1;j

if(tmpmin>a[j])

{ tmpmin = a[j];

a[j]=a[i];

a[i]= tmpmin;

}

}

}

}

void main( ) {

int n,k;

int a[1000]; // array to store data

cout << "Enter 0 for simulation input, and 1 for external input. ";

cin >>k ;

if (k != 1) k=0;

// read data

cout << "Enter number of entries n. ";

cin >> n;

if ( (n<=0) || (n>1000) ) {

cout << "n out of bounds. ";

return;

}

srand((unsigned int) time(NULL));// seed rand() with system time

int i;

for(i=0;i

int x;

if (k == 1) {

cout << " Enter next data : ";

cin >> x; // you can read from a file with this

}

else

x= (int) (rand()%10000); // limit data to 0 to 9999.

cout <<" " << x ;

a[i] = x;

}

cout << endl;

sort(a,n);

for (i = 0; i

cout << " " << a[i];

}

cout << endl;

cout << "Enter number or key to search for OR -1 to exit : ";

cin >> k;

while (k>0) {

int pos;

int l,h;

l=0; h=n-1;

countn =0; // number or calls, globl variable

pos = BinarySearch(a,l,h,k);

cout << "Position : " << pos << " Count: " << countn << endl;

cout << "Enter number or key to search for OR -1 to exit : ";

cin >> k;

}

}