Note for MATH 121 with Professor Hart at KU
Note for MATH 121 with Professor Hart at KU
Popular in Course
Popular in Department
This 4 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 84 views.
Reviews for Note for MATH 121 with Professor Hart at KU
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: 02/06/15
Principle of Induction and Summation Forms Jarod Hart Math 121 Introduction This reading will be a short introduction to summation or sigma notation the principle of induction and summation forms These concepts have proved to be of great importance in the world of mathematics Sigma notation is used widely in almost all areas of mathematics and in order to understand some of these mathematical concepts it is important to understand what the notation means The principle of induction is a very important concept and proof technique used widely in math Finally summation forms are often useful and sometimes provide an insightful thought on common problems Sum forms are paramount in computing de nite integrals using Reimman sums Sigma Notation Sigma notation is simply a shorthand notation for summing numbers It is de ned as follows For a sequence of numbers 11 i 12 n anaia2a3an71an 1 n z This is a fairly basic idea but it serves its purpose by making summation formulas concise It is important to note that although a sum is written in sigma notation it is still a sum and you may apply any idea that you would apply to a sum A couple important properties are For 11 and b for i 123 n and any number 0 the following hold i1 i1 i1 The rst two of the above are simply the laws of associativity and commutativity I doesn t matter what order you add up a bunch of numbers so you may split up the terms however you wish as long as all the same terms are present The third is the distributive law or the idea of factoring out The last is adding 1 repeatedly This is basically counting to n Motivation In order to motivate the next section look at a couple of examples of sums Consider the problem of summing the numbers from 1 to n for some positibe integer 11 By a couple of simple calculations we can see some of the following sums Zi12345 15 i1 But what if you want to nd the sum of the number from 1 to 1000 As you can imagine this process becomes tedious quickly This motivates the idea that maybe there is a closed form for these sums By an interesting line of reasoning that I will revisit later one can generate the formula 211 139 quot012 Check it for the above sums But can you gaurantee that this formula works for any integer There is no way that anybody can try all of the integers to check to make sure the formula works This is where the principle of induction comes into play Principle of Induction The principle of induction is used to show that a statement holds for all positive integers Because no statement can be tested for every integer one by one since the integers are in nite there must be a way of getting around this The idea of induction is to show that the statment holds for 1 and then show that if the statment holds for n then it holds for n 1 The statement of the principle of induction is Let Pn for n a positive integer be some statement that can be determined to be true or false If 1 Base step P1 is true 2 Inductive step Pk is true i Pk 1 is true Then Pn is true for all positive integers The principle of induction can be viewed as a type of domino effect The inductive step sets up all of the dominos in a line That is if a statement is true for any individual integer then it is true for the next one like if any domino falls in a line of dominos it knocks over the next one Then the base step is like knocking over that rst domino Knocking over the rst domino forces all the dominos to fall eventually This is the case with induction The base step states that P1 is true Then using the inductive step P1 is true i P2 is true Then P2 is true i P3 is true and so on Then logically for any positive integer 11 one would conclude that P1 is true i P2 is true i P3 is true i i Pn 7 1 is true i Pn is true Then the statement Pn is true for any integer n For an example of a proof by induction consider the derivative of f x x Rather than using the binomial expansion theorem it can be proved that f x m 1 by using induction and the product rule For any positive integer n x nx 1 Proof In order to apply the principle of induction to this problem one must show two things 1 Base step xl 1x0 1 2 Inductive step digck lociquot1 i xk k 1xk First to show that x 1 h dx hgt0 h l l l l Therefore the base step is true Now to prove the inductive step assume that xk kxk l Now using this assumption we want to show that xk k 1xk As I said before I will use the product rule to show this First look at ka as a product of two functions ka xxk Now use the product rule d d d d 7 7 7 xk 7 dx dxx dxx xltdx Then by the base hypothesis x 1 and by the assumption xk kxk l Then ixk1ixxk xixk xk xkxk 1 xk kxk k1xk dx dx dx Therefore fixC lociquot1 i xk1 k 1xk Then the base and inductive step are both satis ed There fore by the principle of induction 1M m 1 Summation Formulas Earlier in the reading it was suggested that for any positive integer n the formula 2141 i quot0127 holds This is in fact true and I will demonstrate this by using the principle of induction later First let s form an idea of how this formula was derived To simplify this problem lets rst look at summing the numbers 1 through 10 It is simple to just add these numbers up to get the answer but if you inspect how we add these numbers together there is some insight into where this formula came from It is natural to solve this problem by adding the number in ascending order but of course you may add them in any order you wish So let s rearange these numbers a little 1234567891011029384756 1111111111511 Notice here that since 11 10 11 1 11 and the abovce sum is in fact 127011 101 1 This is the form that the sum takes for any even integer and a similar form presents when summing to an odd integer This is the motivation for the sum formula 21139 quot012 but it still doesn t verify that it holds for all positive integers In order to show that we will need a proof by induction For any positive integer n 2141 quot012 Proof First to show the base step is easy 2111 1 and 102 1 1 Then the formula holds for n 1 Now to procede to the inductive step assume that L1 139 Then we need to show that the formula holds for k 1 That is using the assumption we must show that i So look at k1 k ZiZik1 i1 i1 By our assumption L1 139 M162 Then k k kk1 k2k 2k1 k23k2 k1k2 39 39 k 1 k 1 I z z 2 2 2 2 2 Then the inductive step is true as well Therefore by induction 21139 quot012 Other sum formulas can be proved in similar ways i112 nn12n1 30 if 7 n2n122n2 2117 1 7 12 39 For extra credit write a proof by induction similar to the ones I have done in this reading for the following 1 211392 nn162n1 2 2141 21gt 1 112 Notice that this sum formula says that if you add up all of the odd numbers between 0 and 211 you get 112
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'