Radmila Bulajich Manfrino José Antonio Gómez Ortega Rogelio Valdez Delgado Topics in Algebra and Analysis Preparing for the Mathematical Olympiad Radmila Bulajich Manfrino José Antonio Gómez Ortega Rogelio Valdez Delgado Topics in Algebra and Analysis Preparing for the Mathematical Olympiad Radmila Bulajich Manfrino José Antonio Gómez Ortega Facultad de Ciencias Facultad de Ciencias Universidad Autónoma del Estado de Morelos Universidad Nacional Autónoma de México Cuernavaca, Morelos, México Distrito Federal, México Rogelio Valdez Delgado Facultad de Ciencias Universidad Autónoma del Estado de Morelos Cuernavaca, Morelos, México ISBN 978-3-319-11945-8 ISBN 978-3-319-11946-5 (eBook) DOI 10.1007/978-3-319-11946-5 Library of Congress Control Number: 2015930195 Mathematics Subject Classification (2010): 00A07, 11B25, 11B65, 11C08, 39B22, 40A05, 97Fxx S pringer Cham Heidelberg New York Dordrecht London © Springer International Publishing Switzerland 2015 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. Printed on acid-free paper Springer International Publishing AG Switzerland is part of Springer Science+Business Media (www.springer.com) Introduction Topics in algebra and analysis have become fundamental for the mathematical olympiad. Today, the problems in these topics that appear in the contests are frequent, and the problems from other areas that use algebra and analysis in their solutions are also frequent. In this book, we want to point out the principal algebraandanalysistoolsthatastudentmustassimilateandlearntousegradually in training for mathematical contests and olympiads. Some of the topics that we studyinthebookarealsopartofthemathematicalsyllabusinhighschoolcourses, butthereareothertopicsthatarepresentedatthecollegelevel.Thatis,thebook can be used as a reference text for undergraduates in the first year of college who will be facing algebra and analysis problems and will be interested in learning techniques to solve them. The book is dividedintenchapters.The firstfour correspondto topicsfrom high school and they are basic for the students that are training for the math- ematical olympiad contest, at a local and national level. The next four chapters areusually studied in the first yearof college, but they have become fundamental tools, for the students competing in an international level. The last two chapters contain the problems and solutions of the theory studied in the book. Thefirstchaptercoversthebasicalgebra,asarethenumericalsystems,abso- lute value, notable products, andfactorization,amongothers.We expectthatthe reader gain some skills for the manipulation of equations and algebraic formulae to carry them in equivalent forms, which are easier to understand and work with them. In Chapter 2 the study of the finite sums of numbers is presented, for in- stance,thesumofthesquaresofthefirstnnaturalnumbers.Thetelescopicsums, arithmetic and geometricprogressionsareanalyzed, as well as some ofits proper- ties. Chapter 3 talks about the mathematical technique to prove mathematical statements that involve natural numbers, knownas the principle of mathematical induction.Itsuseisexemplifiedwithseveralproblems.Manyequivalentstatements of the principle of mathematical induction are presented. To complete the first part of the book, in Chapter 4 the quadratic and cu- bic polynomials are studied, with emphasis in the study of the discriminant of a quadratic polynomial and Vieta’s formulas for these two classes of polynomials. v vi Introduction The secondpartof the text begins with Chapter 5, where the complex num- bers are studied, as well as its properties and some applications are given. All these with examples related to mathematical olympiad problems. In addition, a proof of the fundamental theorem of algebra is included. In Chapter 6, the principal propertiesof functions arestudied. Also, there is an introduction to the functional equations theory, its properties and a series of recommendations are given to solve the problems where appear functional equa- tions. Chapter 7 talks about the notion of sequence and series. Special sequences arestudiedasbounded, periodic,monotone,recursive,amongothers.Inaddition, the concept of convergence for sequences and series is introduced. In Chapter 8, the study of polynomials from the first part of the book is generalized. The theory of polynomials of arbitrary degree is presented, as well as several techniques to analyze properties of the polynomials. At the end of the chapter, the polynomials of several variables are studied. Most of the sections of these firsteightchaptershaveatthe enda listofexercisesfor the reader,selected and suitable to practice the topics in the correspondingsections. The difficulty of the exercisesvaryfrombeing adirectapplicationofa resultseeninthe sectionto being a contest problem that with the technique studied is possible to solve. Chapter9isacollectionofproblems,eachoneofthemclosetooneormoreof thetopicsseeninthebook.Theseproblemshaveadegreeofdifficultygreaterthan the exercises.Mostofthe problems haveappearedinsome mathematical contests around the world or olympiads. In the solution of each problem is implicit the knowledge and skills that are need to manipulate algebraic expressions. Finally, Chapter 10 contains the solutions to all exercises and problems pre- sentedinthebook.Thereadercannoticethatattheendofsomesectionsthereis a(cid:2) symbol, this means thatthe level ofthe sectionis harderthanotherssections. In a first lecture, the reader can skip these sections; however, it is recommended that the reader have them in mind for the techniques used in them. WethankLeonardoIgnacioMart´ınezSandovalandRafaelMart´ınezEnr´ıquez forhisalways-helpfulcommentsandsuggestions,whichcontributetotheimprove- ment of the material presented in this book. Contents Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 1 Preliminaries 1.1 Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Absolute value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Integer part and fractional part of a number . . . . . . . . . . . . 12 1.4 Notable products . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 Matrices and determinants . . . . . . . . . . . . . . . . . . . . . . 17 1.6 Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.7 Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2 Progressionsand Finite Sums 2.1 Arithmetic progressions . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2 Geometric progressions . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3 Other sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.4 Telescopic sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3 Induction Principle 3.1 The principle of mathematical induction . . . . . . . . . . . . . . . 43 3.2 Binomial coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.3 Infinite descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4 Erroneous induction proofs . . . . . . . . . . . . . . . . . . . . . . 60 4 Quadratic and Cubic Polynomials 4.1 Definition and properties . . . . . . . . . . . . . . . . . . . . . . . 63 4.1.1 Vieta’s formulas . . . . . . . . . . . . . . . . . . . . . . . . 65 4.2 Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5 Complex Numbers 5.1 Complex numbers and their properties . . . . . . . . . . . . . . . . 75 5.2 Quadratic polynomials with complex coefficients . . . . . . . . . . 79 5.3 The fundamental theorem of algebra . . . . . . . . . . . . . . . . . 81 5.4 Roots of unity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.5 Proof of the fundamental theorem of algebra (cid:2) . . . . . . . . . . . 85 vii viii Contents 6 Functions and Functional Equations 6.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.2 Properties of functions . . . . . . . . . . . . . . . . . . . . . . . . . 94 6.2.1 Injective, surjective and bijective functions . . . . . . . . . 94 6.2.2 Even and odd functions . . . . . . . . . . . . . . . . . . . . 96 6.2.3 Periodic functions . . . . . . . . . . . . . . . . . . . . . . . 97 6.2.4 Increasing and decreasing functions. . . . . . . . . . . . . . 98 6.2.5 Bounded functions . . . . . . . . . . . . . . . . . . . . . . . 99 6.2.6 Continuity . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.3 Functional equations of Cauchy type . . . . . . . . . . . . . . . . . 102 6.3.1 The Cauchy equation f(x+y)=f(x)+f(y) . . . . . . . . 102 6.3.2 The other Cauchy functional equations (cid:2) . . . . . . . . . . 105 6.4 Recommendations to solve functional equations . . . . . . . . . . . 108 6.5 Difference equations. Iterations . . . . . . . . . . . . . . . . . . . . 111 7 Sequences and Series 7.1 Definition of sequence . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.2 Properties of sequences . . . . . . . . . . . . . . . . . . . . . . . . 118 7.2.1 Bounded sequences . . . . . . . . . . . . . . . . . . . . . . . 118 7.2.2 Periodic sequences . . . . . . . . . . . . . . . . . . . . . . . 119 7.2.3 Recursive or recurrent sequences . . . . . . . . . . . . . . . 120 7.2.4 Monotone sequences . . . . . . . . . . . . . . . . . . . . . . 124 7.2.5 Totally complete sequences . . . . . . . . . . . . . . . . . . 125 7.2.6 Convergentsequences . . . . . . . . . . . . . . . . . . . . . 126 7.2.7 Subsequences . . . . . . . . . . . . . . . . . . . . . . . . . . 127 7.3 Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.3.1 Power series . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 7.3.2 Abel’s summation formula . . . . . . . . . . . . . . . . . . . 133 7.4 Convergence of sequences and series (cid:2) . . . . . . . . . . . . . . . . 135 8 Polynomials 8.1 Polynomials in one variable . . . . . . . . . . . . . . . . . . . . . . 139 8.2 The division algorithm. . . . . . . . . . . . . . . . . . . . . . . . . 140 8.3 Roots of a polynomial . . . . . . . . . . . . . . . . . . . . . . . . . 145 8.3.1 Vieta’s formulas . . . . . . . . . . . . . . . . . . . . . . . . 145 8.3.2 Polynomials with integer coefficients . . . . . . . . . . . . . 145 8.3.3 Irreducible polynomials . . . . . . . . . . . . . . . . . . . . 146 8.4 The derivative and multiple roots (cid:2) . . . . . . . . . . . . . . . . . 150 8.5 The interpolation formula . . . . . . . . . . . . . . . . . . . . . . . 151 8.6 Other tools to find roots. . . . . . . . . . . . . . . . . . . . . . . . 153 8.6.1 Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 Contents ix 8.6.2 Conjugate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 8.6.3 Descartes’ rule of signs (cid:2). . . . . . . . . . . . . . . . . . . . 155 8.7 Polynomials that commute . . . . . . . . . . . . . . . . . . . . . . 157 8.8 Polynomials of several variables. . . . . . . . . . . . . . . . . . . . 161 9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 10 Solutions to Exercises and Problems 10.1 Solutions to exercises of Chapter 1 . . . . . . . . . . . . . . . . . . 179 10.2 Solutions to exercises of Chapter 2 . . . . . . . . . . . . . . . . . . 190 10.3 Solutions to exercises of Chapter 3 . . . . . . . . . . . . . . . . . . 199 10.4 Solutions to exercises of Chapter 4 . . . . . . . . . . . . . . . . . . 214 10.5 Solutions to exercises of Chapter 5 . . . . . . . . . . . . . . . . . . 220 10.6 Solutions to exercises of Chapter 6 . . . . . . . . . . . . . . . . . . 229 10.7 Solutions to exercises of Chapter 7 . . . . . . . . . . . . . . . . . . 239 10.8 Solutions to exercises of Chapter 8 . . . . . . . . . . . . . . . . . . 248 10.9 Solutions to problems of Chapter 9 . . . . . . . . . . . . . . . . . . 261 Notation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309