المحاضرة الاولى للدكتورة نبيلة

لكل طلبة العلوم قسم كيمياء
محاضرة الاولى فى التاضل والجبر

Chapter 1

Mathematical Induction





1- 1 The well -Ordering Property

In this section, we discuss several important tools that are useful for proving theorems. We begin by stating an important axiom, the well –ordering property.


The well -Ordering Property. Every nonempty set of positive integers has a least element.



The principle of mathematical induction is a valuable tool for proving results about the integers. We now state this principle, and show how to prove it using the well –ordering property. Afterwards, we give an example to demonstrate the principle of mathematical induction. In our study of number theory, we will use both the well –ordering property and the principle of mathematical induction many times.




The Principle of Mathematical Induction.A set of positive integers that contains the integer 1 and the integer n+1 whenever it contains n must be the set of all positive integers.



Proof. Let S be a set of positive integers containing the integer 1and the integer n+1 whenever it contains n.Assume that S is not the set of all positive integers . Therefore, there are some positive integers not contained in S By the well –ordering property, since the set of positive integers not contained in S is nonempty ,there is a least positive integer n which is not in S . Now since n >1 the integer n-1 is a positive integer smaller than n , and hence must be in S . B u t since S contains n-1, it must also contain ( n-1 ) +1 =n ,which is a contradiction, since n supposedly the smallest positive integer not in S This show that S must be the set of all positive integers.







To prove theorems using the principle of mathematical induction, we must show two things . We must show that the statement we are trying to prove is true for 1, the smallest positive integer. In addition, we must show that it is true for the positive integer n + 1 if it is true for the positive integer n. By the principle of mathematical induction, one concludes that the set S of all positive integers for which the statement is true must be the set of all positive integers. To illustrate this procedure, we will use the principle of mathematical induction to establish a formula for the sum of the terms of a geometric progression.




Definition. Given real numbers a and r, the real numbers



a , a r , ar2 ,ar3, ……




Are said to form a geometric progression. Also, a is called the initial term and r is called the common ratio.




Example. The numbers 5, -15, 45, -135, … form a geometric progression with initial term 5 and common ratio -3.




In our discussion of sums, we will find summation notation useful. The following notation represents the sum of the real numbers a1, a2,…., an


∑ak = a1 + a2 +…..+ an.



We note that the letter k, the index of summation, is a "dummy variable" and can be replaced by any letter, so that




Example. We see that



j =1 +2 + 3 + 4 + +5 = 15





2= 2 + 2 + 2 + 2 +2 = 10 ,

and


2j = 2 + 22 + 23 + 24 + 25 =62





We also note that in summation notation, the index of summation may range between any two integers, as long as the lower limit does not exceed the upper limit. If m and n are integers such that m ≤ n, then



ak= am + a m+1 +…..+ an .



For instance, we have



K 2= 32 +42 +52= 50



and



3k= 30+31 +32= 13



and



k3 = ( -2 )3 +( -1 )3 +03 + 13 =- 8



We now turn our attention to sums of terms of geometric progression. The sum of the terms a, ar, ar2,… , arn is



arj = a + ar +ar2 +…….+ arn ,




Where the summation begins with j =0 . We have the following theorem.




Theorem 1.1. if a and r are real numbers and r 1, then



a rj = a + a r +ar2 +…….+ a rn = (a r n+1 –a) ∕ ( r -1 )




Proof. To prove that the formula for the sum of terms of a geometric progression is valid, we must first show that it holds for n = 1. Then, we must show that if the formula is valid for the positive integer n, it must also be true for the positive integer n + 1.




To start things off, let n = 1. Then, the left side of (1.1) is a +a r, while on the right side of (1.1) we have



( ar2 –a ) ∕ (r-1)=a (r2 – 1 ) ∕ ( r – 1 ) = a ( r + 1 ) = a + a r





So the formula is valid when n = 1 .




Now we assume that (1.1) holds for the positive integer n. That is, we assume that



(1.2) a + a r +ar2 +…….+ a rn = (a r n+1 –a) ∕ ( r -1 )


We must show that the formula also holds for the positive integer n + 1. What we must show is that





(1.3 ) a + a r +ar2 +…….+ a rn+1 = (a r ( n+1)+1–a) ∕ ( r -1 )= (a r n+2-a) ∕ r-1





To show that (1.3) is valid, we add to both sides of (1.2) , to obtain




( a + a r +ar2 +…….+ a rn) + a r n+1 = (a r n+1 –a) ∕ ( r -1 ) +a r n+1 (1.4)





The left side of (1.4) is identical to that of (1.3) . To show that the right sides are equal, we note that




(a r n+1 –a) ∕ ( r -1 ) +a r n+1 = (a r n+1 –a) ∕ ( r -1 ) + a r n+1(r -1) ∕ (r -1 )



= ( a r n+1 –a +a r n+2 – a r n+1 ) ∕ ( r -1 )



= ( a r n +2 – a ) ∕ ( r -1 )






Since we have shown that (1.2) implies (1.3), we can conclude that (1.1) holds for all positive integers n.




