Discrete Mathematics With Cryptographic Applications E-Book

Mercury Learning and Information

• Herausgeber: Packt Publishing
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 620

Veröffentlichungsjahr: 2024

Beschreibung

This book offers a comprehensive guide to discrete mathematics and its applications to cryptography. It is designed for students and professionals in fields such as discrete mathematics and finite mathematics, with all necessary prerequisites clearly explained and illustrated. The text introduces key concepts in number theory, coding theory, and information theory, which are essential for understanding cryptography.
Understanding discrete mathematics is crucial for anyone working in cryptography and related fields. The book begins with a survey of elementary functions and moves on to propositional algebra, set theory, and algebraic structures like groups, rings, and fields. It covers binary relations, combinatorics, and elements of number theory, which are fundamental to cryptographic methods.
Readers will explore topics such as Boolean functions, hashing functions, cryptographic maps, combinatorial circuits, and graph theory. The book also delves into advanced areas like finite automata, game theory, and Turing machines. Through numerous examples, problems, and solutions, readers will gain a solid foundation in discrete mathematics and its cryptographic applications.

Leseprobe

DISCRETE MATHEMATICSWITH CRYPTOGRAPHICAPPLICATIONS

LICENSE, DISCLAIMER OF LIABILITY, AND LIMITED WARRANTY

By purchasing or using this book and disc (the “Work”), you agree that this license grants permission to use the contents contained herein, including the disc, but does not give you the right of ownership to any of the textual content in the book / disc or ownership to any of the information or products contained in it. This license does not permit uploading of theWork onto the Internet or on a network (of any kind) without the written consent of the Publisher. Duplication or dissemination of any text, code, simulations, images, etc. contained herein is limited to and subject to licensing terms for the respective products, and permission must be obtained from the Publisher or the owner of the content, etc., in order to reproduce or network any portion of the textual material (in any media) that is contained in the Work.

MERCURY LEARNINGAND INFORMATION (“MLI” or “the Publisher”) and anyone involved in the creation, writing, or production of the companion disc, accompanying algorithms, code, or computer programs (“the software”), and any accompanying Web site or software of the Work, cannot and do not warrant the performance or results that might be obtained by using the contents of the Work. The author, developers, and the Publisher have used their best efforts to insure the accuracy and functionality of the textual material and/or programs contained in this package; we, however, make no warranty of any kind, express or implied, regarding the performance of these contents or programs. The Work is sold “as is” without warranty (except for defective materials used in manufacturing the book or due to faulty workmanship).

The author, developers, and the publisher of any accompanying content, and anyone involved in the composition, production, and manufacturing of this work will not be liable for damages of any kind arising out of the use of (or the inability to use) the algorithms, source code, computer programs, or textual material contained in this publication. This includes, but is not limited to, loss of revenue or profit, or other incidental, physical, or consequential damages arising out of the use of this Work.

The sole remedy in the event of a claim of any kind is expressly limited to replacement of the book and/or disc, and only at the discretion of the Publisher. The use of “implied warranty” and certain “exclusions” vary from state to state, and might not apply to the purchaser of this product.

DISCRETE MATHEMATICSWITH CRYPTOGRAPHICAPPLICATIONS

A Self-Teaching Introduction

Alexander I. Kheyfits, PhD

MERCURY LEARNING AND INFORMATIONDulles, VirginiaBoston, MassachusettsNew Delhi

Copyright ©2021 by MERCURY LEARNINGAND INFORMATION LLC. All rights reserved.

This publication, portions of it, or any accompanying software may not be reproduced in any way, stored in a retrieval system of any type, or transmitted by any means, media, electronic display or mechanical display, including, but not limited to, photocopy, recording, Internet postings, or scanning, without prior permission in writing from the publisher.

Publisher: David Pallai

MERCURY LEARNING AND INFORMATION

22841 Quicksilver Drive

Dulles, VA 20166

[email protected]

www.merclearning.com

800-232-0223

Alexander I. Kheyfits. Discrete Mathematics with Cryptographic Applications.

