Analysis of Recursive Programs: Problem (a) in the dark

PROOF:
Base:
T(1) = 1 by definition
T(1) < c*1^{log 3} + b*1 (assume logs are always base 2) implies
1      <       c + b             OK, remember this for later

Induction hypothesis:
Assume THM is true: T(n) = 3T(n/2) + n < cn^{log₂ 3} + bn for all n < n'.

Induction step:

Suppose n is greater than n', let n = n' + 1

then, T (n) = 3T(n/2) + n (by definition of T(n))

since n/2 < n', by induction hypothesis, T (n/2) = c(n/2^{log₂ 3}) + b(n/2)

Looks ugly but if we realize that all we really need now is that T(n)< cn^{log₂ 3} + bn
and that the 3's nicely cancel, then all we need is (3b + 2) / 2 < b       so...
3b + 2 < 2b
3b - 2b < -2       well well well
b < -2

Hence, by induction on n

T(n) < cn^{log₂ 3} + bn

is true for all n > 1       if b< -2 and 1- b < c , so nice choices are b = -2 and c = 3.
which looks a whole lot like the other day