Difference between revisions of "An Introduction to Mathematical Induction: The Sum of the First n Natural Numbers, Squares and Cubes."

From Math Wiki
Jump to navigation Jump to search
 
(4 intermediate revisions by the same user not shown)
Line 11: Line 11:
 
:: <math style="vertical-align: 0px">1+2+\cdots+13. </math>
 
:: <math style="vertical-align: 0px">1+2+\cdots+13. </math>
  
However, there is an even more powerful shorthand known as '''sigma notation'''. When we write  
+
However, there is an even more powerful shorthand for sums known as '''sigma notation'''. When we write  
  
 
:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=1}^{13}\, i,} </math>  
 
:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=1}^{13}\, i,} </math>  
  
 
this means the same thing as the previous two mathematical statements.
 
this means the same thing as the previous two mathematical statements.
Here, the '''index''' below the capital sigma, <math style="vertical-align: -5px">\left(\Sigma\right) </math>, is the letter <math style="vertical-align: 0px">i </math>, and the <math style="vertical-align: 0px">i </math> that follows the <math style="vertical-align: 0px">\Sigma </math> is our '''rule''' to
+
Here, the '''index''' below the capital sigma, <math style="vertical-align: -5px">\left(\Sigma\right) </math>, is the letter <math style="vertical-align: 0px">i </math>, and the <math style="vertical-align: 0px">i </math> that follows the <math style="vertical-align: 0px">\Sigma </math> &thinsp;is our '''rule''' to
apply to each value of <math style="vertical-align: 0px">i </math>. The values <math style="vertical-align: -1px">1 </math> and <math style="vertical-align: -1px">13 </math> tell us how many times to repeat the rule, i.e., to follow the rule for <math style="vertical-align: -4px">i=1, </math>
+
apply to each value of <math style="vertical-align: 0px">i </math> within the limits. The limits <math style="vertical-align: -1px">1 </math> and <math style="vertical-align: -1px">13 </math> tell us how many times to repeat the rule, i.e., to follow the rule for <math style="vertical-align: -4px">i=1, </math>
 
then add the rule for <math style="vertical-align: -4px">i=2, </math> then for <math style="vertical-align: -4px">i=3, </math> and continue in this
 
then add the rule for <math style="vertical-align: -4px">i=2, </math> then for <math style="vertical-align: -4px">i=3, </math> and continue in this
manner until you reach <math style="vertical-align: -1px">13</math>. In other words,  
+
manner until you reach <math style="vertical-align: -1px">i=13.</math> In other words,  
  
 
:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=1}^{13}}\, i\,=\,1+2+3+4+5+6+7+8+9+10+11+12+13. </math>  
 
:: <math style="vertical-align: 0px">{\displaystyle \sum_{i=1}^{13}}\, i\,=\,1+2+3+4+5+6+7+8+9+10+11+12+13. </math>  
Line 47: Line 47:
 
::<math style="vertical-align: 0px"> \text{The Natural Numbers}\,=\,\mathbb{N}\,=\,\{1,2,3,\ldots\}\,=\,\{1,1+1,1+1+1,1+1+1+1,\ldots\}. </math>
 
::<math style="vertical-align: 0px"> \text{The Natural Numbers}\,=\,\mathbb{N}\,=\,\{1,2,3,\ldots\}\,=\,\{1,1+1,1+1+1,1+1+1+1,\ldots\}. </math>
  
This is the basis for weak, or simple induction; we must first prove our conjecture is true for the lowest value (such as <math style="vertical-align: -1px">1</math>), and then
+
This is the basis for weak, or simple induction; we must first prove our conjecture is true for the lowest value (usually, but not necessarily <math style="vertical-align: -1px">1</math>), and then
 
show whenever it's true for an arbitrary <math style="vertical-align: -4px">n, </math> it's true for <math style="vertical-align: -2px">n+1 </math>
 
show whenever it's true for an arbitrary <math style="vertical-align: -4px">n, </math> it's true for <math style="vertical-align: -2px">n+1 </math>
 
as well. This mimics our development of the natural numbers.  
 
as well. This mimics our development of the natural numbers.  
  
