Homework Assignment #7.5

To be well acquainted with the proof of the master theorem.

To feel very comfortable with the method for solving recurrence relations for typical divide-and-conquer algorithms, including the use of the “change of variable” technique.

Show all work clearly and legibly. i.e., justify your answers. Write or type neatly.

Write the proof of the master theorem in the format of a two-column proof. You should refer directly to the lecture notes to guide you along.

What does a good two-column proof look like? Statements are found in the left column and corresponding justifications for each statement are found on the right. Each statement and reason should be numbered for ease of reference. Each statement must be a mathematical statement that has a truth value. For example, an equation (e.g., $2x+5 = 1$) is either true or not, whereas an expression (e.g., $2x+5$) does not have truth value. Each step must be justified by a reason in the right column. If you cannot provide a clear and convincing reason for a particular statement in your proof, then you need to give the matter further thought and you may consider adding additional steps to improve the argument.