Class Notes (835,856)
Canada (509,444)
Mathematics (2,835)
MAT246H1 (30)
Regina (8)
Lecture

MAT246 Lecture3.docx

5 Pages
197 Views
Unlock Document

Department
Mathematics
Course
MAT246H1
Professor
Regina
Semester
Fall

Description
MAT246 Lecture3 (2012-09-26) Ex. How many subset of {1...n} are there? For example, if n=1, there are 2 subsets. Prove: n P 1…n +)|= 2 A: base case, n=1, LHS = P 1 +)|= 2, RHS = 2 = 2. That is LHS = RHS. B: Assuming the above formula is true. Then assume k P 1…k +)|= 2 ,k ≥ 1, then P 1…k + 1 +)|= |S = 1…k + 1 ,k + 1 ∈ S ∪ T = 1…k + 1 ,k + 1 ∉ T +| P 1…k + 1 +)|= |Pk+1 ∪ Pk+1 | = Pk+1 |+ |Pk+1| = 2 + 2 = 2 k+1 * + k+1 That is P 1…k + 1 )| = 2 . Thus the statement holds for all n. Nonsense proof:  Claim: if k ∈ ℤ, then k + 1 < 𝑘. Proof: suppose the claim holds for k ∈ ℤ, we then have k+1 (k+1)+11 then n is prime Proof: check that n=2 is prime. Suppose n is prime, then n+1=2+1=3 is prime. So by induction all n>1 are prime. Nonsense Proof: proof by example; induction step is false  Claim: for all pairs x,y ∈ ℕ × ℕ, then we have x = y. Proof: A. base case: if x=1, y=1, certainly x=y B. induction: suppose the claim holds for all (x,y) s.t. xx'-1+1=y'-1+1=>x'=y' Nonsense proof: false assumption When inducting with pairs: we proceed by induction on x, base case x=1; Then, we proceed by induction on y, base case y = 1; suppose y = k, 1 = y = k a ≡ b mod m . Thus the theorem holds Case 2: r≠r’, since we assume a=pm+r and b=qm+r’, that is r and r’ are smaller than m. Thus r-r’ cannot be divided by m. Then if we divide a-b by m, there will be a remainder which is not a multiple of m. That is, a − b ≡ 0 mod m does not hold. Thus, the theorem holds. Theorem 3.1.4: for a given modulus m, each integer is congruent to exactly one of the numbers in the set {0,1,2,…,m-1}. Theorem 3.1.5: if a ≡ b mod m and c ≡ d (mod m), then i. (a + c ≡ b + d (mod m), and ii. ac ≡ bd (mod m) Proof: Known a ≡ b mod m and c ≡ d mod m , then ) a-b=sm and c-d=tm i. (a+c)-(b+d) = (a-b)+(c-d) = sm-tm = (s-t)m That is, a + c + b + d ≡ 0 mod m => a + c ≡ b + d mod m ( )( ) Thus, the theorem holds. ii. a=b+sm and
More Less

Related notes for MAT246H1

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit