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

MAT246 Lecture3.docx

5 Pages
Unlock Document


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


Join OneClass

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

Sign up

Join to view


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.