It is also equivalent to prove that whenever the conjecture is true for <math style="vertical-align: -4px">n-1, </math> it's true for <math style="vertical-align: 0px">n. </math> Which approach you choose can depend
+
It is also equivalent to prove that whenever the conjecture is true for <math style="vertical-align: -4px">n-1, </math> it's true for <math style="vertical-align: 0px">n. </math> Which approach you choose can depend on which is more convenient, or possibly which is more appealing to the teacher grading the work.  We will use this style for the proofs on this page.
on which is more convenient, or frequently which is more appealing
 
to the teacher grading the work.
 
  
Although we won't show examples here, there are induction proofs that require '''strong induction'''. This occurs when proving it for the <math style="vertical-align: -5px">(n+1)^{\textrm{th}} </math> case requires assuming more than just the <math style="vertical-align: 0px">n^{\mathrm{th}} </math>
+
Although we won't show examples here, there are induction proofs that require '''strong induction'''. This occurs when proving it for the <math style="vertical-align: -5px">(n+1)^{\mathrm{th}} </math> case requires assuming more than just the <math style="vertical-align: 0px">n^{\mathrm{th}} </math>
case. In such situations, strong induction assumes that the conjecture is true for ALL cases from <math style="vertical-align: 0px">n </math> down to our base case.
+
case. In such situations, strong induction assumes that the conjecture is true for <u>'''ALL'''</u> cases from <math style="vertical-align: 0px">n </math> down to our base case.
  
 
== The Sum of the first ''n'' Natural Numbers ==
 
== The Sum of the first ''n'' Natural Numbers ==

Latest revision as of 13:19, 28 February 2017

Sigma Notation

In math, we frequently deal with large sums. For example, we can write

which is a bit tedious. Alternatively, we may use ellipses to write this as

However, there is an even more powerful shorthand for sums known as sigma notation. When we write

this means the same thing as the previous two mathematical statements. Here, the index below the capital sigma, , is the letter , and the that follows the  is our rule to apply to each value of within the limits. The limits and tell us how many times to repeat the rule, i.e., to follow the rule for then add the rule for then for and continue in this manner until you reach In other words,

Of course, we can change the rule and/or the index. For example,

Most importantly, we frequently don't have the luxury of bounds that are actual values. We can also write something like

or

These non-fixed indices allow us to find rules for evaluating some important sums.

Proof by (Weak) Induction

When we count with natural or counting numbers (frequently denoted ), we begin with one, then keep adding one unit at a time to get the next natural number. We then add one to that result to get the next natural number, and continue in this manner. In other words,

This is the basis for weak, or simple induction; we must first prove our conjecture is true for the lowest value (usually, but not necessarily ), and then show whenever it's true for an arbitrary it's true for as well. This mimics our development of the natural numbers.

It is also equivalent to prove that whenever the conjecture is true for it's true for Which approach you choose can depend on which is more convenient, or possibly which is more appealing to the teacher grading the work. We will use this style for the proofs on this page.

Although we won't show examples here, there are induction proofs that require strong induction. This occurs when proving it for the case requires assuming more than just the case. In such situations, strong induction assumes that the conjecture is true for ALL cases from down to our base case.

The Sum of the first n Natural Numbers

Claim. The sum of the first natural numbers is


Proof. We must follow the guidelines shown for induction arguments. Our base step is   and plugging in we find that

Which is clearly the sum of the single integer . This gives us our starting point. For the induction step, let's assume the claim is true for so

Now, we have

as required.

The Sum of the first n Squares

Claim. The sum of the first squares is


Proof. Again, our base step is   and plugging in we find that

so the rule is certainly true when

This gives us our starting point. For the induction step, let's assume the claim is true for so

Now, we have

as required.

The Sum of the first n Cubes

Claim. The sum of the first cubes is

Notice that the formula is really similar to that for the first natural numbers.


Proof. Plugging in we find that

completing our base step.

For the induction step, let's assume the claim is true for so

Now, we have

as required.

Aside from being good examples of proof by simple or weak induction, these formulas are useful to find an integral as a limit of a Riemann sum.