Assignment Two Evaluation

For the question one, it took more for me to come up with a pattern then the proving. I wrote down all the possible cases until the length of the binary string became 6 and found a pattern of P(n) numbers. However, I still had to figure out the reason behind. Otherwise, my proof will become an intuition or a guess. I found out that P(n-1) and P(n-2) are related to P(n) and this is somewhat similar to Fibonacci's sequence. From this question, I learned that finding a pattern might be the toughest step and the rest is easy. I think what we are learning in this course is more about finding pattern and the lectures are there to help us explain the pattern in words. From now on, I will look closer to the pattern when it comes to proving or coming up with an algorithm.
The question two was about expressing time complexity of a binary search algorithm. It was similar to the question we learned in a tutorial and a lecture. It was just that we did not go deeply inside the concept. First, I had to prove that the P(n) is non-decreasing. It was basically the one from the textbook. I proved the time complexity in two different ways. The first was by inequality and proving both upper bound and lower bound. The second was using the master theorem.