# Homework #10

Please, read the entire chapter 9. We did not cover it in
class the way it is presented in the text-book, however, you will find that I
touched upon many ideas mentioned in it.

**Section 9.2**, Problems 10, 26, 30 36

**Section 9.3**, Problems 9, 21, 32, 36

# Section 9.4. 19 b), 26, 34

# Section 9.5. 26

## Not for submittal

As for solving recurrence equations, consider the generic
form of the equations we discussed in class:

T(n) = a * T(n / b) + f(n) with initial condition T(1) =
f(1), where a and b are constants and f(n) is some function depending on n,
e.g. f(n) = 1, or f(n) = n or f(n) = 2 * n^{2} and so on

Just to familiarize yourself with the technique of solving
such a type of recurrence equation, try to solve this equation for the
following cases:

a)
a = 3, b = 2, f(n) = 1

b)
a = 2, b = 3, f(n) = n

When it comes to the sum, you can approximate it to a reasonable
simpler form. For instance, if the sum, equals n^{2} + n, you can treat
it to be just n^{2}.