Review

I just finished reviewing the lecture notes. I didn't write Q3, and Q4 in Assignment3, which is miserable for me, because I total have no idea about the question. However, I got the questions now, after reviewing the lecture notes. It is too late to make assignment3 up, but luckily, its not late for the final exam. My mistake told me I should prepare everything early, and do my best to follow the prof during lecture. I'll use much more time then the lecture if i fall behind. I'll continue working on csc236 until the final exam ends. I'll rewrite all questions(questions in term tests, quizzes, and lectures) we did in this term, then review the notes again. Also, I'll start writing the aid sheet for the final exam.

Review about midterms

In midterm1, Q1 and Q2, I assume P(n) is true. However, I should first state what P(n) is. That's the reason why I lose mark in Q1 and Q2. In Q3, I didn't earn a single mark. I forgot to write the base case of structured induction which is a significant mistake. Also, in Q3, op = op1 + op2 - 1, but unfortunately, I wrote op = op1 + op2 instead, that's where I made mistake.

In midterm2,  Q1, I state for all natural number i, 0 < i < n ... in assumption. I should also state i is power of 2, not arbitrary. I just earn one mark on Q2, and ill discuss it with TA later, for learning how to do that right.

Complete Induction

Content:
[∀ n ∈ N, p(0), ..., p(n - 1) => p(n)] => ∀ n ∈ N, p(n)

Example:
Claim: Every natural number greater than 1 has a prime factorization.
Proof:
Assume that ∀ n ∈ N - {0, 1} and that for all natural numbers 1 < j < n, p(j) is true. -> IH
Then n is either prime or not prime.
Case1: n is prime Then n = n is its own prim factorization.
Case2: n is not prime Then n has ate least 3 factors, 1, n, and x ≠ 1, x ≠ n. So 1 < x < n, som x is a factor different from 1 and n. Then also, n has a factor y = n/x, y ≠ n and y ≠ 1, since otherwise xy ≠ n.
Now by IH x and y have prime factorization, we conclude n has a prime factorization, that is p(n).
Since n was arbitrary, this shows that ∀ n ∈ N - {0, 1}, [p(2), p(3), ..., p(n - 1)] => p(n)
Conclude ∀ n ∈ N - {0, 1},  n has a prime factorization.

Mathematical Induction

Content:

[ p(0) ∧ (∀  n ∈ N, p(n)  => p(n + 1)] => ∀ n ∈ N, p(n)

Example:

Claim:  Every set with n elements has exactly 2^n subsets.

Proof:

Base Case: If n = 0, the oly set of size 0 is {} with set of subset | {{}} | = 1 = 2^0, so p(0) is true.

Induction Step:

Assume n ∈ N, and that p(n) is ture. -> IH

If S is a genetic set with | S | = n + 1. Now there is some x ∈ S, since n + 1 > 0, and we partition the subsets of S in two sets: S- is the set of  subsets of S that do contain x. Since f: S- -> S+, f(S) = S U { x } is a bijection. we know | S- | = | S+ |, by IH, | S- | = 2^n, because S- is the set of subsets of S - { x }, and | S - { x } | = n + 1 - 1 = n. So S has | S- | + | S+ | = 2^n + 2^n = 2^(n + 1) subsets. Since S was arbitrary, this meas every set of size n + 1 has 2^(n + 1) subsets, i.e. p(n + 1).

Since, for genetic n, p(n) => p (n + 1), this shows ∀ n ∈ N, p(n)  =>  p(n + 1)

Conclude, ∀ n ∈ N, p(n), by mathematical induction.