ISBN: 978-1-68392-763-1

Library of Congress Control Number: 2021942465

The publisher recognizes and respects all marks used by companies, manufacturers, and developers as a means to distinguish their products. All brand names and product names mentioned in this book are trademarks or service marks of their respective companies. Any omission or misuse (of any kind) of service marks or trademarks, etc. is not an attempt to infringe on the property of others.

212223 321 This book is printed on acid-free paper in the United States of America.

Our titles are available for adoption, license, or bulk purchase by institutions, corporations, etc.

For additional information, please contact the Customer Service Dept. at 800-232-0223(toll free).

All of our titles are available in digital format at academiccourseware.com and other digital vendors. The sole obligation of MERCURY LEARNING AND INFORMATION to the purchaser is to replace the disc, based on defective materials or faulty workmanship, but not based on the operation or functionality of the product.

CONTENTS

Preface

Chapter 1:A Brief Survey of Elementary Functions

1.1 Mathematical Induction

1.2 Factorials and The Stirling Formula

1.3 Recursive Definitions

1.4 Elementary Functions

1.4.1Quadratic Functions

1.4.2Exponential and Logarithmic Functions

1.4.3Trigonometric Functions

1.5 Stirling Asymptotic Formula

1.6 Exercises

Chapter 2:Propositional Algebra

2.1 Propositions

2.2 Connectives: Truth Tables

2.2.1Order of Operations

2.3 Exercises

Chapter 3:Naïve and Formal (Axiomatic) Set Theory

3.1 Classes and Sets. Axioms and Theorems

3.1.1Classical Set Theory

3.1.2Operations on Sets: Set Diagrams

3.2 Exercises

Chapter 4:Groups, Rings, and Fields

4.1 Groups, Rings, and Fields

4.2 Matrices and Determinants

4.3 Finite Groups

4.3.1Cyclic Groups

4.4 The Discrete Logarithm Problem

4.5 Exercises

Chapter 5:Predicates and Quantifiers—Algebraic Theory

5.1 Predicates

5.2 Quantifiers

5.2.1Commutativity of Quantifiers and Boolean Operations

5.3 Exercises

Chapter 6:Binary Relations and Relational Databases

6.1 Ordered Totalities and Cartesian Products

6.2 Relations

6.2.1Special Classes of Relations

6.3 Orderings and Posets

6.3.1Equivalence Relations

6.3.2Equivalence Classes

6.4 Relation Databases

6.5 Exercises

Chapter 7:Combinatorics

7.1 Finite and Infinite Sets: Basic Rules

7.1.1The Sum and Product Rules

7.1.2Unions, Cartesian Products, Booleans

7.1.3Arrangements and Combinations

7.1.4Stirling Numbers

7.1.5Combinations With Repetitions

7.1.6Permutations With Identified Elements

7.2 Exercises

Chapter 8:Elements of Number Theory

8.1 Divisibility and FTA

8.1.1Divisibility, the FTA, and the Euclidean Algorithm

8.1.2Euclidean Algorithm

8.1.3Algorithms

8.1.4Modular or Clock Arithmetic: Linear Congruences

8.1.5Totient Function

8.1.6Pseudorandom Numbers

8.1.7Cryptography Application: Sharing Secrets

8.1.8Affine Ciphers

8.2 Exercises

Chapter 9:Boolean Functions

9.1 Boolean Degree: DNF and CNF

9.2 Boolean Polynomials

9.3 Boolean Derivatives

9.4 Exercises

Chapter 10:Hashing Functions and Cryptographic Maps

10.1 Rosetta Stone

10.2 Hashing Functions

10.3 Substitution Ciphers

10.4 Exercises

Chapter 11:Generating Polynomials and Inversion Formulas

11.1 Partitions of the Integers

11.1.1Compositions

11.1.2Inversion Formulas

11.2 Exercises

Chapter 12:Systems of Representatives

12.1 SDRs

12.1.1Systems of Triples

12.2 Exercises

