Unwinding Woes

It's been almost 2 months since the start of the semester. Time surely flies, doesn't it? It's been one though week for me, with midterms and assignments. It's not going to get any easier next week as I have another midterm and 3 assignments (one of which is from this course) all due on Friday.

Meanwhile in 236, the course is getting harder as I move into uncharted territory: unwinding. At first, I find it challenging to come up with a closed form of an endlessly expanding statement. After working on the tutorial problem set last Thursday, I find it important to write your equation in certain way.

Take Q2 for example, where n = 3^k. On my first attempt, I substituted n for 3^k right from the get go and I ended up with a messy statement with no pattern readily visible. Then I looked at tutorial solution and I hit myself in the head. If we use n, we can come up with a "sigma" to close the expansion, and use the formula for geometric series (not that I know anything about geometric series).

The course has given me no major problem before this, but with unwinding and mergesort, it's going to get more interesting. Especially since unwinding was not covered in 165, IIRC.

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.