Unwinding; Week#6

Example of recursively defined function:

defines the value of the function at some natural number n in terms of the function's value at the previous number, n-1, whereas the function at 0 is explicitly given. 

- we would refer to the first part of the definition as the base-case and to the second part as the inductive step of the recursion. 

when proving a recursively define function, first thing we would have to do is the step called "unwinding", which derives to find a closed-form formula for a function, f(n).

How-To-Do: we unwind(a technique called repeated substitution) the recursive definition of f(n) by simply repeatedly applying the induction step of the definition to smaller and smaller arguments of function(recursive steps), f. we keep this step until we discover a pattern that will convey us a closed-form formula. 

1.  find closed-form formula for the function by using unwinding technique

2. prove that the closed-form formula is equal to the recursive definition of the given function by using an appropriate induction.

CompleteInduction-Example

Proof. We prove by complete induction that any amount of at least 8 cents can be made by using 3 cents and 5 cents. The induction hypothesis, P(n) will be:

 there is a collection of coins whose value is n + 8 cents.

"simply follow the template given in the previous post about complete induction."
"very similar to the Postage question we did during the lecture"

BaseCase: P(0) is true because a 3 cent coin together with a 5 cents coin makes 8 cents

Inductive Step: We assume P(m) holds for all m <= n, and prove that P(n+1) holds. There are two different cases; we prove by cases

Case 1. (n+1=1), then (n+1)+8 = 9 cents, we can make 9 cents by using 3 x 3 cents = 9 cents
Case 2. (n+1=2), then (n+1)+8 = 10 cents, we can make 9 cents by using 2 x 5 cents = 10 cents

Case 3. (n+1 >= 3), then 0 <= n - 2 <= n, so by the complete induction hypothesis, for n-2 cents amount can be made. Now by adding a 3 cents coin; n-2 + 3 = n+1 can be made

Conclude that P(n), any amount of 8 cents or more can be made out of 3 cents and 5 cents coins, holds for every positive natural integers, n.

Well-Ordering Induction

Template: Well-Ordering Proofs

Stating the template for a well-ordering proof steps would be adequate to give general explanation of its definition;

- Define the set, C, of counterexamples to P being true

- Use a proof by contradiction and assume that C is non-empty

       contradiction definition: 

       a form of proof that establishes the truth or validity of a proposition by showing that the         proposition's being false would imply a contradiction

- By the well ordering Principle, there will be a smallest element(introduced a new variable), n in C.

- Reach a contradiction (somehow) - often by showing how to use n to find another member of C that is smaller than n.

- Conclude that C must be empty, that is, no counterexamples exist.

Complete Induction

Complete Induction

only minor difference from a mathematical Induction is that it allows us to assume more than just P(n), whereas, in a mathematical induction, we only assume that P(n) is true and try to prove that P(n+1) is also true.  In the inductive step of our complete induction proof, we may assume P(0),P(1),....,P(n) are all true and based on our assumption, we prove that P(n+1) is also true. 

A Template for Induction Proofs:

1. State that our proof is by complete induction to convey the overall structure of the proof of our upcoming arguments and statements.

2. Define an appropriate predicate P(n)

assume that P(0),P(1),...P(n) is all true. The eventual conclusion of the induction proof will be that P(n) is true for all positive n. Thus, we should produce the predicate P(n) so that follows from the conclusion. Often, it can be derived from the proposition that we are trying to prove. 

The predicate P(n) is called the Induction Hypothesis.

3. Prove that P(n) is true. This step of the proof is called the Base-Case(or Basis); showing that the statement holds when n is equal to the lowest value that n is given in the question.

4. Prove that P(n) implies P(n+1) for every positive natural integers, n. This step of the proof is called the Inductive Step.

by assuming the induction hypothesis, then use this assumption to prove the statement for n + 1; this step requires some ingenuity and appropriate mathematical approach.

5. Based on the facts that have been made in the previous steps, we may conclude that P(n) is true for all non-negative integers, n. 

think the induction as the domino effect:
1. the first domino will fall
2. whenever a domino falls, its next neighbor will also fall 
- P(0) -> P(1) -> P(2) -> P(3) -> ... -> P(n)
then conclude that all of the dominoes will fall; P(n) is true for all positive natural integers, n

TheFirstAssignment! Due

The first assignment from CSC236 was not as difficult as i thought it would be, but definitely required hours and hours of time-efforts. 

The main obstacle that i have encountered with the course at this point is that even thought i have clear understanding of concepts of course material such as the Induction and every steps make sense and i can sort of grasp the whole idea and follow along. However!! with a given example or a problem, i found very hard to figure out the inductive step of where by using induction hypothesis, i am supposed to make a appropriate approach to show connection between the gap of implication of P(n) to P(n+1) with ingenuity and suitable mathematical approaches.

the most parts of the assignment was done by Danny during the lecture, i just had to follow what he had done but needed to make modifications to them but not too hard since i was given with basic frame of the proofs.ThankYou!

i really hope to get a good grade on this, which would indicate well-to-do within the course later . 

Mathematical Induction

Mathematical induction, also called simple induction, is a method of mathematical proof usually used to prove that a given statement is true for all nutural positive numbers. This induction seems to me as one that is, by far the most powerful and commonly-used proof technique in computer science and mathematics, and SIMPLE!! as the name tells.

the Principle of Simple Induction

- Establish that the property is true at the starting point(Predicate), simply prove that P(n) is true
- Establish that the property spreads from each natural number to its successor:

explanation:
Let P(n) be a predicate. If:
- P(0) is true, and <- BaseCase
- P(n) implies P(n+1) for all non-negative integers, n. <- Induction Step.

Nothing too complicated about this induction. We've already covered this in the previous course of CSC165. But sure it is definitely important to have a clear understanding of this fundamental and essential one-of-kind induction. 

Back To School Back To SLOG

This is my whole new beginning of a journey to be success in the course,
                                             
"Introduction to the theory of Computation"

I thought of this idea of making ourselves a Blog"SLOG" is great in terms of that, this can actually give us an opportunity to keep track of our improvements and developments within this course, when looking back the posts that we have made after a certain time passed.

while writing posts, these are the things i would look forward

1st. i hope while writing posts on the course material, i would gain more clear understanding and insight of the concept. Probably this would be a good opportunity for me to review what i have studied and check whether there is any misunderstandings or things that i have missed while studying specific topic.

2nd. by posting my experience and my thoughts on the course, i would share mine with other classmates, such that i can actually be part of this course's community and feel like we're actually moving forwards to where we say "success" together with everyone in this course.

3rd. to keep up with posts, i would have to do certain amount of research and study in order to write posts, which prevents me from being behind from course materials and lectures. ThankYou!

I guess everyone in this course who are working their best to do their best has one thing in common!!!
becoming fulfilled in this course with a decent grade, which requires time and efforts.

i would expect nothing from this course if i don't deserve to have them!! No Give-Up No Lazy

i will try my best and the best for the rest of the term.