Week 8 & 9: Proving negation, Algorithm Analysis

Quizzes always make me nervous. Well, what wouldn't make me nervous if it is graded, but the thing about the quizzes is that it comes back every week. It is a bit pressure sometimes, but there is an advantage of taking quizzes as well. The good thing about taking quizzes that I found is that it is the opportunity to test myself if I studied material correctly. The given problem for each quiz is asking fairly basic concept of what we learned in previous week. What I learned from quizzes actually helped me in Assignment #2.

Again(I wrote about quiz last week as well), I got quiz #6 wrong. I think I was misunderstanding about proving negation or didn't apply disproving the statement by proving negation flexibly.

Suppose there is a statement that you should prove or disprove. Let's say, after the brainstorming in my head, if I figured out that the given statement is false so I have to disprove it. When disprove the statement, most of the times you negate the given statement and try to find a counterexample. If I can show a counterexample, then that is enough to prove the negation is true. If I show the negation is true, then the original statement is disproved.

Here is the statement from Quiz #6:

                For all real numbers x, y, if x and y are both positive, then


Now, I want to disprove this statement, so I found the negation and showed there exists a counterexample.


 Let    . Then 
Let  . Then  .
Notice, . # 
Then, . # algebra
Then,  . # algebra
Therefore, 
Thus, .


Note that we don't need to indent anything when you show that there is a counterexample. You indent the next proof line only when you assume something. But in this case, showing negation is true, we only introduce there exists a counterexample, so we can write the each step without any indentation.

After this quiz, I realized that I didn't write some of my proofs in assignment #2. Thanks to the quiz, I could handed in the right format of proofs.