0. Code

>	restart; with(plots):

Warning, the name changecoords has been redefined

>

>	StandardPlot  :=  proc( expr )      end proc:

  1. The Concept - Sum of Integers Formula

Here is a formula the sum of the first n positive integers.

>	`1 + 2 + 3 + .... + n` = n*(n+1)/2;

In a sense this formula is a function. Given an integer n, the sum of the first n integers is the value of this formula

>	S := n -> n*(n+1)/2;

It appears to work for n = 1, n = 2, in fact all n values through 15 at least.

>

S(1); 1;

>	S(2); 1 + 2;

>	for k from 1 to 15 do        `when k = `, k,`, the sum is `,         sum( j, j = 1..k),` and the formula gives `, S(k); od;

So it appears  that this formula works - however, how do we know it doesn't fail for some larger value of n? We can't check an infinite number of possible values.

Here is a way. Since we know it works for some values of n, that is a good start. But now if we can show that whenever it works for one value, it also works for the next value, then we'll be certain that it always works. What we are saying is that if it works for n, then if we the next integer, n+1, we should get the value of the formula for S(n+1). Lets see if these two are equal.

>	S(n+1) = S(n) + (n+1);

>	expand(lhs(%)) = expand(rhs(%)) ;

>	verify(lhs(%), rhs(%), testeq);

They are! We have proven the formula is true for all integers n ³ 1. This is, in essence, the method of mathematical induction. There are two indispensable steps :
            
            Mathematical Induction - to Verify a Formula

            1. Show that it works for at least one value of n
            2. Show that whenever it works for a general value of n, it also works for the next value.

The first step is usually very easy - simply plug in a value and show it works for that one value. The second step involves expressing the same value in two different ways, as we did above.

  2. More Examples of Equalities

Here is another example. Lets do this in a more streamlined way following the two steps above.

        Example 2.1  : Prove that  +  +  +...+  =   
                                 is true for all integers n > 0.

>	S := n -> n/(n+1);

                  Step 1  : Verify for n = 1

>	S(1) = 1/(1*2);

                Step 2 : Show that the formula for S(n+1) holds if it holds for S(n).

>	S(n+1) = S(n) + 1/( (n+1)*( (n+1) + 1) );

>	simplify(lhs(%)) = simplify(rhs(%)) ;

>	testeq( lhs(%) = rhs(%) );

Done!



        Example 2.2  :    .... + =

This one is a little trickier, because we can't simply add another term to find S(n+1) because S(n) is a square. To get around this, we can take the sqareroot of S(n), add (n+1)^3, then square that result to demonstrate the veracity of this formula.

>	restart: S := n -> sum( k, k = 1..n)^2 ;

                  Step 1  : Verify for n = 1

>	S(1) = 1^3;

                Step 2 : Show that the formula for S(n+1) holds if it holds for S(n).

>	S(n+1) = sqrt( S(n) + (n+1)^3) ^2;

>	simplify(lhs(%)) = simplify(rhs(%)) ;

>	testeq( lhs(%) = rhs(%) );

Done!

        Example 2.3  : Prove that  +  +  +...+  =   
                                 is true for all integers n > 0.

>	S := n -> 2^(n+1) - 1;

                  Step 1  : Verify for n = 1

>

S(1) = 1;

                Step 2 : Show that the formula for S(n+1) holds if it holds for S(n).

>	S(n+1) = S(n) + 2^(n+1);

>	simplify(lhs(%)) = simplify(rhs(%)) ;

>	testeq( lhs(%) = rhs(%) );

Done!

  3. Induction & Inequalities

When we are trying to prove an inequality rather than an equation, we go through the same two general steps, but we can't express the result as a function.

       Example 3.1  : Prove that       is true for all integers .

>	Inequal :=  2*n + 1 <= n^2;

                  Step 1  : Verify for n = 3 (the smaller number we can start at in this case)

>	subs( n = 3, Inequal); verify(lhs(%), rhs(%) ,{'less_than','equal'});

                Step 2 : Show that the formula for S(n+1) holds if it holds for S(n).  Let's substitute n+1 for n, in the left side of the inequality,
               with the hope of showing it is less than the right side.

>	LHS := subs( n = n+1, lhs(Inequal) );

>	% = '(2*n + 1),` + `,2';

                Since we know the the inequality is true for n, we can make this statement :

>	LHS < ''n^2 + 2'';

              Also, by hypothesis :

>

2 < n;

>	2 < 2*n + 1;

>	'LHS' < 'n^2 + (2*n+1)';

>	n^2 + (2*n+1): % = factor(%) ;

>	LHS < (n+1)^2;

>	subs( n = n+1, Inequal);

So we have demonstrated the inequality is also true for n+1!


        Example 3.2  : Prove that     is true for all integers .

>	Inequal := n^2 <= 2^n;

                  Step 1  : Verify for n = 4

>	subs( n = 4, Inequal); verify(lhs(%), rhs(%) ,{'less_than','equal'});

                Step 2 : Show that S(n+1) follows if S(n) is true. We can assume that .

>	LHS := subs( n = n+1, lhs(Inequal) );

>	expand(%);

                   Using the inequality above in example 3.1....

>	LHS := %; LHS <= n^2 + n^2;

                   Using the fact that

>	2*n^2 <= 2*(2^n);

>	2*n^2 <= 2^(n+1);

Done!

  4. Divisibility

Here is another variation - demonstrating that an expression is divisible by some number for all integers plugged into the formula.

       Example 4.1  : Prove that    is divisible by 3 for all integers n > 0.

>	S := n -> n^3 + 14*n + 3;

                  Step 1  : Verify for n = 1

>	S(1); %/3;

                Step 2 : Show that the formula for S(n+1) holds if it holds for S(n).

>

S(n+1);

>	expand(%);

              Lets take the difference of S(n+1) and S(n) - this will eliminate the .

>	difference := S(n+1) - S(n);

             We expand the difference and find that each term is divisible by three!

>	expand(%);

>

%/3;

             This proves it. Do you see how? S(n+1) = S(n) + a polynomial divisible by three. Since both polynomials
             on the right are divisible by 3, then so is the left side, since they are equal.

>	S(n+1) = 'S(n) + 3*(%)';