Term Test 2

The test 2 was gone. But, I did not do the good job. The questions are a little difficult to understand for me. So, I need to do more exercises in the last month.

As a part time student, I could not take office hour to ask my questions. So, an excellent textbook is very important. But, the course note is not enough to understand all material which is taught in class. For the first chapter, I read “how to prove it” as supplementary book. I have not yet found out any matched supplementary material for chapter 3.

Actually, the course note is not too bad. It only needs to add more examples and explanations. 

Chapter 3: assignement 2

In the assignment 2, we need to get close form of H(n) = H(n-1) + H(n-2) if n >2. Then based on the skill we are taught form lecture, we get H(n) = F(n + 1) by unwind. We already know the close form of Fibonacci.  So, we get final close form that combines both of H(n) = F(n+1) and Fibonacci close form.

In the book of “mcs” that is the textbook of CSC240. The author uses the method that is to prove Fibonacci to prove H(n). So, author gets a homogeneous linear form first: f(n) = a1f(n-1) + a2f(n-2) + …adf(n-d). Then get x = (1+sqr(5))/2. Quoting the theorem 21.31: if f(n) and g(n) are both solutions to a homogeneous linear recurrence, then h(n) = sf(n) + tg(n) is also a solution for all s and t of Real number, author get the same answer.

It looks that the former way is easier. But three authors of “mcs” are professors of MIT and researcher of Google. Why do they not to use that method to prove this? I has just a little bit of confusion. 

Recurrence problem

When I read some books, i found solving Towers of Hanoi problem let me understand the whole process of proof.

Everyone knew Hanoi problem. So the recursive solution has three stages.
Stage1:  Move the top n-1 disks from the first post to the first post to the second using the solution for n -1 disks. This can be done in Tn-1 steps.
Stage2: Move the largest disk from the first top to the third post. This takes just 1 step.
Stage3: Move the n - 1 disks from the second post to the third post, again using the solution for n - 1 disk. This can also be done in Tn-1 steps.

This algorithm shows that Tn, the minimum number of steps required to move n disks to a different post, is at most Tn-1 + 1 + Tn-1 = 2Tn-1 + 1.

So we can find a recurrence.

T1 = 1
Tn = 2Tn-1 + 1  for n >= 2

So we can use this recurrence to compute any number of terms in the sequence:
T1 =1
T2 = 2T1 + 1 = 3
T3 = 2T2 + 1 = 7
T4 = 2T3 + 1 = 15
...

Let us prove this Claim

the proof is by induction on n. The induction hypothesis is that Tn = 2^n - 1. This is true for n = 1 because T1 = 1 = 2^1 -1.
Assume that Tn -1 = 2^(n-1) -1 in order to prove that Tn = 2^n -1. Where n >= 2
Tn = 2Tn-1 + 1 = 2(2^(n-1) - 1 ) + 1 = 2^n -1

The first equality is the recurrence equation, the second follows from the induction assumption, and the last step is simplification.

Chapter 1: Complete Induction

Sometimes, I cannot understand the meaning of Complete Induction.  I always confuse how to use it. I have an example here which gets from “How to prove it”.

Sample: Suppose n is an integer larger than 1 and n is prime. Then P(n): 2^n -1 is prime.

We can see

n = 2, 2^n – 1 = 3

n = 3, 2^n – 1 = 7

n = 5, 2^n – 1 = 31

Then, the next prime number 7 is in N. The expression holds for every prime number less than 7. So, from complete induction, P(7)  holds. Similarly, the expression holds too for next prime number 11. Such that, I get conclusion that P(n) holds for every prime number. As a matter of fact, everyone knows this predict is not correct. But I cannot figure out where is wrong with my proof.

The definition of Complete Induction is described for all natural numbers. In this sample, I do not use 4 and 6 in the proof because they are not prime number. Does this not obey the rule of Complete Induction? I do not think so.  At ton of proofs, we define the base case which is from bigger numbers than 1. That means the domain of variable may not include all natural numbers.

Chapter 0: sample

Let’s start my first blog of csc236.

In the chapter 0 Preliminaries of Notes (“Notes” below), the author defines “Partial Order” is “if R is antisymmetric and transitive”. At first, I thought the definition is wrong because this definition of this term in the “How to prove it” (“How” below) is “if R is reflexive, transitive, and antisymmetric”. As if the definition in Notes is missing reflexive. From definition 4.4.1 of “How”, R is said to be antisymmetric if x in A and y in A then xRy and yRx implies x = y. Base on that, xRy and yRx are correct if antisymmetric holds. That could to say that antisymmetric includes reflexive, I guess.

The reason of confusion is the sample R3 in the Notes. R3={(a,b): a and b are persons and a is an ancestor of b}. Notes explains that R3 is a partial order. Form definition of reflexive, we can image from R3: I and I are persons and I am ancestor of I. Oh, I become my daddy, or I am my son, so I am I. Does it sound weird? Of course, there is not any defect in the logic. But, I do not think this sample could help us to understand the term. So, this sample is used in the notes is not reasonable.

This is my personal opinion.