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!

Genesis!

So here's my first post for the SLOG. Over the course of this semester, you can expect to find weekly posts where I talk about things related to the course (milestones, ideas, etc.).

Anyway, let's talk about complete induction. At first, I was quite confused by it because I couldn't understand how it differs from simple induction. However, after doing assignment 1 and the second tutorial problem set, I finally got it.

For now, the material I'm having trouble with is well-ordering. I haven't got time to review it yet, but I expect to do so in the next day or two, while preparing for the first test.