- #1

- 51

- 0

## Homework Statement

Solve and prove your solution for the following recurrence relation for the number of comparisons in Binary Search:

C(2

^{1}- 1)=1

C(2

^{i}- 1) = 2 + C(2

^{(i+1)}- 1)

## The Attempt at a Solution

The setup for this would be:

C(n)={ 1, n=1 and 2 + C(2

^{(i+1)}- 1), otherwise

From this I would do substitution and guessing, and then prove the guess with induction?