Induction

An example of Induction

Prove that (1+2+3+...+n) = n(n+1)/2

Step 1:  Show true for n=1

(1) = 1  therefore true for n=1



Step 2:  Assume true for some n=k

Since we assumed it is true for some n=k we know that

(1+2+3+...+k) = k(k+1)
                -----
                  2



Step 3:  Now show true for n=k+1

We know that the sum of (1+2+3+...+k+1) = (1+2+3+...+k+(k+1)) = (1+2+3+...+k)+(k+1)

now we can use our assumption from step 2: (1+2+3+...+k)=k(k+1)/2  
let's substitute this into our equation and we get:

(1+2+3+...+(k+1))= (k(k+1)) + (k+1)
                    ------
                       2

Now if we distribute the k we get (k^2+k) + (k+1) 
                                   -----
                                     2

Now we simplify to get (k^2 +k+2k+2)
                        -----------
                             2

Which equals (k^2+3k+2)       (k+1)(k+2)    (k+1)((k+1)+1) 
              --------    =    --------   =   ----------
                  2               2               2

Therefore by induction:
(1+2+3...+n) = n(n+1)/2

An overview. The word 'induction' is used in two quite different ways in logic. There is traditional logic and there is modern mathematical logic. The mathematical one doesn't replace the traditional one, which remains correct, but the two are used in different spheres.

More people these days are more familiar with mathematics than with traditional logic so this might need to be stated clearly for those who are confused.

Traditionally, arguments are either deductive or inductive. Deduction gives certainty, induction only gives likelihood. If you can prove deductively that something is true, there is no way it can fail to be. If you argue inductively towards a conclusion, you only demonstrate a high probability that the matter will turn out be to true. (A third possibility, formulated in the late nineteenth century, is abduction.)

Examples: the sun has risen every day so far, all swans so far examined are white, and all known crows are black. So we can presume, by induction, that the sun will rise tomorrow, that all swans are white, and that all crows are black. David Hume articulated the classic argument that we can never entirely rely on such inductive reasonings, no matter how well grounded they seem to be on evidence. Frivolous thought: Perhaps he was writing just after the discovery of black swans in New Holland.

In mathematics there is a different principle called 'induction' or 'mathematical induction', which is deductive. Mathematical induction is a valid deductive argument and gives the answer with certainty (if the conditions are fulfilled): it is not inductive in the traditional sense and does not suffer from Hume's Problem of Induction.

The usual form of mathematical induction works by proving a formula for (i) some trivial case such as k = 0 or k = 1, and (ii) a general conditional that if it's true for arbitrary k then it's true for k + 1. If these jointly hold then it's true for all natural numbers k.

A superficially stronger form is called strong induction. This requires for condition (ii) that the formula holds not just for the one k previous to the one we're now considering, but for all k less than it. Usually this is harder to establish but with some problems it's easier. The end result is the same, that it's true for all k.

There is a technique called transfinite induction that uses the same kind of method, but instead of being limited to all natural numbers, it is applicable to all ordinals at every level of infinity. This has three branches: (i) a trivial initial condition such as k = 0, (ii) a successor condition that if it's true for an ordinal k then it's true for its successor ordinal k + 1, and (iii) a limit condition that if it's true for all k less than some limit ordinal λ then it's true for λ.

Transfinite induction is not however inherently true, in the sense that it's not in the usual axioms of set theory: it is equivalent to the Axiom of Choice, to the Well Ordering Theorem, and to Zorn's Lemma. It is therefore possible to have alternative mathematical logics in which it doesn't hold.

In*duc"tion (?), n. [L. inductio: cf. F. induction. See Induct.]

1.

The act or process of inducting or bringing in; introduction; entrance; beginning; commencement.

I know not you; nor am I well pleased to make this time, as the affair now stands, the induction of your acquaintance. Beau. & Fl.

These promises are fair, the parties sure, And our induction dull of prosperous hope. Shak.

2.

An introduction or introductory scene, as to a play; a preface; a prologue.

[Obs.]

This is but an induction: I will draw The curtains of the tragedy hereafter. Massinger.

3. Philos.

The act or process of reasoning from a part to a whole, from particulars to generals, or from the individual to the universal; also, the result or inference so reached.

Induction is an inference drawn from all the particulars. Sir W. Hamilton.

Induction is the process by which we conclude that what is true of certain individuals of a class, is true of the whole class, or that what is true at certain times will be true in similar circumstances at all times. J. S. Mill.

4.

The introduction of a clergyman into a benefice, or of an official into a office, with appropriate acts or ceremonies; the giving actual possession of an ecclesiastical living or its temporalities.

5. Math.

A process of demonstration in which a general truth is gathered from an examination of particular cases, one of which is known to be true, the examination being so conducted that each case is made to depend on the preceding one; -- called also successive induction.

6. Physics

The property by which one body, having electrical or magnetic polarity, causes or induces it in another body without direct contact; an impress of electrical or magnetic force or condition from one body on another without actual contact.

Electro-dynamic induction, the action by which a variable or interrupted current of electricity excites another current in a neighboring conductor forming a closed circuit. -- Electro-magnetic induction, the influence by which an electric current produces magnetic polarity in certain bodies near or around which it passes. -- Electro-static induction, the action by which a body possessing a charge of statical electricity develops a charge of statical electricity of the opposite character in a neighboring body. -- Induction coil, an apparatus producing induced currents of great intensity. It consists of a coil or helix of stout insulated copper wire, surrounded by another coil of very fine insulated wire, in which a momentary current is induced, when a current (as from a voltaic battery), passing through the inner coil, is made, broken, or varied. The inner coil has within it a core of soft iron, and is connected at its terminals with a condenser; -- called also inductorium, and Ruhmkorff's coil. -- Induction pipe, port, ∨ valve, a pipe, passageway, or valve, for leading or admitting a fluid to a receiver, as steam to an engine cylinder, or water to a pump. -- Magnetic induction, the action by which magnetic polarity is developed in a body susceptible to magnetic effects when brought under the influence of a magnet. -- Magneto-electric induction, the influence by which a magnet excites electric currents in closed circuits.

Logical induction, Philos., an act or method of reasoning from all the parts separately to the whole which they constitute, or into which they may be united collectively; the operation of discovering and proving general propositions; the scientific method. -- Philosophical induction, the inference, or the act of inferring, that what has been observed or established in respect to a part, individual, or species, may, on the ground of analogy, be affirmed or received of the whole to which it belongs. This last is the inductive method of Bacon. It ascends from the parts to the whole, and forms, from the general analogy of nature, or special presumptions in the case, conclusions which have greater or less degrees of force, and which may be strengthened or weakened by subsequent experience and experiment. It relates to actual existences, as in physical science or the concerns of life. Logical induction is founded on the necessary laws of thought; philosophical induction, on the interpretation of the indications or analogy of nature.<-- "scientific method" is now considered as the latter, rather than the former! -->

Syn. -- Deduction. -- Induction, Deduction. In induction we observe a sufficient number of individual facts, and, on the ground of analogy, extend what is true of them to others of the same class, thus arriving at general principles or laws. This is the kind of reasoning in physical science. In deduction we begin with a general truth, which is already proven or provisionally assumed, and seek to connect it with some particular case by means of a middle term, or class of objects, known to be equally connected with both. Thus, we bring down the general into the particular, affirming of the latter the distinctive qualities of the former. This is the syllogistic method. By induction Franklin established the identity of lightning and electricity; by deduction he inferred that dwellings might be protected by lightning rods.

 

© Webster 1913.