Chapter 13:Boolean Algebras

13.1 Operations and Axioms

13.2 Boolean Rings

13.3 Exercises

Chapter 14:Combinatorial Circuits

14.1 Graphs and Schemes

14.2 Logical Problems

14.2.1Binary Adders

14.3 Exercises

Chapter 15:Complete Systems of Boolean Functions and Bases

15.1 Complete Systems and Bases

15.2 Post Theorem

15.2.1Bases

15.3 Exercises

Chapter 16:Introductory Graph Theory, Euler’s Formula, and Unbreakable Ciphers

16.1 Graphs and Diagrams

16.2 Connectivity in Graphs

16.2.1Unbreakable Ciphers

16.2.2Bipartite Graphs

16.3 Exercises

Chapter 17:Trees and Digraphs

17.1 Spanning Trees

17.2 Binary Search

17.3 Exercises

Chapter 18:Computations and Algorithms

18.1 Exercise

Chapter 19:Finite Automata

19.1 Simple Model

19.2 Tables and Graphs of Automata

19.3 Classification: Equivalent States and Equivalent Automata

19.3.1Minimization of Automata

19.3.2Automaton Operators

19.3.3Regular Grammars

19.4 Exercises

Chapter 20:Introduction to Game Theory

20.1 Classification of Strategies

20.2 Exercises

Chapter 21:Information Theory and Coding

21.1 Measure of Information

21.2 Channels

21.3 Exercises

Chapter 22:Probability Theory with a Finite Sample Space and the Birthday Problem

22.1 Random Experiments

22.2 Probability Distributions

22.3 Expectation: Bayes Formula

22.4 Bernoulli Trials and The Birthday Problem

22.5 Exercises

Chapter 23:Turing Machines, P and NP Classes, and Other Models of Computation

23.1 Turing Machines

23.2 Exercise

Chapter 24:Answers and Solutions to Selected Exercises

Bibliography

Index

PREFACE

Mathematics and sciences, including political science have always involved many problems requiring large computations and sometimes, thousands of people. A century ago, the word “computer” meant a human being performing those computations. The top-level scientists, like Gottfried Leibniz, Lady Ada Lovelace, Alan Turing, and others were thinking how to automatize those computations. The breakthrough happened in the thirties-forties of the previous century, when Alan Turing proved the theorem about the universal program and John von Neumann developed the scheme of the universal computer machine, which all of us have used since then – see Chapter 23. The technology was ready, and the very first electronic computer “ENIAC” executed its initial programs in 1945. Since then, “computer” has meant an electronic device.

ENIAC declassifying in 1946 led to the explosive growth of the number of electronic computers, and correspondingly, to the growth of the number of people working with computers. Those people were mostly mathematicians, but very soon mathematics departments could not provide enough cadres, and the colleges and universities had to start teaching different courses to the new “computer scientists,” whose first mathematical course was often called Discrete Mathematics or Finite Mathematics. Within a few years, discrete mathematics has become an independent mathematical discipline. Paul Halmos predicted [25, p. 19] that in the foreseeable future “. . . discrete mathematics will be an increasingly useful tool in the attempt to understand the world, and ... analysis will therefore play a proportionally smaller role.”

Textbooks for the new discipline quickly followed, from concise lecture notes to Kenneth Rosen’s monumental treatise [43], whose 8th edition (2019) amounts to more than 1000 pages. But every new generation meets their own challenges and requires new textbooks, see, e.g., [42], whatever good are the previous ones. A quarter century back, it was important to emphasize the algorithmic nature of discrete mathematics [37]. Now the 20-30-year-old discussions – see, e.g., [36], are mostly forgotten. The Internet security issues are more important than ever before, and this textbook was written with strengthened attention to these topics. A short version of these lectures was initially taught in 1971 and has evolved during the following half-century, being greatly influenced by the times and people – by my students, friends, and colleagues on both sides of the Atlantic.

