Math 5020: Fundamentals of Mathmatics for Teachers

Math 5020

Fundamentals of Mathematics for Teachers

Description: Number theory and combinatorics are branches of mathematics in which challenging problems can be explored that require a background with which most students are familiar. This course deals with topics in these two fundamental mathematical fields, including modular arithmetic, linear and quadratic diophantine equations, continued fractions, permutations and combinations, distributions and partitions, recurrence relations and generating functions. It is one of two required courses for the Mathematics for Teachers program. An emphasis in this course is placed on writing and explaining mathematics clearly.

Prerequisite: Permission of the instructor is required for students who are not in the Graduate Programme in Mathematics and Statistics.

Professor: Mike Zabrocki
Office: TEL 2028
Hours: Thursday 4-5:30pm
phone: 416-736-2100 x33980
e-mail: zabrocki at mathstat dot and the usual ending

Class meets Thursday 6-9pm in Ross S537

Text : Number Theory by George Andrews

We have a FORUM for math 5020. This is a web site that will allow you to post questions/comments/communications about the course. I will try to keep track of postings and answer them on a regular basis.

Grades for the course will be based on the following criteria:

Class presentation	10%
Un-exams (4 x)	5%+10%+10%+15%
Forum exercises	Fall 15%+Winter 15%
Class participation (incl attendance)	Fall 10%+Winter 10%

Handouts

Initials	Induction problems	Combinatorial problems	Widget and doodle	OLEIS	GF examples	Combgfs	Last unexam
EA	1	16	1	6	9	6c	2
MB	21	14	3	7	8	2d	4
LC	3	12	5	8	16	3d	6
SD	4	10	7	9	7	4c	8
PK	5	8	9	10	15	16b	10
AL	6	6	11	11	6	3c	12
YL	7	4	13	12	13	11d	14
GM	8	2	15	13	14	6d	15
KM	9	1	2	14	3	7c	13
PM	10	3	4	15	5	5d	11
LR	12	7	6	16	10	7d	9
SR	13	9	8	2	11	9d	7
MS	14	11	10	3	17	9e	5
RS	15	13	12	4	4	8d	3
KTG	16	15	14	5	12	4d	1

Announcements

(April 22, 2010) I'm going to try to plug away at postings as I get some time. While I was caught up this weekend I seemed to get slammed for the 'deadline' of April 18 for the exercises and I expect I will get more for the due date of April 25 for the unexam.
Remark (1): a former 5020 student sent me the following reference on generating functions. It could be useful.
Remark (2): I found out that the sum side of problems (7) (8) and (9) of the unexam do not seem to have a nice expression. The problem is that it does not seem possible to write down the generating function for partitions with at most height k and at most 3 parts of any one type. To fix this, you may on these problems choose to sum over the size of the first part of the partition. As far as I can tell this makes the problem much easier. You might also consider this possibility for the ones with "at most k parts of size k" (problems (13) (14) (15)), but with these there is also a way of writing down the expression with the Durfee square.

(March 26, 2010) I doled out the last problem for the unexam. Start thinking about it now so we can talk about it in class next week.

(March 26, 2010) I took a picture of the generating functions on the board before I left. Comments:
(27) while I believe the partitions can be broken in to even parts and odd parts, and the even parts have a generating function \prod_{i\geq1}1/(1-q^{4i}), I have a problem with the generating function for the odd parts. Consider the parts of size 1 (if there are any), they occur (), (1), (111), (11111), ... so the generating function is 1+q+q^3+q^5+... = 1 + q/(1-q^2). Then you have to do the same thing for parts of size 3, 5, etc. See the matching worksheet problem (13)->(m).
(28) the Durfee square is size 3x3 and so it contains 9 cells and then you want to make the blocks to the right of the Durfee square consist of an odd number of columns of size 3, an even number of columns of size 2, and an even number of columns of size 1.
(29) I suggest that you break it up into a staircase of height 1,2 or 3 and a partition of length <= the height of the staircase.
(30) seems right if that is a q^{2i-1} in the denominator (my picture is too fuzzy).
(5) and (6) seem right.
(21) break it into a staircase of length exactly equal to 5 and a partition of length <=5.
(22) this expression is equal to 1/q^infinity which is not right.

