20 CHAPTER 1.PRELIMINARIES plurality_zoo [animal+'s'for animal in zoo] plurality_zoo ['baboons','beetles','elephants','ostrichs','snakes'] Almost like it says:we add an "s"to each animal name,for each animal in the zoo,and place them in a new list.Perfect.(Except for getting the plural of "ostrich"wrong.) Lists of Integers One final type of list,with numbers this time.The srange()function will create lists of integers.(The“s”in the name stands for“Sage”and so will produce integers that Sage understands best.Many early difficulties with Sage and group theory can be alleviated by using only this command to create lists of integers.)In its simplest form an invocation like srange(12)will create a list of 12 integers,starting at zero and working up to,but not including,12.Does this sound familiar? dozen srange(12);dozen [0,1,2,3,4,5,6,7,8,9,10,11] Here are two other forms,that you should be able to understand by studying the examples teens srange(13,20);teens [13,14,15,16,17,18,19] decades srange(1900,2000,10);decades [1900,1910,1920,1930,1940,1950,1960,1970,1980,1990] Saving and Sharing Your Work There is a "Save"button in the upper-right corner of the Sage Notebook.This will save a current copy of your worksheet that you can retrieve your work from within your notebook again later,though you have to re-execute all the cells when you re-open the worksheet. There is also a "File"drop-down list,on the left,just above your very top compute cell (not be confused with your browser's File menu item!).You will see a choice here labeled "Save worksheet to a file..."When you do this,you are creating a copy of your worksheet in the sws format (short for "Sage WorkSheet").You can email this file,or post it on a website,for other Sage users and they can use the "Upload"link on the homepage of their notebook to incorporate a copy of your worksheet into their notebook. There are other ways to share worksheets that you can experiment with,but this gives you one way to share any worksheet with anybody almost anywhere. We have covered a lot here in this section,so come back later to pick up tidbits you might have missed.There are also many more features in the Sage Notebook that we have not covered. 1.5 Sage Exercises 1.This exercise is just about making sure you know how to use Sage.You may be using the Sage Notebook server the online CoCalc service through your web browser.In either event,create a new worksheet.Do some non-trivial computation,maybe a pretty
20 CHAPTER 1. PRELIMINARIES plurality_zoo = [ animal + ' s ' for animal in zoo ] plurality_zoo [ ' baboons ' , ' beetles ' , ' elephants ' , ' ostrichs ' , ' snakes ' ] Almost like it says: we add an “s” to each animal name, for each animal in the zoo, and place them in a new list. Perfect. (Except for getting the plural of “ostrich” wrong.) Lists of Integers One final type of list, with numbers this time. The srange() function will create lists of integers. (The “s” in the name stands for “Sage” and so will produce integers that Sage understands best. Many early difficulties with Sage and group theory can be alleviated by using only this command to create lists of integers.) In its simplest form an invocation like srange(12) will create a list of 12 integers, starting at zero and working up to, but not including, 12. Does this sound familiar? dozen = srange (12) ; dozen [0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11] Here are two other forms, that you should be able to understand by studying the examples. teens = srange (13 , 20) ; teens [13 , 14 , 15 , 16 , 17 , 18 , 19] decades = srange (1900 , 2000 , 10) ; decades [1900 , 1910 , 1920 , 1930 , 1940 , 1950 , 1960 , 1970 , 1980 , 1990] Saving and Sharing Your Work There is a “Save” button in the upper-right corner of the Sage Notebook. This will save a current copy of your worksheet that you can retrieve your work from within your notebook again later, though you have to re-execute all the cells when you re-open the worksheet. There is also a “File” drop-down list, on the left, just above your very top compute cell (not be confused with your browser’s File menu item!). You will see a choice here labeled “Save worksheet to a file...” When you do this, you are creating a copy of your worksheet in the sws format (short for “Sage WorkSheet”). You can email this file, or post it on a website, for other Sage users and they can use the “Upload” link on the homepage of their notebook to incorporate a copy of your worksheet into their notebook. There are other ways to share worksheets that you can experiment with, but this gives you one way to share any worksheet with anybody almost anywhere. We have covered a lot here in this section, so come back later to pick up tidbits you might have missed. There are also many more features in the Sage Notebook that we have not covered. 1.5 Sage Exercises 1. This exercise is just about making sure you know how to use Sage. You may be using the Sage Notebook server the online CoCalc service through your web browser. In either event, create a new worksheet. Do some non-trivial computation, maybe a pretty
1.5.SAGE EXERCISES 21 plot or some gruesome numerical computation to an insane precision.Create an interesting list and experiment with it some.Maybe include some nicely formatted text or TEX using the included mini-word-processor of the Sage Notebook (hover until a blue bar appears between cells and then shift-click)or create commentary in cells within CoCalc using the magics %html or %md on a line of their own followed by text in HTML or Markdown syntax (respectively). Use whatever mechanism your instructor has in place for submitting your work.Or save your worksheet and then trade with a classmate
1.5. SAGE EXERCISES 21 plot or some gruesome numerical computation to an insane precision. Create an interesting list and experiment with it some. Maybe include some nicely formatted text or TEX using the included mini-word-processor of the Sage Notebook (hover until a blue bar appears between cells and then shift-click) or create commentary in cells within CoCalc using the magics %html or %md on a line of their own followed by text in html or Markdown syntax (respectively). Use whatever mechanism your instructor has in place for submitting your work. Or save your worksheet and then trade with a classmate
The Integers The integers are the building blocks of mathematics.In this chapter we will investigate the fundamental properties of the integers,including mathematical induction,the division algorithm,and the Fundamental Theorem of Arithmetic. 2.1 Mathematical Induction Suppose we wish to show that 1+2+…+n=nn+1 2 for any natural number n.This formula is easily verified for small numbers such as n=1, 2,3,or 4,but it is impossible to verify for all natural numbers on a case-by-case basis.To prove the formula true in general,a more generic method is required. Suppose we have verified the equation for the first n cases.We will attempt to show that we can generate the formula for the (n+1)th case from this knowledge.The formula is true for n=1 since 1=1(1+1) 2 If we have verified the first n cases,then 1+2++n+(m+1)=nn+) +n+1 2 =n2+3n+2 2 =m+1n+1)+刂 2 This is exactly the formula for the (n+1)th case. This method of proof is known as mathematical induction.Instead of attempting to verify a statement about some subset S of the positive integers N on a case-by-case basis,an impossible task if S is an infinite set,we give a specific proof for the smallest integer being considered,followed by a generic argument showing that if the statement holds for a given case,then it must also hold for the next case in the sequence.We summarize mathematical induction in the following axiom. Principle 2.1 First Principle of Mathematical Induction.Let S(n)be a statement about integers for nEN and suppose S(no)is true for some integer no.If for all integers k with k no,S(k)implies that S(k+1)is true,then S(n)is true for all integers n greater than or equal to no. 22
2 The Integers The integers are the building blocks of mathematics. In this chapter we will investigate the fundamental properties of the integers, including mathematical induction, the division algorithm, and the Fundamental Theorem of Arithmetic. 2.1 Mathematical Induction Suppose we wish to show that 1 + 2 + · · · + n = n(n + 1) 2 for any natural number n. This formula is easily verified for small numbers such as n = 1, 2, 3, or 4, but it is impossible to verify for all natural numbers on a case-by-case basis. To prove the formula true in general, a more generic method is required. Suppose we have verified the equation for the first n cases. We will attempt to show that we can generate the formula for the (n + 1)th case from this knowledge. The formula is true for n = 1 since 1 = 1(1 + 1) 2 . If we have verified the first n cases, then 1 + 2 + · · · + n + (n + 1) = n(n + 1) 2 + n + 1 = n 2 + 3n + 2 2 = (n + 1)[(n + 1) + 1] 2 . This is exactly the formula for the (n + 1)th case. This method of proof is known as mathematical induction. Instead of attempting to verify a statement about some subset S of the positive integers N on a case-by-case basis, an impossible task if S is an infinite set, we give a specific proof for the smallest integer being considered, followed by a generic argument showing that if the statement holds for a given case, then it must also hold for the next case in the sequence. We summarize mathematical induction in the following axiom. Principle 2.1 First Principle of Mathematical Induction. Let S(n) be a statement about integers for n ∈ N and suppose S(n0) is true for some integer n0. If for all integers k with k ≥ n0, S(k) implies that S(k + 1) is true, then S(n) is true for all integers n greater than or equal to n0. 22
2.1.MATHEMATICAL INDUCTION 23 Example 2.2.For all integers n 3,2n>n+4.Since 8=23>3+4=7, the statement is true for no =3.Assume that 2>k+4 for k>3.Then 2k+1=2.2k> 2(k+4).But 2(k+4)=2k+8>k+5=(k+1)+4 since k is positive.Hence,by induction,the statement holds for all integers n >3. Example 2.3.Every integer 10m+1+3.10%+5 is divisible by 9 for nE N.For n=1, 101+1+3.10+5=135=9.15 is divisible by 9.Suppose that 10+1+3.10+5 is divisible by 9 for k>1.Then 10k+1)+1+3.10+1+5=10k+2+3.10k+1+50-45 =10(10k+1+3.10+5)-45 is divisible by 9. Example 2.4.We will prove the binomial theorem using mathematical induction;that is, (a+b)n= (n akon-k, k=0 where a and b are real numbers,n EN,and n n! k(n-)月 is the binomial coefficient. We first show that ()=(因+(”) This result follows from )+(”)= n! n! n-十(k-1)m-k+1月 (n+1)月 =+1- If n =1,the binomial theorem is easy to verify.Now assume that the result is true for n greater than or equal to 1.Then (a+b)n+1=(a+b)(a+b)r =a+(E(国w- E()+*+∑（风）1-
2.1. MATHEMATICAL INDUCTION 23 Example 2.2. For all integers n ≥ 3, 2 n > n + 4. Since 8 = 23 > 3 + 4 = 7, the statement is true for n0 = 3. Assume that 2 k > k + 4 for k ≥ 3. Then 2 k+1 = 2 · 2 k > 2(k + 4). But 2(k + 4) = 2k + 8 > k + 5 = (k + 1) + 4 since k is positive. Hence, by induction, the statement holds for all integers n ≥ 3. Example 2.3. Every integer 10n+1 + 3 · 10n + 5 is divisible by 9 for n ∈ N. For n = 1, 101+1 + 3 · 10 + 5 = 135 = 9 · 15 is divisible by 9. Suppose that 10k+1 + 3 · 10k + 5 is divisible by 9 for k ≥ 1. Then 10(k+1)+1 + 3 · 10k+1 + 5 = 10k+2 + 3 · 10k+1 + 50 − 45 = 10(10k+1 + 3 · 10k + 5) − 45 is divisible by 9. Example 2.4. We will prove the binomial theorem using mathematical induction; that is, (a + b) n = ∑n k=0 ( n k ) a k b n−k , where a and b are real numbers, n ∈ N, and ( n k ) = n! k!(n − k)! is the binomial coefficient. We first show that ( n + 1 k ) = ( n k ) + ( n k − 1 ) . This result follows from ( n k ) + ( n k − 1 ) = n! k!(n − k)! + n! (k − 1)!(n − k + 1)! = (n + 1)! k!(n + 1 − k)! = ( n + 1 k ) . If n = 1, the binomial theorem is easy to verify. Now assume that the result is true for n greater than or equal to 1. Then (a + b) n+1 = (a + b)(a + b) n = (a + b) (∑n k=0 ( n k ) a k b n−k ) = ∑n k=0 ( n k ) a k+1b n−k + ∑n k=0 ( n k ) a k b n+1−k
24 CHAPTER 2.THE INTEGERS =a+1+ (")+(份w+ =an+1 (”)+(】+ We have an equivalent statement of the Principle of Mathematical Induction that is often very useful. Principle 2.5 Second Principle of Mathematical Induction.Let S(n)be a statement about integers for nEN and suppose S(no)is true for some integer no.If S(no),S(no+ 1),...,S(k)imply that S(k+1)for k no,then the statement S(n)is true for all integers n≥no- A nonempty subset S of Z is well-ordered if S contains a least element.Notice that the set Z is not well-ordered since it does not contain a smallest element.However,the natural numbers are well-ordered. Principle 2.6 Principle of Well-Ordering.Every nonempty subset of the natural num- bers is well-ordered. The Principle of Well-Ordering is equivalent to the Principle of Mathematical Induction. Lemma 2.7.The Principle of Mathematical Induction implies that 1 is the least positive natural number PROOF.LetS={n∈N:n≥l}.Then1∈S.Assume that n∈S.Since0<l,it must be the case that n =n+0<n+1.Therefore,1<n<n+1.Consequently,if n ES,then n+1 must also be in S,and by the Principle of Mathematical Induction,and S=N. Theorem 2.8.The Principle of Mathematical Induction implies the Principle of Well- Ordering.That is,every nonempty subset of N contains a least element. PROOF.We must show that if S is a nonempty subset of the natural numbers,then S contains a least element.If S contains 1,then the theorem is true by Lemma 2.7.Assume that if S contains an integer k such that 1<k<n,then S contains a least element.We will show that if a set S contains an integer less than or equal to n+1,then S has a least element.If S does not contain an integer less than n+1,then n+1 is the smallest integer in S.Otherwise,since S is nonempty,S must contain an integer less than or equal to n.In this case,by induction,S contains a least element. ▣ Induction can also be very useful in formulating definitions.For instance,there are two ways to define n!,the factorial of a positive integer n. ·The explicit definition:n!=1·2.3…(n-l)·n. The inductive or recursive definition:1!1 and n!=n(n-1)!for n 1. Every good mathematician or computer scientist knows that looking at problems recursively, as opposed to explicitly,often results in better understanding of complex issues
24 CHAPTER 2. THE INTEGERS = a n+1 + ∑n k=1 ( n k − 1 ) a k b n+1−k + ∑n k=1 ( n k ) a k b n+1−k + b n+1 = a n+1 + ∑n k=1 [( n k − 1 ) + ( n k )] a k b n+1−k + b n+1 = n∑ +1 k=0 ( n + 1 k ) a k b n+1−k . We have an equivalent statement of the Principle of Mathematical Induction that is often very useful. Principle 2.5 Second Principle of Mathematical Induction. Let S(n) be a statement about integers for n ∈ N and suppose S(n0) is true for some integer n0. If S(n0), S(n0 + 1), . . . , S(k) imply that S(k + 1) for k ≥ n0, then the statement S(n) is true for all integers n ≥ n0. A nonempty subset S of Z is well-ordered if S contains a least element. Notice that the set Z is not well-ordered since it does not contain a smallest element. However, the natural numbers are well-ordered. Principle 2.6 Principle of Well-Ordering. Every nonempty subset of the natural numbers is well-ordered. The Principle of Well-Ordering is equivalent to the Principle of Mathematical Induction. Lemma 2.7. The Principle of Mathematical Induction implies that 1 is the least positive natural number. Proof. Let S = {n ∈ N : n ≥ 1}. Then 1 ∈ S. Assume that n ∈ S. Since 0 < 1, it must be the case that n = n + 0 < n + 1. Therefore, 1 ≤ n < n + 1. Consequently, if n ∈ S, then n + 1 must also be in S, and by the Principle of Mathematical Induction, and S = N. Theorem 2.8. The Principle of Mathematical Induction implies the Principle of WellOrdering. That is, every nonempty subset of N contains a least element. Proof. We must show that if S is a nonempty subset of the natural numbers, then S contains a least element. If S contains 1, then the theorem is true by Lemma 2.7. Assume that if S contains an integer k such that 1 ≤ k ≤ n, then S contains a least element. We will show that if a set S contains an integer less than or equal to n + 1, then S has a least element. If S does not contain an integer less than n + 1, then n + 1 is the smallest integer in S. Otherwise, since S is nonempty, S must contain an integer less than or equal to n. In this case, by induction, S contains a least element. Induction can also be very useful in formulating definitions. For instance, there are two ways to define n!, the factorial of a positive integer n. • The explicit definition: n! = 1 · 2 · 3 · · ·(n − 1) · n. • The inductive or recursive definition: 1! = 1 and n! = n(n − 1)! for n > 1. Every good mathematician or computer scientist knows that looking at problems recursively, as opposed to explicitly, often results in better understanding of complex issues