To describe the contents of this book in more detail, let us notice that our thoughts are initially appeared as electrical-chemical potentials in the “grey matter” in our brains. To communicate our thoughts to other people, those potentials must be converted into electrical potentials governing oscillations of our vocal cords, and the latter create the fluctuations of the air pressure, carrying our speech. When these acoustical oscillations reach our ears, all the transformations are done in the opposite direction. Thus, the information that we create and obtain, is to be encoded and decoded in many different ways. These transformations are studied by coding theory, which is an important part of the discrete mathematics. However, to perform those conversions, we must represent the signals in a suitable form, i.e., as Boolean functions, and the book starts with an exposition of elementary logic and Boolean calculus. What is more, we often do not want other people to know the outcomes of our dealings with information, hence giving rise to the cybersecurity issues.

Boolean functions are maps, and chapters devoted to the functions, sets, and relations follow. We also consider in more detail predicates and quantifiers, which are necessary in many applications. When it is appropriate, we include expositions of some applications of these mathematical questions to computer-related issues, such as, e.g., relational databases or hashing functions. Several classical discrete mathematics topics, namely combinatorics, graph theory, complete systems of functional elements, etc., and some applications like finite automata, necessary for the potential users of the book, are included. These developments are based upon some algebraic structures, like groups, rings, fields, and Boolean Algebras. That allowed us to consider certain cryptography issues, in particular, the Discrete Logarithm Problem.

The book also contains chapters about number theory and game theory. No discussion of cryptography is possible these days without number-theoretical issues, like clock arithmetic and CRT. That background allows us to consider affine ciphers and some procedures of sharing secrets. The book also includes a chapter about game theory, the topic, whose inclusion in a discrete mathematics text is long overdue.

It is not the first text, which uses cryptology to enhance the teaching of mathematics – see, e.g., an interesting note [7]. Due to the volume restrictions, specifically crypto-questions are not covered here as much as they deserve. If the discussion of crypto–issues would deviate too far from the discrete mathematics, we are to stop there. To proceed farther, we would recommend the excellent books [2, 13, 14, 40]. The table of contents shows in more detail, what is in the book.

Many sections contain more material than can be reasonably taught at a two-hour class. That allows a lecturer some freedom of choice, and also provides the material for the student’s individual work.

No mathematical exposition is possible without mathematical induction, which is unknown to most high school students. The author’s experience shows though, that the method of mathematical induction, being properly explained, is well accessible to college freshmen. The very first chapter of the book is devoted to mathematical induction and to a very brief discussion of elementary functions, necessary in the textbook. That sets out the prerequisite level for the whole book. It is supposed that most college freshmen, independently upon their specialization, will benefit from this textbook. However, those lower prerequisites brought an unexpected problem. Certain language, which the college sophomores usually know quite well, can be unfamiliar to some potential readers. Thus, the book explains in more detail than usual, certain parlance, e.g., “necessary and sufficient conditions” or the like. This is especially necessary and useful now due to proliferation of on-line courses, where the student often cannot ask immediately certain “simple” questions. The reader, who is fluent with that material, can skip this material with no harm.

Of course, this is a mathematics textbook, and its reading requires concentration. To develop this culture, the reader is supposed to solve at least some of the included problems, and to analyze the suggested solutions. This is especially important in the times of online education. We remark in passing that it is not unusual, when the students find new solutions of old problems or suggest new problems. The author always welcomes any such input. The book contains more than 600 problems of various levels of difficulty. All of the exercises for the students’ individual work are placed in the end of chapters. Many other problems can be found in the cited literature, e.g., in [19].

We thank many people for help. Parts of the book were discussed at the DIMACS Center at Rutgers University during the Reconnect conferences. The Reconnect-2019 workshop at the Champlain College in Burlington, VT, was invaluable in finalizing this project. The present author, as anyone else, has its favorite books; I cannot list all of them, but I want to mention delightful books by M. Schroeder [45] and by L. Lovasz, J. Pelikan and K. Vesztergombi [35]. We want to personally thank the following people: Midge Cozzens, Fred Roberts, David Pallai and the staff of Mercury Learning and Information, who made this project possible.

