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