(March 11, 2010) I have posted what I think are the last of the handouts that I am going to give this year (except perhaps an alternate proof of section 14-2). We are going to have to work hard to finish all these before the last class so it is important that you practice hard and ask questions about the assignments when we see each other.

(March 2, 2010) It was pointed out to me (even in class on Thursday, but I forgot to correct it) that I had left off the words "tail hits" in the question of the unexam. I just corrected it so that the question is stated correctly. I did not purposely leave off the "tail hits" as a means of getting the 100 points.

(March 1, 2010) I know that we didn't get to spend much class time on the two worksheets that I posted today, but you should know how to take coefficients of rational generating functions by hand. We will come back to these worksheets if we have time in class, otherwise I expect that you will work on them on weeks that I don't give you lots of extra work (this week concentrate on your unexams). You will need techniques of ' partial fraction decomposition' (reference 2 - Wikipedia, reference 3) that we talked about in class. One of the questions on the 'More Number Theory' worksheet is a question a student told me he had to do on a test in his high school class, another is one that came up in my cryptography class and both use really strongly the addition and multiplication principles.

(Feb 25, 2010) An example of a command in Maple to expand a series of a generating function:
series( (1+q+q^2)/(1-q-q^2), q, 20);
In Sage, the same command is:
q=var('q')
taylor((1+q+q^2)/(1-q-q^2), q, 0, 20)
The commands expand( expr ), factor( expr ), simplify( expr ) are commonly used to manipulate algebraic expressions.

(Feb 12, 2010) Here are the answers that people posted on the boards last night. I see one common error with several of them. Some of them seem to say "a sequence of integers" is equal to "generating function." This is not right. When the problem is to prove "LHS = RHS," instead of saying something like "LHS = A(q)" (which is false), it should say "g.f. for LHS = A(q)." ALL of them should essentially say "g.f. for LHS = g.f. for RHS" therefore "LHS = RHS."