Alexander I. Kheyfits, PhD.September 2021

CHAPTER 1

A BRIEF SURVEYOF ELEMENTARY FUNCTIONS

1.1MATHEMATICAL INDUCTION

1.2FACTORIALS AND THE STIRLING FORMULA

In the previous computation, we had to multiply consecutive natural numbers. This procedure occurs so often that it deserved its own name and symbol.

Definition 2The product of n consecutive natural numbers from 1 through n inclusive is called the n factorial and is denoted as n!.

For example, ; if , then . If we want to preserve this property for , it is natural to define.

The symbol n! does not look very impressive for small n but let us study it more carefully. Already , and we observe that the factorials grow very fast. James Stirling (1692–1770), the younger contemporary of Newton (1643–1727), showed the asymptotic formula to be proved in Lemma 2,

(1.4)

The letter e is a standard symbol for the famous real number , which will be discussed below. The symbol and name here mean that the ratio of the left- and right-hand sides of the formula tend to 1 as . This formula, without the precise value of the constant, was known to Abraham de Moivre (1667-1754) even before Stirling.

Problem 12Approximate 10! by formula (1.4) and compare with the exact value given above.

Solution. By Stirling’s formula, , with the relative error less than 1%. If n is increasing, the relative error is even smaller.

Problem 13Compute . For what natural numbers is this expressiondefined?

Solution. For , hence .

Problem 14How many digits are in the number 100!?

Solution. Of course, we are not going to compute the huge number 100! precisely and count the digits. It is much easier to use a calculator and get . Hence,

so that the decimal number 100! has 158 decimal digits.

1.3RECURSIVE DEFINITIONS

The definition of the factorial function can be written as

Such a definition is called recursive because at the second step, it returns to the same definition, but with a smaller value of the parameter. Indeed, we compute the factorial through the factorial. Recursive definitions are often used in computer science and mathematics. As another example, let us consider a recursive definition of integer powers , that can be defined for any natural n as and .

The definitions of well-known arithmetic and geometric progressions (sequences), namely,

where a0 is the initial term and d, called the difference, are given numbers, and

are also recursive definitions.

Problem 15List the first five terms of the arithmetic progression with the first term and the difference . Prove that the terms of any arithmetic progression satisfy

Solution. To prove the first equation, it is enough to employ the definition and iterate it, .

Problem 16Given , where A and B are some constants, and where ; find an explicit expression for .

Solution. Look for the solution as , where the constants and are the roots of the quadratic equation The conditions for a0 and a1 give and .

This solution can be easily generalized for any homogeneous difference equations with constant coefficients and with a certain non-homogeneity. The method is similar to the case of linear differential equations with constant coefficients, see, for example, [28, Sect. 4.4].

Problem 17Find explicitly the Fibonacci numbers, which satisfy the difference relation and the initial conditions .

Solution. The relation and the initial conditions lead to the quadratic equation with the irrational roots and the formula for the Fibonacci numbers

This formula, containing radicals, gives for every natural n integer values. For example, , etc.

To prove that a recursive definition returns the quantity it is supposed to, one must use the mathematical induction. For instance, in the example above, the zeroth part of the definition, , must be used as a basis of induction. Then, the inductive step is justified by the second part of the recursive definition, . Any rigorous exposition, which includes a recursive definition or a recursive procedure, must be accompanied by an inductive proof of its validity.

Problem 18Find the recursive formula for the general term of a sequence, if it starts with , and every subsequent term is 3 more than twice the previous term.

Solution., for .

Problem 19Does the sequence , satisfy the recurrence relation ?

Solution. No, since in general .

Functions of two or more variables can also be defined recursively. A common example is the Ackermann function , defined as follows:

Problem 20Compute the values

Problem 21Give a recursive definition of the set of pairs of positive integers whose sum is odd.

1.4ELEMENTARY FUNCTIONS

