Tutorial 3 Recap

Let's recap the solution of tutorial 3 questions.

Q1: We want to prove that for some positive rational number c, P(n): T(n) >= c log(n).

• Case 1: n = 1
• No problem here: log(1) = 0, so c log(1) = 0 for all c
• Then T(1) = 1 >= 0 = c log(1)    # P(1)
  
• Case 2: n > 1
• T(n) = 1 + T(ceiling(n / 2))
         >= 1 + c log(ceiling(n / 2))
         >= 1 + c log(n / 2)
         >= 1 + c log(n) - c log(2)
         >= 1 + c log(n) - c
  
• What we want: turn 1 + c log(n) - c into c log(n)
  Remember that we want to prove P(n) for some c
  Then we can set a value of c such that P(n) holds (set c = 1)
  Then T(n) >= 1 + (1) log(n) - (1)
  T(n) >= (1) log(n)    # P(n) for c = 1
  
• Then there is a rational number c such that T(n) >= c log(n).

Q2: We want to prove that for all natural number k, P(n): T(2^k) = k + 1. (Note: This is actually similar to the quiz given in the tutorial. The only difference is, in the quiz we use T(3^k), but the solution's logic is the same.)

• Base Case (n = 1): T(2) = 2 = (1) + 1    # P(1)
  
• Induction Step: Assume P(n) for an arbitrary natural number n.
• Then T(2^k) = k + 1
  T(2^(k + 1)) = 1 + T(ceiling(2(k + 1) / 2))
                       = 1 + T(2^k)    # we can ignore the ceiling because 2^k is always an integer
                       = 1 + k + 1      # by IH
                       = k + 2            # P(n + 1)!
  
• Then P(n) => P(n + 1)
  
• Then for all natural number n, P(n)

Q3: We have to unwind G(n). Unfortunately, we didn't get the chance to finish this question during the tutorial.

Well Ordering

As I have said in my previous post, I was struggling to understand the principle of well-ordering. Thankfully, someone in Piazza kindly posted a link (go to page 43) that explains it in a very good way.

Basically, what we do in well-ordering is assume that a set of counter-examples to P(n) called C exists and that c is the smallest element of C. In the link I provided, P(n): 1 + 2 + 3 + ... + n = n(n + 1)/2

• Then, for all n < c (e.g. n = c - 1), P(n) holds, since the smallest value of n where P(n) is false is n = c.
  
• With this in mind, we show P(c - 1):
  1 + 2 + 3 + ... + (c - 1) = c(c - 1)/2
  
• Then we modify P(c - 1) to be P(c) and show that P(c) is in fact, true:
  1 + 2 + 3 + ... + (c - 1) + c = c(c - 1)/2 + c    # add c to both sides
                                             = (c^2 - c + 2c)/2
                                             = (c^2 + c)/2
                                             = c(c + 1)/2         # P(c + 1)!
  
• But P(c) is suppose to be false, this is a contradiction!
  
• Then, P(c) should be true and there is no counter-example to P(n).
  
• Therefore for all n, P(n) holds.

Thanks to Alex for the awesome post!