Example. Let n be a positive integer. To find the sum



2k = 1 +2 +22 +……+2n




We use theorem 1.1 with a = 1 and r = 2, to obtain




1 +2 +22 +……+2n = ( 2 n+1 – 1 ) ∕ (2 -1 )= 2 n+1 -1





Hence, the sum of consecutive nonnegative powers of 2 is one less than the next largest power of 2.




A slight variant of the principle of mathematical induction is also sometimes useful in proofs.




The Second Principal of Mathematical Induction. A set of positive integers which contains the integer 1, and which has the property that if it contains all the positive integers 1, 2, …, k , then it also contains the integer k + 1, must be the set of all positive integers.




Definition. We say the function f is defined recursively if the value of f at 1 is specified and if a rule is provided for determining f (n+1) from f (n) .




If a function is defined recursively, one can use the principle of mathematical induction to show it is defined uniquely at each positive integer.




We now give an example of a function defined recursively. We define the factorial function f (n) = n! . First, we specify that




f (1) = 1 ,




and then we give the rule for fining f (n+1) from f (n), namely




f (n+1) =( n +1) f (n) .




These two statements uniquely define n!.




To find the value of f (6) = 6! From the recursive definition of f (n) = n!, use the second property successively, as follows





We now use the first statement of the definition to replace f(1) by its stated value 1, to conclude that


6! =6.5.4.3.2.1




In general, by successively using the recursive definition, we see that n! is the product of the first n positive integers, i,e.




n! = 1.2.3.4……n.




For convenience, and future use, we specify that 0! = 1.




We take this opportunity to define a annotation for products, analogous to summation notation. The product of the real numbers a1, a2, …,an is denoted by



= a1a2a3…..an



The letter j above is a "dummy variable", and can be replaced arbitrarily.




Example. To illustrate the notation for products we have




= 1.2.3.4.5 = 120





= 2.2.2.2.2 = 32







j = 2.22.23.24.25= 215











We note that with this notation,
n! =




Factorials are used to define binomial coefficients.


Definition. Let m and k be nonnegative integers


With k ≤ m. The binomial coefficient is defined by

=

In computing , we see that there is a good deal of cancellation, because
==


Example. To evaluate the binomial coefficient , we note that

=35 =



We now prove some simple properties of binomial coefficients.





Proposition 1.2 Let n and k be nonnegative integers with k n . Then



= ((i
= ( (ii





Proof. To see that (i) is true, note that




=1=




and




==1



To verify (ii) , we see that




An important property of binomial coefficients is the following identitt.



Theorem 1.2 Let n and k be positive integers with n ≥ k . Then




+=






Proof. We perform the addition



+=+






By using the common denominator k! (n-k+1)!. This gives



+=+


=


= =










Using Theorem 1.2, we can easily construct Pascal's triangle ,which displays the binomial coefficients. In this triangle, the binomial coefficient is the ( k+1)th number in the (n+1)th row. The first nine rows of Pascal's triangle are displayed in Figure 1.1.










We see that the exterior numbers in the triangle are all 1. To find an interior number, we simply add the two numbers in the positions above, and to either side, of the position being filled. From Theorem 1.2, this yields the correct integer.



Binomial coefficients occur in the expansions of powers of sums. Exactly how they occur is described by the binomial theorem.




The Binomial Theorem. Let x and y be variables and n a appositive integer.


Then


( x+y ) n = xn +x n-1 y +x n-2 y2 +x n-3 y3 +…..




+ x 2y n-2 +xy n-1 + yn



or using summation notation,


(x +y )n = x n-j yj






We prove the binomial theorem by mathematical induction. In the proof we make use of summation notation.




Proof. We use mathematical induction. When n = 1, according to the binomial theorem, the formula becomes



( x+y ) 1= x1y0 +x 0y1




But because = , this states that ( x + y )1= x +y , which is obviously true.



We now assume the theorem is valid for the positive integer n, that is we assume that




(x +y )n = x n-j yj




We must now verify that the corresponding formula holds with n replaced by n + 1, assuming the result holds for n . Hence, we have



( x +y ) n+1= ( x + y )n ( x +y)



=(x n-j yj ) ( x + y )




We see that by removing terms from the sums and consequently shifting indices, that


x n-j +1 yj = x n+1 + x n-j+1 yj






and



x n-j +1 y j+1 = x n-j y j+1 +y n+1


=x n-j+1 y j +y n+1



Hence, we find that


( x + y )n+1= x n+1 ++ ) x n-j+1 y j +y n+1





By Theorem 1.2, we have



+ =




So we conclude that



( x + y )n+1 = x n+1 + x n-j+1 y j +y n+1


= x n+1-j yj



This establishes the theorem.



We now illustrate one use of the binomial theorem. If we let x = y = 1, we see from the binomial theorem that


2n =( 1 +1 )n = 1 n-j 1j =




This formula shows that if we add all elements of the (n+1)th row of Pascal's triangle, we get 2n. For instance, for the fifth row, we find that



+++ += 1+4 +6 +4 +1 =16 =24