The next few pages contain a very brief survey of the basic elementary functions5 – Power, Exponential, Logarithmic, and Trigonometric Functions. If the reader is familiar with that material, she can safely skip it and go to the next lecture. However, we know from the experience that many students, especially at the community colleges, know (if any) this stuff insufficiently, that is why it is included here.

Consider a quadratic equation . It has two real roots, . A similar equation has no real solution, but if we consider it over the larger set of complex numbers, the equation has two roots. The reason for that is that the map for real x is not a surjection, that is, given a y, we not always can return to x. This is a very common problem, and we address it now.

First, we consider bijective maps and let be bijective. This means that for every element there exists one and only one element such that . Now we construct the map as follows. For every we set , where xy has been just defined. Since the element yx was defined uniquely, we uniquely defined the map . By our construction, the map g has the following properties.

The domain of g is Y and the co-domain is X. For each ,

(1.5)

therefore,

(1.6)

The map g is called the inverse map of the map f (because it is unique) and is denoted . If the inverse map exists, f is called invertible. Let us repeat that the domain of f coincides with the co-domain of g and vice versa; the co-domain of f coincides with the domain of g. It is clear also that in this case, the inverse map, g is also bijective and invertible, and we can write . We restate the conclusion of this argument in the following theorem, where the uniqueness obviously follows from the construction of the inverse map.

Theorem 1Any bijective map has the unique inverse map, which is also bijective and satisfies the equations (1.5)–(1.6).

Theorem 1 says, in particular, that a non-bijective function cannot have the inverse function. However, there may exist one-sided (from left or from right) invertible functions. We proceed as one often does in mathematics: namely, we use the properties, which have been proven in a particular case (in this case, equations (1.5) – (1.6) valid for bijective maps) as the definitions in general situation.

Definition 3Consider two arbitrary sets X and Y, and an arbitrary map ; f is called left-invertible if there exists a map , such that ; the map is called a left-inverse map of f.

A map f is called right-invertible if there exists a map , which is called a right-inverse map for f, such that . The name (left or right) is given according to the position with respect to the given map f. Map f itself is a right-inverse for and is a left-inverse for .

Theorem 2Criterion of the unilateral invertibility. A map is left-invertible iff it is injective. A left-inverse map exists iff . It does not have to be unique. It is unique if either fis bijective or the domain X contains only one element x0.

A map is right-invertible iff it is surjective. It exists iff . A right-inverse map may not be unique. It is unique if f is bijective or the co-domain Y is a one-element set.

A map is invertible (from both sides) iff it is bijective. In this case, f is both left- and right-invertible or , the left-inverse map and the right-inverse map are unique, coincide with one another and both are equal to the inverse map .

Proof. Let f be left-invertible and be its range. The map is bijective and . Therefore, f is injective. Vice versa, if f is injective, the function is a bijection; thus, it has an inverse map. Extending its definition onto in either way, for example, defining for every , where x0 is an arbitrary element of X, we derive a left-inverse map to f. It is obvious that any such extension generates a left-inverse of f.

Problem 22Finish the proof of Theorem 2

1.4.1Quadratic Functions

Let , and . We know already that this f is neither injective nor surjective, thus, it has no unilateral inverse, on ether side. To proceed, we should reduce either its co-domain or domain, or both. First we reduce the co-domain by removing the negative numbers and get a surjective map , where . This g has at least one, maybe many right-inverse maps. One of them is , , where . We can also define , where and, as before, . We can also scramble these two branches, say, use one for and use another for .

Problem 23Verify that for all right-inverses grof g,

Next, we consider function given by the same formula . It is an injection, and therefore it has left-inverse maps. One of them is , but we also must define for , for example, as .

Problem 24Define another left-inverse function for and verify that for all left-inverses , .

The map for is a bijection, so that it is invertible. Its inverse is a bijection too, and we have for all . This function is the main ingredient of all unilateral inverses above. It is called the principal square root of a positive number .

1.4.2Exponential and Logarithmic Functions

