Induction • Prove that ∑_(i=1)^n▒i=n(n+1)/2, ∀n≥1 • Base case, n=1 ○ ∑_(i=1)^i▒i=1=(1×2)/2 • Induction step ○ For n 1 ○ Assume ∀k s.t. 1≤kn, ∑_(i=1)^k▒i=k(k+1)/2 ○ Then∑_(i=1)n▒i=(∑_(i=1)(n−1)▒i)+n=(n−1)(n)/2+n=n(n+1)/2 Proposition 1: Well-ordering of Z • Statement ○ Every nonempty set S of Z(≥0) has a unique minimum element ○ That is, ∃!m∈S s.t. m≤s, ∀s∈S • Proof (Existence) ○ Assume S is finite § We will argue by induction on |S| § Base case: |S|=1 □ This is clear § Assume |S| 1 □ Choose x∈S, then |S∖{x}|=|S|−1 □ By induction S∖\x} has a minimum value: call it m □ Case 1: xm, then x is a minimum value of S □ Case 2: mx, then m is a minimum value of S ○ Now we prove the general case § Choose x∈S § Let S^′≔{s∈S│s≤x} § Then |S^′ |≤x+1∞ § Choose a minimum element of S: call it m § Let s∈S □ If s∈S^′, then m≤s □ If s∉S′, then m≤xs § In either case, m≤s, so m is a minimum element of S ○ This proves existence • Proof (Uniqueness) ○ Suppose m and m′ are both minimum elements of S ○ m≤m′, and m^′≤m ○ Thus, m=m^′ ○ This proves uniqueness Proposition 2: The Division Algorithm • Statement ○ Let a,b∈Z, where b 0 ○ Then ∃!q,r∈Z s.t. a=qb+r, and 0≤rb • Proof (Existence) ○ Let S≔{a−bq│q∈Za−bq≥0}⊆Z(≥0) ○ S is not empty § Let q∈Z s.t. q≤a/b § Then bq≤a § ⇒0≤a−bq § i.e. a−bq∈S ○ Thus S contains a unique minumum elemtent: call it r ○ Choose q∈Z s.t. § a−bq=r § ⇒a=bq+r ○ We still need to show 0≤rb § We know 0≤r, since r∈S, so we just need to show rb § If r≥b, then a−b(q+1)=a−bq−b=r−b≥0 § But a−b(q+1)∈S, and it is less than r § This is impossible, since r is minimum element of S § Thus, rb ○ Therefore we ve proven the existence of q and r