(Jan 29, 2010) Although we aren't going to be using computers in this class for any great extent, I would like you to get used to the idea that some computations can more easily done on the computer and you shouldn't be afraid to try out something like Maple or SAGE when you need it. On the surface these are just big calculators. You have access to Maple if you log onto your mathstat account or through many of the university computers. You can have access to SAGE over the web.
Here are some commands that you might want to know to do modular arithmetic in Maple:
a mod n; - compute a modulo n as a value between 0 and n-1. (e.g. 12 mod 7; is 5)
a^b mod n; - compute a^b modulo n, but this only works for relatively small values of a,b (e.g. 5^10 mod 13; is 12)
ipowermod(a,b,n); - compute a^b modulo n, but this works for really big values of a and b, negative b means powers of the inverse of a. e.g. ipowermod(342342754,293847293,928347294387); is 659093719639
where
ipowermod:=proc(a,b,n) local x; if b<0 then return ipowermod(a,-b,n)^(-1) mod n; elif b=0 then return 1; elif b=1 then return a mod n; elif b mod 2=0 then x:=ipowermod(a,b/2,n); return x^2 mod n; else return a*ipowermod(a,b-1,n) mod n; end; end:
igcdex(a,b,'s','t'); gives the extended gcd where s*a+t*b = gcd(a,b) (e.g. igcdex(5,7,'s','t'); then s=3,t=-2.
Finally, if you type in with(numtheory); in Maple it loads a number theory library and you have access to functions like jacobi(a,n) and legendre(a,p), phi(n) - the Euler phi function.
You can get help on any function by typing ? functionname

That being said, I am a SAGE fan and I find it easier to get help there. If I don't find the function within sage I go to Google and type something like "jacobi symbol sage" and I was able to find functions I didn't know. Type the first few letters of the function and the TAB key and SAGE will complete the word. If you put a question mark after the function name and hit the TAB key an explanation of the function will come up. Also you don't need to have the semi-colon at the end of the line like in Maple. In sage the commands are:
mod(a,b) - compute a modulo n as a value between 0 and n-1. (mod(4,3) returns 1)
power_mod(a,b,n) - compute a^b modulo n (e.g. power_mod(342342754,293847293,928347294387))
Try looking at xgcd for extended gcd, euler_phi for the Euler phi function, kronecker_symbol and legendre_symbol is the Jacobi symbol and Legendre symbol respectively.

(Jan 29, 2010) The general multiplication principle for generating functions is: "If A_i(q) is a generating function for a set of objects, then A_1(q) A_2(q) ... A_r(q) is a generating function for r-tuples of objects where the i-th entry in the tuple is an object corresponding to the generating function A_i(q). The size/type of a tuple is the sum of the sizes/types of the objects in the tuple." There is an addition principle of generating functions too. "If A(q) and B(q) are generating functions for sets of objects then A(q)+B(q) is the generating function for the (disjoint) union of the objects represented by A(q) and the objects represented by B(q)."

(Jan 28, 2010) The next unexam is posted and remember, it is all about making sure that you have explained it all in a short, simple direct solution. The first question might take a few sentences to state clearly, but if your second one is more than 1/2 page, I will suggest that you are not being clear.

(Jan 22, 2010) We stayed late (yet again) last night. Thanks everyone for putting in so much work last night. Keep solving those problems! We want to build up our library so that on the 3rd page of that exercise we can derive all of these Fibbonaci/Lucas identities without using induction. Just a reminder, we won't start early next week. Also, there are a couple of errors on that worksheet having to do with Lucas numbers starting at 2, 1 or 1, 3. I should be following Andrews convention and he said that L_1 = 1 and L_n = F_{n+1} + F_{n-1} on p.7. I think that I followed wikipedia and they probably start L_0 = 2 but then they also start F_0 = 1. Just to not mess things up too much, lets follow the convention that L_1 = 2 and then only the generating functions for M^{(0)}(q), M^{(1)}(q) and M^{(-1)}(q) are wrong on the second page and L(q) = (2-q)/(1-q-q^2) on the first (I think).

(Jan 22, 2010) Sorry that demo didn't go so well last night. I woke up this morning and knew what was wrong with the SAGE part (I still can't figure out what the Maple commands are).
sage: n = 87905578924245789034527890435278904537890452389705897545389701 sage: a = 34578534786345786435786 sage: power_mod(a, divmod(n-1,2)[0], n) 84945071240645380280487097648633869882198852261368495855379089
Now since that is not +/-1 it is not prime.

Next I wrote a little more code:
sage: for i in range(200): n= 87905578924245789034527890435278904537890452389705897545389701+2*i if power_mod(a, divmod(n-1,2)[0], n)==1 or power_mod(a, divmod(n-1,2)[0], n)==n-1: print(i)
and found that n+102 is likely a prime and so is n+306.

(Jan 9, 2010) I downloaded the pictures that I took with my iPhone and I posted the solutions to the coefficients in generating function worksheet. The ones taken of the board aren't too clear but the ones taken of individual pages seemed to turn out ok. If you have questions on any particular one let me know.

(Jan 8, 2010) I fixed the bijection that I talked about last night and I wrote it up with all the details about why it is both surjective and injective.

(Jan 7, 2010) The forum was down the last few days but it is back. Thanks for those that pointed it out. I added a new forum exercise that uses the site : The Online Encyclopedia of Integer Sequences This exercise can potentially be a mini-research project so it might be more challenging than the past ones that we have done.

(Dec 3, 2009) I need about 3 hours to catch up on the forum postings and I don't see having that amount of free time before classes end. What that means is that I am going to make the Forum postings due in the new year.

(Nov 20, 2009) I won't be able give feedback on the forum for a few days because I will be traveling but I will try to plug away at them when I get the chance.

(Nov 20, 2009) And now, the assignment you have all been waiting for. The first unexam. The worksheet that I meant to distribute tonight is here. Here is the next set of problems that I would like you to post on the forum. I know it seems like two more problems, but neither one requires little explanation, just an answer that I can argue with.