If three real numbers satisfy the equation , then b is called the base, x is the exponent, and y the power. For example, , while . If the base b is fixed, becomes a function of x, it is called the exponential function (to the) base b. Experimenting with convenient values, for example, with , we conclude that x can be any real number, but y is always positive, even if x is negative, say, . This statement is deep; its proof requires some mathematical analysis. Actually, for different bases b there are different exponential functions , however, their properties are very similar, that is why you can often read about “the exponential function.”

The next statement summarizes the basic properties of the exponential function. We consider them only when the base or ; when , we have the constant function , which is in a sense trivial. What is more, if , the values of are the same for different values of x, thus, the function is not injective. The case necessitates consideration of the complex numbers, which is beyond this book.

Theorem 3Let the base. The domain of the exponential function consists of all real numbers, and its range consists of all the positive real numbers. If , then it is a continuous positive monotonically increasing function, if , it is monotonically decreasing. Therefore, as a function from to itself, it is injective. Moreover, as a function from to strictly positive real numbers, it is a bijection and, therefore, it has the inverse function. The following properties follow from the properties of the exponents,

Problem 25Graph the 16 exponential functions and

Consider the exponential function with the positive base . Therefore, this function is monotone, and so that, it is injective if the domain consists of all real numbers, or it is even bijective, if we consider only the positive real numbers as its domain. Either way, this exponential function has the (left) inverse, called the logarithmic function and denoted as

or just .

The definition and Theorem 3 imply the following features of the logarithmic function.

Theorem 4The domain of logarithmic function consists of positive real numbers, and the range consists of all real numbers. If , then, it is a continuous monotonically increasing function, for it is monotonically decreasing. It is (left) inverse of the exponential function, namely, for all real x, while for . Next,

Lemma 1Change of Base formula. For any positive it is hold

Problem 26Prove the statements of this section.

Next, we show a few simple applications of these functions to compound interest problems.

Problem 27On January 1, you have the balance of P dollars in your bank account; this amount is called the principal P. Since you keep your money in this account and allow the bank to use this money, once or several times a year, the bank pays you some small amount, called the interest p, and deposits this interest into your account, thus adding to the current amount. If the interest equals p% of the current balance, this method is called the compound interest. In other words, the bank pays “interest on interest.” Here p is the annual interest, and if the bank pays the interest k times per year, each payment is equal of the annual interest. Let , , and , that is, the interest is paid semi-annually. What is the balance on the account after the five full years will expire?

Problem 28A bank pays compound interest k times per year. How much time is it necessary to double the balance in your account?

Problem 29Let x be a real number and k be an integer, such that . Prove that .

Problem 30If is an odd number, then .

1.4.3Trigonometric Functions

Consider the function , where . This is a periodical function with the smallest positive period and with the range , therefore, it is not injective nor surjective and has neither left, nor right inverse. However, if we restrict it to the set , the restricted function is monotone and takes on in this interval every its possible value from −1 to 1 exactly once. Thus, we consider the restricted function . This is a bijective function, so that it has the inverse map, which is denoted as , or (in particular, on calculators) as . This function is the main part of all the inversions of the sin function.

Since the function is bijective, when and , it has both left- and right-inverse maps, and we have

(1.7)

(1.8)

By tradition, we denoted the argument in the second equation as x, even though visually it runs over the axis.

Consider a surjective function . Again, there are infinitely many different right-inverse functions, one of them is . We have – but only for . Outside of this set the expression is undefined (as a real number).

Finally, we consider an injective function . It is injective but not surjective, thus, it is left-invertible, and we define one of its left-inverses as . Equation becomes now (1.7). It is worth noticing that the left-hand side of (1.7), namely, is defined now for all real x, and not only for , however, for formula (1.7), in general, fails. For instance, if , then .

Problem 31Compute for all real x.

Solving various equations is one of the most common mathematical tasks, and the results of this section clarify what can be expected while solving the equations. In general, consider an equation . If f is surjective, then the equation has a solution for every , and this solution is generally not unique. If f is injective, then the equation has the unique solution for every ; however, for the equation has no solution. If f is bijective, then the equation has the unique solution for every . Obviously, these theorems are pure existence theorems – they contain no algorithms for constructing a solution in particular cases.

