CSCI 650
Design and Analysis of Algorithms

Induction exercises

Page 49 of Computer Algorithms Problem 2:

Proof by induction of (a):

already shown

Proof by induction of (c):

Induction on x? on i? on n?

What is the base case? Why can x not equal 1?

Proof:

Proof by induction of (b):

I give in