(Nov 13, 2009) I won't be here the week that we have class on November 26th. I am going to give (a) another set of problems for forum postings and (b) an unexam on the evening of November 19th and class will not be held on the 26th. I am not too concerned about making up the time because we have (and will) run over on occassion.

(Nov 13, 2009) Found error in the answer for combinatorial problem #8. Corrected.

(Oct 24, 2009) I found two more errors on the induction problems and I corrected them (#14 and #15). Repeat: if you are having problems with yours, check a few cases and ask me if can't seem to do yours. There could be a few more typos in this problem set.

(Sept 26, 2009) Don't be afraid to ask questions about the forum problems if you are stuck. I had a couple of people point out some typo's/mistakes. E.g. #6 and #9 are now corrected.

(Sept 24, 2009) We have Ross S525 reserved for the classroom.

(Sept 20, 2009 w/ update Sept 24) By showing the list of topics and giving people a week to 'think about it' I left open the door for some to start emailing me asking if they could have this or that topic. I already discussed on Thursday with the person who volunteered to go first with Fermat's Little Theorem. I have since had emails requesting card shuffling, intro to elliptic curves, multiplicative functions, chinese remainder theorem, primes and Tchebychev's inequality, and primitive roots. If there is a particular topic that you want, I don't know of a better way of resolving this than by asking you to send an email request with a possible backup choice.

(Sept 18, 2009) Lindsy had a shorter "direct proof" of the identity 1^3 + 2^3 + 3^3 + ... + n^3 = n^2*(n+1)^2/4 that she showed me before class ended last night. She took n^2*(n+1)^2 - (n-1)^2*n^2 = 4 n^3 and then computed the telescoping sum. Everything in the telescoping sum cancels except n^2*(n+1)^2 on one side and on the other she showed that it was 4( 1^3 + 2^3 + 3^3 + ... + n^3 ). Who knew?

(Sept 18, 2009)- For those of you who are looking ahead at what we are doing next week, we will be finishing up Chapter 2 and starting section 3-1. The first presentation will be the week after on Fermat's Little Theorem.

(Sept 18, 2009)- I am going to assign you each a proof by induction to put on the forum later this week. I want to edit the problems that I had on the list that I passed around a bit before I do. If you want some practice, go ahead and try a few of them.

(Sept 18, 2009)- I looked into what you needed for the accounts. I have contacted the math department IT group to reset the forum so it might take a day or two. In the meantime you should go to the computing services web page and go to the tab "Accounts -Manage my services" in the pull down menu. Once you log in you want to activate your AML account. NB: This may not work for a day or two while the accounts are being set up so if you can't activate your AML account, try back later.

(Sept 18, 2009)- From last night. For homework, do a calculation of a gcd using Theorem 2-2. I think I gave as an example: gcd(1471, 341) but also try an example like gcd(1473, 341) where the gcd is not 1.

(Sept 11, 2009)- Please note the registration reminder that was posted to the blog and sent to the mailing list (maybe not everyone is on yet). Make sure you are registered by Septemeber 15 or be square.

(Sept 11, 2009)- For homework I asked you to try the exercise to show 1^3 + 2^3 + 3^3 + ... + n^3 = n^2*(n+1)^2/4 by induction. As a bonus you can show it without using induction by adding terms k*(k+1)*(k+2)*(k+3) - (k-1)*k*(k+1)*(k+2) = 4*k*(k+1)*(k+2) for k between 1 and n in two different ways.

(Sept 8, 2009)- I am the coordinator for the M.A. for Teachers program and have been posting announcements to a blog about the program since some time last year. You are encouraged to keep up with the postings and are welcome to comment (anonymously if you would like). I mix up articles/online material about mathematics and education with announcements about the program so I recommend that you take a look at some past postings. Some important past announcements that are still current information:
Grades for a graduate program at York university
Results of the survey
Past courses in the program
What is this program about
Peter Gibson's remarks about Analysis for Teachers
My remarks about Fundamentals for Teachers

(Sept 7, 2009)- Note that graduate classes for the Mathematics and Statistics program are begin on September 9, Important dates. The first day of class for this course will therefore be Thursday, September 10th, 2009.