This article is taken from the book 50 Mathematical ideas

Proof
Mathematicians attempt to justify their claims by proofs. The
quest for cast iron rational arguments is the driving force of
pure mathematics. Chains of Correct deduction from what is
known or assumed, lead the mathematician to a conclusion
which then enters the established mathematical storehouse.
Proofs are not arrived at easily – they often come at the end of a great
deal of exploration and false trails. The struggle to provide them occupies
the center ground of the mathematician’s life. A successful proof carries the
mathematician’s stamp of authenticity, separating the established theorem
from the conjecture, bright idea or first guess.
Qualities looked for in a proof are rigor, transparency and, not least, elegance.
To this add insight. A good proof is ‘one that makes us wiser‘- but it is also
better to have some proof than no proof at all. Progression on the basis of
unproven facts carries the danger that theories may be built on the
mathematical equivalent of sand.

Not that a proof lasts forever, for it may have to be revised in the light of
developments in the concepts it relates to.
What is a proof? When you read or hear about a mathematical result
do you believe it? What would make you believe it? One answer would be
a logically sound argument that progresses from ideas you accept to the
statement you are wondering about. That would be what mathematicians
call a proof, in its usual form a mixture of everyday language and strict logic.
Depending on the quality of the proof you are either convinced or remain
skeptical.
The main kinds of proof employed in mathematics are:

the method of the counterexample;

the direct method;

the indirect method;

and the method of mathematical induction.

<———-Foot Notes——————>
Euclid’s Elements provides the model for
mathematical proof  c.300 BC
Descartes promotes mathematical
rigor as a model in his Discourse
on Method   AD 1637

<——————————————->
The counterexample: Let’s start by being skeptical – this is a method of
proving a statement is incorrect. We’ll take a specific statement as an example.
Suppose you hear a claim that any number multiplied by itself results in an
even number. Do you believe this? Before jumping in with an answer we should
try a few examples. If we have a number, say 6, and multiply it by itself to get
6 x 6 = 36 we find that indeed 36 is an even number. But one swallow does nor
make a summer. The claim was for any number, and there are an infinity of
these. To get a feel for the problem we should try some more examples. Trying
9, say, we find that 9 x 9 = 81. But 81 is an odd number. This means that
the statement that all numbers when multiplied by themselves give an even
number is false. Such an example runs counter to the original claim and is
called a counterexample. A counterexample to the claim that ‘all swans are
white’, would be to see one black swan. Part of the fun of mathematics is
seeking out a counterexample to shoot down a would-be theorem.
If we fail to find a counterexample we might feel that the statement is correct.
Then the mathematician has to play a different game. A proof has to be
constructed and the most straightforward kind is the direct method of proof.
The direct method:  In the direct method we march forward with logical
argument from what is already established, or has been assumed, to the
conclusion. If we can do this we have a theorem. We cannot prove that
multiplying any number by itself results in an even number because we have
already disproved it. But we may be able to salvage something. The difference
between our first example, 6, and the counterexample, 9, is that the first
number is even and the counterexample is odd. Changing the hypothesis is
something we can do. Our new statement is: if we multiply an even number by
itself the result is an even number.
First we try some other numerical examples and we find this statement verified
every time and we just cannot find a counterexample. Changing tack we try
to prove it, but how can we start?’ We could begin with a general even number
n, but as this looks a bit abstract we’ll see how a proof might go by looking at
a concrete number, say 6. As you know, an even number is one which is a
multiple of 2, that is 6 — 2 x3. As 6 x 6 = 6 + 6 + 6 + 6 + 6 + 6 or, written
another way, 6 x 6 = 2 x 3 + 2 x 3 + 2 x 3 + 2 x 3 + 2 x 3 + 2 x 3 or,rewriting
using brackets,

<————-Foot Notes —————>
De Morgan introduces the term
‘mathematical induction’   1838
Bishop proves results
exclusively by constructive
methods  1967
lmre Lakatos publishes the
influential Proofs an d Refutations  1976
<———————————————–>

