Week 12-Proof by Induction

        This week, I was taught proof by induction. This topic is not unfamiliar to me since I already learn it from MAT137. However, by re-learning it in CSC165, my understanding was solidified.  I think the hard part about proof by induction is the idea that by assuming a term works and later proving that the next term works, I am able to demonstrate that all term works. After being taught again in CSC165, I was convinced by the prof that proof by induction does work.
         Proof by induction is a proof technique used to establish a given statement for all natural numbers. It is similar to the idea of dominoes, in which by knowing that domino0(d0) works, I know that d1 works, then d2, then d3 and so on until all dominoes (all natural numbers) have been enumerated. The general structure for proof by induction goes like this:
 1. Assume d0 does fall
 2. Base case: d0 falls # by assumption
 3. Induction step: - assume n a generic natural number, and that dn falls
                              - then dn+1 falls # dn will hit dn+1
                              - then for all n, dn falls implies dn+1 falls
                              - then for all n, dn falls
                              - then d0 falls implies for all n, dn falls
Basically, the central idea is that after proving that the base case works, assume the assumption works for dn, and try to arrive at a conclusion that dn+1 also works.
        Here is an example of proof by induction, (without the quantifiers and bookends):
 claim:

proof:

Lastly, proof by induction is a topic that comes easy to me since I already learned it before. However, the problem about diagonals presented in class troubles me. I was unable to figure out a clear pattern to the boxes since there are too many different combinations of dimensions for the box. Thanks to Loora's blog, I was able to gain some insight.

http://looralicsc165slog.blogspot.ca/2014/11/last-problem-solving.html?showComment=1417589892018#c163994337424380139

Week 11- Halt, computability and many other confusions

        This week, I was introduced to the most confusing concept ever----that nobody can write a halt(f,n) that works for all programs. In order to recount my troubles, I have to first explain what is halt. Basically, halt is a Python function with two arguments. The first argument takes any other function f, and this function f has to take a single input n. The second argument is any input n that can go into the function f. What halt does is that it examines the code in f, and all the data in n, then return the boolean value True if f(n) halts at a certain value of n. If f(n) does not halt at any value of n, then halt(f,n) returns the value False. For some programs, it is possible to write a halt function that tests if the function halts.
        For instance, a halt function can be written to test if function may_halt halts at a specific s.

All I need to do is to check the length of string s. If length of s is not even, which means it's odd, then the program may_halt halts by printing the string s and the string " has odd length", while halt(may_halt, s) returns the value True. Similarly, if the length of s is even, then may_halt(s) iterates forever nonstop and halt(may_halt, s returns False. However, I cannot write a halt for function collatz(n). Maybe in the near future, someone may come up with a code for halt that tests if collatz halts or not, but as for now, no one has any idea how. All we know is that collatz halts for every single n up to more than 2^58, but we don't know if it halts for all n in the set of natural numbers.

Hence, although it is possible to write a halt for may_halt, it is impossible to write a halt(f,n) that works for all programs. The impossibility to write a universal halt confuses me and I could not comprehend why is this concept true. I understand that for functions like collatz, I might not be able to write a halt function. But what makes computer scientists so certain that it is impossible to write a halt that works for all programs? For instance, the fact that we don't know if alien exists does not necessarily mean that they don't exist. It could be that aliens do exist but we just haven't encounter one yet. My confusion is cleared after I was shown its proof.

        The proof for the claim that nobody can write halt(f,n) uses proof by contradiction. Now, consider the function sushi in two cases:

For the first case, assume sushi(sushi) halts, then halt(sushi, sushi) is True and the while loop iterates forever (an infinite loop), which means that sushi(sushi) does not halt (I arrived at a contradiction). For the second case, assume sushi(sushi) does not halt, then halt(sushi, sushi) is False and 2 is returned. This also poses a contradiction since it would mean that sushi(sushi) does halt. Thus, because contradiction occurred in both cases, we cannot write halt(f,n). 

Week 10-Proving General Statements

        From this week and from last week, I learned proofs that involve the definition of lower_bound, upper_bound and limits. Such proofs are very specific about the functions involved in the definitions, and  a function has to be given in order for the proof to work. However, this week, I learned how to prove general statements that does not involve a specific function. In other words, I need to proof certain claims for a general function f and g. What makes this week's material easy is that all these proofs involve similar concepts and formats. The only important thing to keep in mind is to memorize the definition of upper-bound, lower-bound, limits and their corresponding negations. Here is an example of a proof for a general statement:

To begin the proof, I first assume that f, and g both belong to the set of function F. This is because the proof asks me to prove the general statement for all f and g in F. Then I proceed by assuming the antecedent as usual. And from the antecedent, I know that f is lower-bounded by g, hence I can state its definition in the next line. Because I have to assume the antecedent and arrive at the consequent, I have to arrive at the definition that f^2 is lower-bounded by g^2. Hence I have to prove that

is true (where f(n) is f^2 and g(n) represents g^2). From this understanding, I have to pick values for both c and B. Since I don't really know how the proof will turn out, I left the pick c and pick B line empty for now and start by assuming the domain and the antecedent in the following line. Next, I squared f. Since from the antecedent, I know that f is greater than or equal to c'g, I also know that its square is greater than or equal to the square of c'g. In order to use the definition of f lower-bounded by g, n has to be greater than B', hence B can equal to B'. Now that I know what to pick for B, I can go back and write pick B= B'. And because B' is a natural number, B is also a natural number. Then I proceed with my previous calculation and got to that f^2 is greater or equal to c'^2 times g^2. In order to arrive at the consequent that f^2 is greater than or equal to cg^2, all I have to do is make c = c'^2. Hence I know what values to pick for c. And because c' is a positive real number, and real numbers are closed under multiplication, I can state that c is also a positive real number. Now that the proof is finished, all i have to do is to state the bookends and conclude the original claim.

        In conclusion, it is much faster to figure out the values for c and B before tackling the problem. To be able to do this, quickly formulate the proof on a piece of scrap paper. Hence, by figuring out what I have to do in order to arrive at the consequent, I can write up the proof much faster than having to change my c and B values constantly.

Week 9-Prove big-Oh of non-polynomials using limits

        In this week's class, I was taught how to prove that a non-polynomial function(such as an exponential function) grows faster than a polynomial function. To devise such a proof, I need to first learn the the definition of limits and the L'Hopital Rule. A good thing about this lesson is that I was recently taught the application of the L'Hopital Rule, however, the definition of limit used in CSC165 differs from the one I learned in MAT137. To begin, L'Hopital Rule is used to compute the derivative (or the limit) of a function in the form of f/g, where f and g are functions with g not equal to 0. An example is:

where I applied the L'Hopital Rule twice to obtain a denominator that is not equal to 0.

The value I received is positive infinity, meaning that as n approaches positive infinity 3^n/3n^2 also becomes increasingly large (also positive infinity). In other words, as n increases, 3^n becomes much more larger than 3n^2. This understanding is used to prove that 3^n grows at least as fast as 3n^2.

Now here is a complete example for proof using definition of limits:

        In conclusion, to prove that an exponential function is lower-bounded by a polynomial function, first assume c and B. Then prove that the limit of the exponential function divide by the polynomial function approaches infinity when n also approaches infinity. Later, state the formal definition of the limit and pick n in terms of n' and B. Then, just use the definition of limit to prove the consequent of the definition of lower_bound. To sum up, this type of proof is no different than the materials covered last week (such as the proof for lower- and upper-bound). The only difference is that the definition of limits is applied. Hence, I found this week's class to be very easy to understand.