Induction and mathematical induction. Induction is
the process of discovering general laws by the observation
and combination of particular instances. It is used in all 
sciences, even in mathematics. Mathematical induction
is used in mathematics alone to prove theorems of a 
certain kind. It is rather unfortunate that the names are 
connected because there is very little logical 
connection between the two processes.  There is, however, some practical 
connection; we often use both methods together.
We are going to illustrate both methods by the same 
example.
1.   We may observe, by chance, that

       1 + 8 + 27 + 64 = 100 

and recognising the cubes and the square, we may give
to the fact we observed the more interesting form:

       1^3 + 2^3 + 3^3 + 4^3 = 10^2

How does such a thing happen?  Does it often happen
that such a sum of successive cubes is a square?
     In asking this we are like the naturalist who, impressed
by a curious plant or a curious geological formation,
conceives a general question. Our general question is
concerned with the sum of successive cubes
 
    1^3 + 2^3 + 3^3 + ... + n^3

We were led to it by the "particular instance" n=4

     What can we do for our question?  What the naturalist
would do; we can investigate other special cases.  The
special cases n=2, 3 are still simpler, the case n=5 is
the next one.  Let us add, for the sake of uniformity and
completeness, the case n=1.  Arranging neatly all these
cases, as a geologist would arrange his specimens of a 
certain ore, we obtain the following table:


1                         =    1    =   1 ^ 2 
1  +  8                   =    9    =   3 ^ 2
1  +  8  +  27            =   36    =   6 ^ 2
1  +  8  +  27 + 64       =  100    =   10^ 2
1  +  8  +  27 + 64  + 125=  225    =   15^ 2

It is hard to believe that all these sums of consecutive
cubes are squares by mere chance.  In a similar case, the
naturalist would have little doubt that the general law
 suggested by the special cases heretofore observed is correct;
the general law is almost proved by induction., The
mathematician expresses himself with more reserve although
fundamentally, of course, he thinks in the same
fashion.  He would say that the following theorem is
strongly suggested by induction;
 
      The sum of the first n cubes is a square

2.  We have been led to conjecture a remarkable somewhat
mysterious law.  Why should those sums of successive
cubes be squares?  But, apparently, they are squares.
     What would the naturalist do in such a situation?  He 
would go on examining his conjecture. In so doing, he 
may follow various lines of investigation. The naturalist
may accumulate further experimental evidence; if we wish 
to do the same we have to test the next cases
n=6,7,... The naturalist may also reexamine the
facts whose observation has led him to his conjecture
he compares them carefully he tries to disentangle some
deeper regularity, some further analogy.  
Let us follow this line of investigation.
     Let us reexamine the cases n=1,2,3,4,5 which we 
arranged in our table. Why are all these sums squares?
What can we say about these squares? Their bases are 
1,3,6,6,10,15. What about these bases?  Is there some
deep regularity, some further3r analogy?  Is there some deeper
regularity, some further analogy? At any rate, they do not
seem to increase too irregularly.  How do they increase
The difference between two successive terms of this sequence
 is itself increasing
3-1=2, 6-3=3, 10-6=4, 15-10=5

Now these differences are conspicuously regular.  We may 
see here a surprising analogy between the bases of 
those squares we may see a remarkable regularity in the he numbers
1,3,6,10,15;

1=1
3=1+2
6=1+2+3
10=1+2+3+4
15=1+2+3+4

If this regularity is general (and the contrary is hard to 
believe) the theorem we suspected takes a more precise
form:

 It is, for n = 1,2,3,...

1^3 + 2^3 + 3^3 + ... + n^3 =  ( 1+ 2 + 3 + ... + n) ^ 2
 
3. The law we just stated was found by induction, and the manner
in which it was found conveys to us an idea
about induction which is necessarily one-sided and imperfect
but not distorted. Induction tries to find
regularity and coherence behind the observations. Its most
conspicuous instruments are generalisation, specialisation, 
analogy. Tentative generalisation starts from an effort to
understand the observed facts; it is based on analogy, and
tested by further special cases.
     We refrain from further remarks on the he subject of 
induction about which there is wide disagreement among
philosophers. But it should be added that many mathematician
results were found by induction first and proved 
later. Mathematics presented with rigour is a systematic
deductive science but mathematics in the he making is an 
experimental inductive science.
4.  In mathematics as in the physical sciences we may
use observation and induction to discover general laws.
But there is a difference. In the physical sciences, there is 
no higher authority than observation and induction but
in mathematics there is such an authority: rigorous
proof.
     After having worked a while experimentally it may be 
good to change our point of view.  Let us be strict. We
have discovered an interesting result but the reasoning
that led to it was merely plausible, experimental,
provisional, heuristic; let us try to establish it definitely by
a rigorous proof.
     We have arrived now at a "problem to prove": to
prove or to disprove the result stated before (See 2, 
above).
     There is a minor simplification. We may know that
       
             1 + 2 + 3 + ... + n = n(n+1)/2