Problem 32Are the following functions bijective? Injective? Surjective? Neither? If possible, construct left- or right- or inverse functions.

1.

2.

3.

4.

5..

Problem 33Prove that the set of polynomials with integer coefficients is countable, that is, can be put in a one-to-one correspondence with the set of natural numbers.

1.5STIRLING ASYMPTOTIC FORMULA

We consider now quantities that depend upon integer parameters and can take on natural values, that is, the functions from the set of the integers to the set of natural numbers. We study these functions or maps (mappings), often called sequences, in detail later on. The reader can now skip the end of this lecture, which includes a small foray into analysis, and return to it later, as necessary.

If there are two variables, say two sequences and , depending upon a parameter6, then it is written as . The notation7, means that is bounded for all . The notation8, means that as .

It is also convenient to define two integer-valued functions from to , where and are the sets of the real numbers and the integers, respectively.

Definition 4The floor function , called also the integer part of x, or (from French “Entier”), denotes the largest integer which is smallerthan or equal to x, that is, is always an integer and; for example, and . Similarly, the smallest integer, which is no less thanx, is called the ceiling function and is denoted as ; for example, and , where is the Napierian number.

Problem 34Compute , ,, .

Solution., , , .

Problem 35 (1) Graph the functions and .

(2) Prove that. Study the equality cases.

(3) Prove that .

(4) Prove that for every real x.

(5) Prove that if x is not integer, and if x is aninteger.

(6) Prove that the number of multiples of a natural number k among the integers is given by the floor function . Let us notice that the integer part if . What is this quantity among the integers , where is any integer?

Problem 36How many integers are between 1 and 6 inclusive?

Solution. One immediately sees that the answer is 6.

Problem 37How many integers are between −8 and 6 inclusive?

Solution. Now the answer consists of three addends: 6 integers for the positive numbers, 8 for the negative numbers, and 1 for the 0, thus the final answer is , which can be written as .

Problem 38How many multiples of a natural number p are between m and n, inclusive, where are the integers?

Solution. The fraction n / p is not always integer, hence the answer includes the floor and/or ceiling function. With this observation, you can immediately check that the answer is

Problem 39How many integers between 4 and 44 are prime?

Problem 40Check whether the following equations are true or false.

1) ; 2) ; 3) .

Lemma 2

Proof. Hereafter, the symbol log always means natural logarithms, that is, logarithms are to the base e, the Napier number . We have

Integrating by parts and considering that , we finish the proof.

Problem 41Stirling formula can be made more precise and include the decaying terms of orders . Prove that

and

Problem 42Compute the precise values of 5! and 10!, and compare with their Stirling approximations in Lemma 2.

Solution. and . By Lemma 2, and .

Definition 5The “double factorial” is the product of consecutive natural numbers from 1 to n of the same parity as n. For example,

and .

Problem 43Define the double factorial as recursive function.

Problem 44Modify the Stirling asymptotic formula for the double factorials.

1.6EXERCISES

1 The zero is included in the set of natural numbers, as is the common agreement in discrete mathematics and computer science. We do not give an axiomatic description of the set of natural numbers. The most common, Peano system of axioms, includes The Axiom of Mathematical Induction, which is discussed in detail below.

2 The abbreviation “iff” stands for “if and only if” and means “necessary and sufficient condition(s)”; we discuss it in detail in the next Lecture.

3 These two methods have occurred not only in mathematics and sciences, but also, for example, in historiography: cf. the discussion of Gesetzwissenschaft versus Geschichtswissenschaft in [23, p. 251].

4 Such a mathematical joke with a wrong proof is called a sophism or a fallacy.

5 Here “elementary functions” only means that some features of these functions are studied at high school.

6 The symbol is not a number, the writing means that the parameter n becomes and then remains bigger than any positive number.

7 Called “Big O.”

8 Called “Small o.”