Introduction to Number Theory
Introduction to Number Theory MATH 3240
Popular in Course
Popular in Mathematics (M)
verified elite notetaker
This 7 page Class Notes was uploaded by Mary Veum on Thursday September 17, 2015. The Class Notes belongs to MATH 3240 at University of Connecticut taught by Keith Conrad in Fall. Since its upload, it has received 38 views. For similar materials see /class/205818/math-3240-university-of-connecticut in Mathematics (M) at University of Connecticut.
Reviews for Introduction to Number Theory
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/17/15
EXAMPLES OF PROOFS BY INDUCTION KEITH CONRAD 1 INTRODUCTION In this handout we illustrate proofs by induction from several areas of mathematics linear algebra polynomial algebra and calculus Becoming comfortable with induction proofs is almost entirely a matter of having lots of experience The rst kind of induction argument one usually sees is for summation identities such as 221 k n n2 That style of induction proof is not how induction is generally used in proofs in mathematics Two questions naturally arise from this 1 Why are students sometimes taught only induction with summation identities if it s not a typical way induction is often used in proofs 2 Why are induction proofs of summation identities bad models for induction else where in mathematics I will leave the answer to the rst question to your imagination The answer to the second question is that in most uses of induction you can t argue by trying to add something to both sides like in the proof of a summation identity because what is being proved isn t an identity so there aren t both sides in the rst place Even identities that are proved by induction can t always proceed by manipulating the previously settled cases into the next case like in a summation identity The right way to approach an inductive argument is to ask yourself How can I use the earlier cases to prove the next case rather than How can I algebraically manipulate the earlier cases into the next case In particular the inductive step does not usually begin by immediately writing down the earlier case and doing something to it What normally happens is that the earlier proved cases appear somewhere within the inductive step but it could be in the middle or the end This will be clearer after you read the proofs below Another important idea for creating proofs by induction is to try out small explicit ex amples Can you get the case n 2 from the case n 1 somehow Can you get the case n 3 from the case n 2 somehow If you have no idea how to manufacture the inductive step in general working out small cases of the inductive step successfully can usually help suggest an outline for a proof of the inductive step in general 2 LINEAR ALGEBRA We begin with an inductive proof of a matrix identity where the do something to both sides idea from summation identity proofs works Theorem 21 Let A be a square matrix and B be an invertible square matrix of the same size Then BABAYL BAnB 1 for all integers n 2 0 Proof We argue by induction on n the exponent The result is obvious for n 0 when both sides equal the identity matrix When n 1 the equation BAB l1 BAB 1 is obvious 1 2 KEITH CONRAD Let s see what happens in the case when n 2 this is not strictly necessary but is the kind of work a student should do to discover a proof of the inductive step try small cases We have 131434 BAB 1BAB 1 BAB 1BAB 1 BAIAB l BAAB l BAZB l The way B and B 1 cancelled in the middle is the key idea Let s prove the case n 3 from the case n 2 in the same way now that we know BAB UZ BAZB l 13141343 BAB 12BAB 1 13142134131411 BA2B 1BAB 1 BAZIAB l 131421411 314334 Hopefully from these two small cases you already see how the inductive step for any n will work That general step is what we turn to next To prove the inductive step assume the result is established for exponent n BAB 1 BAnB l Then BAB 1 1 BAB 1 BAB 1 BAnB 1BAB 1 BA B 1BAB 1 BAnlAB l BA AB 1 BAn1B71 We used the inductive hypothesis in the second equation Thus the result is true for exponent n 1 if it is true for exponent n Since the base case n 1 is true and assuming the n th case is true we showed the n 1 th case is true we conclude that the theorem is true for all integers n 2 O D In our next theorem from linear algebra whose proof uses induction we do not argue in the inductive step from one case directly to the next case Instead the inductive step has a proof of the next case by reducing ourselves to the setting of the previous case This reduction idea is extremely important a lot of proofs by induction follow it Theorem 22 Let A be a square matrix Eigenuectors for A having distinct eigenvalues are linearly independent if V1 VT are eigenvectors for A with AV xlVi for distinct scalars 1 T then V1 VT are linearly independent As a reminder an eigenvector for A is a nonzero vector V such that AV V for some scalar EXAMPLES OF PROOFS BY INDUCTION 3 Proof We induct on r the number of eigenvectors Since a single nonzero vector is a linearly independent set by itself the theorem is true and not interesting when r 1 Now suppose r gt 1 and the result has been veri ed for r 7 1 That is assume it is known that any 7 7 1 eigenvectors ofA with distinct eigenvalues are linearly independent That is our inductive hypothesis If we are now given r eigenvectors V1 V7 of A with distinct eigenvalues 1 AT suppose 61V162V2CTVT 0 for some scalars Ci We want to prove each c is 0 That is what linear independence means We need to use A somehow In equation 21 apply A to both sides 61AV1 62AV2 CTAV7 0 SO Clx1V1 32Ang CTATVT 0 Look closely at 21 and 22 They both say some linear combination of the Vi s is equal to 0 but they use different looking systems of coef cients By a suitable scaling we will be able to make the coef cients of V1 in 21 and 22 match and then subtracting one equation from the other will cancel that term and leave us with r 7 1 vectors to which the inductive hypothesis applies The coef cients of V1 in 21 and 22 are 01 and 011 So if multiply through 21 by 1 we get 23 611V1 621V2 CT1V7 0 where the coef cient of V1 is now 011 just like in 22 Now subtract 23 from 22 and the rst term is eliminated Cg2A1V2CTT1VT 0 The vectors V2 VT are r71 eigenvectors ofA Their eigenvalues A2 T are distinct by hypothesis so the inductive hypothesis tells us that V2 VT are linearly independent Therefore 24 tells us that cii 7 1 0 for i 23 r Since the eigenvalues are distinct i 7 1 7 0 fori 2 r so oi 0 for i 23 r Feeding this into 21 gives us 01V1 0 so 01 0 as well since V1 7 0 Thus every oi is O D 3 POLYNOMIALS Proofs about polynomials often proceed using induction on the degree That is a general theorem about polynomials is proved rst for constant polynomials degree 0 then for linear polynomials degree 1 then for quadratic polynomials degree 2 and so on Theorem 31 Let be a nonconstant polynomial with real coe icients and degree d Then has at most at real Toots We can t replace at most at real roots77 with exactly at real roots77 since there are nonconstant polynomials like 2 1 which have no real roots Zero roots is at most two roots so the theorem is true for 2 1 4 KEITH CONRAD Proof We will argue by induction on the degree d of Note 1 2 1 Our theorem begins with degree 17 not degree 0 A polynomial of degree 1 with real coefficients is of the form fz am 1 b7 where a and b are real and a 7 O This has exactly one root7 namely 719017 and thus at most one real root That settles the theorem for d 1 Notice we proved the theorem for all polynomials of degree one at the same time Now assume the theorem is known for all polynomials of some degree d with real coeff cients This is the inductive hypothesis We want to prove the theorem for all polynomials of degree d 1 with real coefficients That is the inductive step We consider two cases Case 1 The polynomial has no real roots for instance7 2 1 in degree 2 Since there are 0 roots7 and 0 g d 17 the polynomial has at most 1 1 real roots Case 2 The polynomial has a real root What we re going to do now as a method of reducing to an earlier case is use the root to pull out a linear factor of our polynomial of degree d 1 The complementary factor will have degree d7 to which the inductive hypothesis will be applicable Write our polynomial of degree d 1 as 31 cd1md1 cdmd 1 1 61m 1 07 where 0739 E R and cd1 7 0 Let r be a real root7 so 32 0 cd1rd1 3de 1 Cl 1 co Subtracting 32 from 317 the terms 00 cancel and we get 33 cd1md1 7 rd1 cdmd 7 rd 1 61m 7 r The polynomial formula mi 7 Ti x 7 7 x7quot1 rxjiz 1 717171 1 rjizm 77171 show 7 7 r7 is divisible by z 7 r Write the second factor as c27Tz7 so 34 90739 i 7 95 TQjr7 and substituting 34 into 33 gives 1 11 2 0190 NQNM j1 11 90 i 7 Z Cijr j1 90 NQW say Each Qjrm has real coefficients and all 07 are real7 so Qm has real coefficients Computing the degree of both sides7 deg fz 1 1 deg c2z7 so deg Qm d We can therefore apply the inductive hypothesis to Qz it has at most 1 real roots Any root of fz is either r or a root of Qz if fs 0 then s 7 rQs 07 so 3 r or Qs 0 Since there are at most 1 real roots of c2z7 tossing r into the list gives us at most 1 1 real roots of As fz was an arbitrary polynomial of degree d 1 with real coefficients7 we have shown all polynomials of degree d 1 with real coefficients have at most 1 1 real roots This completes the proof of the inductive step D EXAMPLES OF PROOFS BY INDUCTION 5 4 CALCULUS We will prove three theorems from calculus using induction In the rst two theorems we will take for granted the product rule The proof of the product rule has nothing to do with induction but everything to do with the limit de nition of the derivative This will not be discussed7 since this is a handout on induction7 not limits Our rst inductive proof in calculus is the power rule Theorem 41 For n 2 1 z nzn l Proof We will use the product rule and induction The case n 1 says m 17 which can be proved directly from the de nition of the derivative as the limit of a Newton quotient This is left to the reader to check To understand the inductive step7 rst let s check two special cases the passage from n 1 to n 2 and the passage from n 2 to n 3 Using the product rule on m2 m2 mzy mx mx m m 2x 3 2 Using the product rule on x 7 written as x m mayx2mx2xmm2m21m2xz22m23z2 Note where the used the formula for 2 in this proof of the formula for mgy With these special cases in mind7 the inductive step in general should make sense as suming z nmn l we have by the product rule mnT1mnm x m m fly xn1 mnmn71 x 7n n 1zn D Remark 42 Although the power rule is an identity7 it can t be proved using the simple minded do something to both sides77 method of induction in proofs of summation identities Think about it how are you going to massage both sides of the equation z nzn l to get zn y on the left side The exponent appears inside the derivative7 so you can t apply some simple operation to z to make it mn y You will not get anywhere by starting the inductive step with What happened instead in the proof is that the product rule lets us write zn y in terms of mny7 and at that point we can bring in the inductive hypothesis about This is why the right attitude in induction proofs is to ask How can I use the previous case77 instead of How can I start with the previous case77 Our next inductive proof in calculus is an example of inducting on the number of terms in a formula Theorem 43 For di erentz39able functions f1z 7 was fnltzgtgt 1 was f1zfnx he quot39 Mz Proof We induct on n the number of functions When n 17 the formula is clear since both sides equal fmf1 To handle the case n 27 the product rule tells us f190f2 flf2x f1f 6 KEITH CONRAD Divide both sides by f1zf2 and we get the formula we are looking for f1f2 flf2 Mad90 He we f1f2 f1f290 f1f290 M90 M90 Let s see how to prove the theorem for n 3 by a reduction to the case n 2 we can View a product of three terms f1zf2zf3z as a product of two terms f1zf2zf3m By the proved case of any two differentiable functions f1f2fs f1f2fsm V V f1f2fs f1f2fs f1f2 We f1f290 M90 Again by the case of two differentiable functions f1f2 Wm M f1f290 M90 M90 M90 M90 We can apply the same idea for the general proof of the inductive step Let s assume the theorem is proved for any n differentiable functions When f1z fn1z are any n 1 differentiable functions write 41 f1mfnfn1 f1fn fn1 where the rst product on the right contains 71 functions Treating f1z fn as a single function we can view the right side of 41 as a product of two functions Then we can use the proved case of the theorem for two functions to simplify the expression with n 1 functions before using the inductive hypothesis f1fn11 f1m39fnmfn11 f1mfn1 f1fn 39 fn1 1 MW f1 95 39 39 39 M1 fn1 Case of two functions Mm Mm fade 777 by1ndhyp mas M90 max 1 l and this is what we needed to show for n 1 functions D Remark 44 The inductive step ofthis proof does not start with the identity for 71 functions and do something to both sides in order to get the identity for n 1 functions Instead the inductive step starts off by writing f1 fn1z f1m fn1z in terms of f1m fnm f1z and then the inductive hypothesis can be applied Our nal inductive proof in calculus is a beautiful formula for n in terms of integrals Theorem 45 Euler For n 2 0 fax mne m dz nl Proof We argue by induction on n For n 0 00 b b e m dm lim e m dm lim 757m 0 Hoe 0 Hoe lim 7547 7 750 0 7 71 1 0 baoo EXAMPLES OF PROOFS BY INDUCTION 7 Assuming the theorem is proved for some value of n we prove it for n 1 by expressing fax zn1e m dz in terms of fax zne m dz using integration by parts 00 b zn e m dz lim zn1eim dz 0 17400 0 b lim udv u zn17dv 5 dz Hoe 0 l7 l7 lim uv 7 Udu du n 1z v 75 Hoe 0 0 n1 b b lim 7 n 1zne m dz baoo em 0 0 g bn1 co 7 lt7 O n 1 zne m dz 0 Hoe eb Exponentials grow much faster than polynomials7 so UNAeh a 0 as b a 00 Therefore 00 00 00 zn eim dz 0 0 71 1 znrfm dz 71 1 znrfm dz 0 0 0 By the inductive hypothesis7 this last expression is n 1 71 n 1l That completes the proof D Remark 46 The inductive step did notstart with the equation f0 zne m dz n and do something to both sides to turn it into the equation fooo zn1e m dz n 1 Instead we started with the integral fooo zn1e m dz and rewrote it in terms of fooo zne m dz7 at which point we can bring in the inductive hypothesis about f0 zne m dz The key thing to look for when you read a proof by induction is how the inductive step uses earlier cases to get the next case Review each proof again with this in mind Frequently the inductive step does not start with the inductive hypothesis that is7 an earlier case right away
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'