At any rate, this is easy to verify. Take a rectangle with 
sides n and n+ 1, and divide it in two halves by a zigzag
line as in Fig. 15a which shows the case n=4. Each of 
the halves is "staircase-shaped" and its area has the
expression 1+2+...+n for n=4 it is 1+2+3+4
see Fig 18 b. now the whole area of the rectangle is 
n(n+1) of which the staircase shaped area is one half;
this proves the formula

     _____________     _____________
    T          _| T   T          _| T
    |        _|   |   |        _| | |
    |      _|     |   |      _| | | |
    |    _|       |   |    _| | | | |
    |  _|         |   |  _| | | | | |
    | |           |   | | | | | | | |
    ~~~~~~~~~~~~~L    ~~~~~~~~~~~~~~L

             Fig. 18

We may transform the result which we found by in-
induction into

      1^3  + 2^3 + 3^3 + ... + n^3  = (n(n+1)/2)^2

5.  If we have no idea how to prove this result, we may
at least test it. Let us test the first case we have not
tested yet, the case n=6. For this value, the formula
yields.

      1 + 8 + 27 + 64 + 125 + 216  = (6*7/2)^2

and, on computation, this turns out to be true, both sides
being equal to 441.
     We can test the formula more effectively.  The formula
is, very likely, generally true, true for all values of n.
Does it remain true when we pass from any value n to 
the next value n+1?  Along with the formula as written
above (p.118) we should also have

1^3 + 2^3 + 3^3 + ... + n^3 + (n+1)^3 = ((n+1)(n+2)/2)^2

Now, there is a simple check. Subtracting from this the
formula written above, we obtain

(n+1)^3 = ((n+1)(n+2)/2)^2 - (n(n+1)/2)^2

this is, however, easy to check. The right hand side may 
be written as

((n+1)/2)^2 * [(n+2)^2-n^2] = ((n+1)/2)^2 [n^2 + 4n + 4 - n^2]

(n+1)^2/4 * (4n+4)      =  (n+1)^2(n+1) = (n+1)^3

We do not know yet whether
 
1^3 + 2^3 + 3^3 + ... + n^3 = (n(n+1)/2)^2

is true. But if we know that this was true we could infer,
by adding the equation which we have verified beyond doubt that
 
1^3 + 2^3 + 3^3 + ... + n^3 + (n+1)^3  = ((n+1)(n+2)/2)^2

is also true which is the same assertion for the next integer n+1.
Now we actually know that or conjecture is true for n=1,2,3,4,5,6. By
virtue of what we have just said. The conjecture, being true for n=6,
must also be true for n=7; being true for n=7 it is true for n=8;
being true for n=8 if is true for n=9; and so on.  It holds for all n,
it is proved to be true generally.  
6. The foregoing proof may serve as a pattern in many similar 
cases. What are the essential lines of this pattern?  The
assertion we have to prove must be given in advance, in 
precise form.  The assertion must depend on an integer n. The
assertion must be sufficiently "explicit" so that we have some
possibility of testing whether it remains true in the passage from n
to the next integer n+1.  If we succeed in testing this effectively,
we may be able to use our experience, gained in the process of
testing, to conclude that the assertion must be true or n+1 provided
it is true for n.  When we are so far it is sufficient to know that
the assertion is true for n=1; hence it follows for n=2; hence it
follows for n=3, and so on; passing from any integer to the next, we
prove the assertion generally.  This process is so often used that it
deserves a name.  We could call it "proof from n to n+1" or still
simpler "passage to the next integer."  Unfortunately the accepted
technical term is "mathematical induction." This name results from a
random circumstance.  The precise assertion that we have to prove may
come from any source, and it is immaterial from the logical viewpoint
what the source is.  Now in many cases, as in the case we discussed
here in detail, the source is induction, the assertion is found
experimentally, and so the proof appears as a mathematical complement
to induction; this explains the name.  
7.  Here is another point, somewhat subtle, but important to
anybody who desires to find proofs by himself.  In the foregoing,
we found two different assertions by observation and induction, 
one after the other, the first under 1, the second under 2,
the second was more precise than the first.  Dealing
with the second assertion, we found a possibility of checking the
passage from n to n+1, and so we were able to find a proof by
"mathematical induction." Dealing with the first assertion, and
ignoring the precision added to it by the second one we should
scarcely have been able to find such a proof. In fact, th3e first
assertion is less precise, less explicit" less "tangible," less
accessible to testing and checking than the second one.  Passing from
the first to the second, from the les precise to the more precise
statement, was an important preparative for the final proof.  The
circumstance has a paradoxical aspect.  The second assertion is
stronger; it implies immediately the first, whereas the somewhat
"hazy" first assertion can hardly imply the more "clear-cut" second
one.  Thus, the stronger theorem is easier to master than the weaker
one; this is the INVENTORS PARADOX