6×6=2x(3+3+3+3+3+3)
This means 6 x 6 is a multiple of 2 and, as such, is an even number. But in this
argument there is nothing which is particular to 6, and we could have started
with n = 2 x k to obtain
n x n = 2 x (k+k+…+k)
and conclude that n x n is even. Our proof is now complete’ In translating
Euclid’s Elements, latter-day mathematicians wrote ‘QED’ at the end of a proof
to say job done – it’s an abbreviation for the Latin quod erat demonstradum
(which was to be demonstrated). Nowadays they use a filled-in square l. This is
called a halmos after Paul Halmos who introduced it.
The indirect method:  In this method we pretend the conclusion is false
and by a logical argument demonstrate that this contradicts the hypothesis’
Let’s prove the previous result by this method.
Our hypothesis is that n is even and we’ll pretend n x n is odd. We can write
n x n : n + n + . . . + n and there are n of these. This means n cannot be even
(because if it were n x n would be even). Thus n is odd, which contradicts the
hypothesis.
This is actually a mild form of the indirect method. The full-strength indirect
method is known as the method o{ reductio ad absurdum

(reduction to the
absurd), and was much loved by the Greeks. In the academy in Athens,
Socrates and Plato loved to prove a debating point by wrapping up their
opponents in a mesh of contradiction and out of it would be the point they
were trying to prove. The classical proof that the square root of 2 is an irrational
number is one of this form where we start off by assuming the square root of 2 is
a rational number and deriving a contradiction to this assumption.
The method of mathematical induction  Mathematical
induction is powerful way of demonstrating that a sequence of statements P1,
P2, P3, .. . are all true. This was recognized by Augustus De Morgan in the
1830s who formalized what had been known for hundreds of years. This specific
technique (not to be confused with scientific induction) is widely used to prove
statements involving whole numbers. It is especially useful in graph theory,
number theory and computer science generally. As a practical example, think
of the problem of adding up the odd numbers. For instance, the addition of the
first three odd numbers 1 + 3 + 5 is 9 while the sum of first four I + 3 + 5 + 7 is
16.Now 9 is 3 x 3 = 3 squared and 16 is 4 x 4= 4 squared,

so could it be that the addition of
the first n odd numbers is equal to n squared?

If we try a randomly chosen value of n,

say n = 7, we indeed find that the sum of the first seven is 1 + 3 + 5 + 7 + 9 +
1 1 + 13 = 49 which is 7 squared. But is this pattern followed for all values of n?

How can we be sure? We have a problem, because we cannot hope to check an
infinite number of cases individually.
This is where mathematical induction steps in. Informally it is the domino
method of proof. This metaphor applies to a row of dominoes standing on their
ends. If one domino falls it will knock the next one down. This is clear. All we
need to make them all fall is the first one to fall. We can apply this thinking to
the odd numbers problem, The statement P’ says that the sum of the first n
odd numbers adds up to n squared.

Mathematical induction sets up a chain reaction
whereby P1, P2, P3,. . . will all be true. The statement P1 is trivially true
because1 = 1 squared. Next, P2 is true

because1 + 3 = l squared  +3 =2 squared, P3 is true because
1 + 3 + 5 = 2 squared + 5 = 3 squared and P4 is true

because I + 3 + 5 +7 = 3 squared + 7 = 4 squared
‘We use the result at one stage to hop to the next one. This process can be
formalized to frame the method of mathematical induction.
Difficulties with Proof: Proofs come in all sorts of styles and sizes.
Some are short and snappy, particularly those found in the text books. Some
others detailing the latest research have taken up the whole issue of journals
and amount to thousands of pages. Very few people will have a grasp of the
whole argument in these cases.
There are also foundational issues. For instance, a small number of
mathematicians are unhappy with the reductio ad absurdam method of
indirect proof ‘where it applies to existence. If the assumption that a solution
of an equation does not exist leads to a contradiction, is this enough to prove
that a solution does exist?  Opponents of this proof method would claim the
logic is merely sleight of hand and doesn’t tell us how to actually construct a
concrete solution. They are called ‘Constructivists’ (of varying shades) who
say the proof method fails to provide ‘numerical meaning’- They pour scorn on
the classical mathematician who regards the reductio method as an essential
weapon in the mathematical armory. On the other hand the more traditional
mathematician would say that outlawing this type of argument means working
with one hand tied behind your back and, furthermore, denying so many
results proved by this indirect method leaves the tapestry of mathematics
looking rather threadbare.
The condensed idea
 Signed and Sealed