Induction in Geometry

THE METHOD OF

MATHEMATICAL

INDUCTION

INDUCTION IN

GEOMETRY

THE METHOD OF

MATHEMATICAL

INDUCTION

I. S. Sominskii

Translated and adapted from the fifth Russian edition (1959) by Luise Lange and Edgar E. Enochs

INDUCTION IN

GEOMETRY

L. I. Golovina and I. M. Yaglom

Translated and adapted from the second Russian edition (1961) by A. W. Goodman and Olga A. Titelbaum

Dover Publications, Inc.

Mineola, New York

This volume includes both The Method of Mathematical Induction and Induction in Geometry. Both books can serve as an introduction to mathematical induction for solving analytical problems, and they contain numerous examples from the fields of algebra, geometry, and trigonometry. Many of the problems are solved in the text, while others are left for the reader to determine.

Copyright

Copyright © 2019 by Dover Publications, Inc.

All rights reserved.

Bibliographical Note

This Dover edition, first published in 2019, is an unabridged republication in one volume of The Method of Mathematical Induction and Induction in Geometry, both originally published in 1963 by D. C. Heath and Company, Boston, as part of the Survey of Recent East European Mathematical Literature series.

Library of Congress Cataloging-in-Publication Data

Names: Sominskiæi, I. S. (Il§ëiìa. Samuilovich), author. | Golovina, L. I. (Lidiëiìa Ivanovna), author. | ëIìAglom, I. M. (Isaak Moiseevich), 1921-1988, author.

Title: The method of mathematical induction / I.S. Sominskii. Induction in geometry / L.I. Golovina and I.M. Yaglom.

Other titles: Metod matematicheskoæi indukëtìsii. English | Induction in geometry

Description: Dover edition. | Mineola, New York : Dover Publications, Inc., [2019] | An unabridged republication in one volume of: The method of mathematical induction, and Induction in geometry, both originally published in Boston by D.C. Heath and Company, 1963, as part of the Survey of recent East European mathematical literature series.

Identifiers: LCCN 2019018298| ISBN 9780486838564 | ISBN 0486838560

Subjects: LCSH: Induction (Mathematics) | Geometry—Problems, exercises, etc. | Logic.

Classification: LCC QA9 .S5813 2019 | DDC 511.3/—1dc23

LC record available at https://lccn.loc.gov/2019018298

Manufactured in the United States by LSC Communications

83856001

www.doverpublications.com

2019

THE METHOD OF

MATHEMATICAL

INDUCTION

I. S. Sominskii

PREFACE TO THE AMERICAN EDITION

THE METHOD of mathematical induction is a widely used method of mathematical proof. Without command of this method it is impossible to make a serious study of mathematics. Moreover, the basic idea which underlies the method of mathematical induction is interesting not only to students of mathematics and the applied sciences, but also to students in other fields.

The fundamental ideas of the method of mathematical induction, and some of its simpler applications, are presented in Chapter 1 and in section 1 of Chapter 2. To understand this portion of the text no mathematics is needed beyond what is usually covered in a year and a half of high school algebra. For the rest of the booklet, however, it would be desirable to have the background of two years of algebra and a course in trigonometry.

This booklet is particularly suitable for independent study. It contains a large number of problems, some of which are solved as part of the text. More than half of the problems, however, are left as exercises for the reader, with solutions given at the end of the booklet.

CONTENTS

Introduction

CHAPTER 1. The Method of Mathematical Induction

1. Examples of unsound induction in mathematics

2. More examples of unsound induction

3. The principle of mathematical induction

4. Proof by mathematical induction

5. Using mathematical induction to detect faulty conjectures

CHAPTER 2. Examples and Exercises

6. Elementary examples and exercises from algebra and geometry

7. Advanced examples and exercises

CHAPTER 3. Proofs of Some Theorems of Algebra

8. Polynomials and progressions

9. Permutations, combinations, and the binomial theorem

Solutions of Exercises in Chapter 2

Introduction

Any statement can be classified as general or particular.

Examples of general statements are:

All citizens of the U.S.S.R. are entitled to an education.

The diagonals of a parallelogram bisect one another.

All numbers ending in zero are divisible by 5.

Examples of particular statements are:

Petrov is entitled to an education.

The diagonals of the parallelogram ABCD bisect one another. 140 is divisible by 5.

The process of deriving a particular statement from a general statement is called deduction. Consider these statements:

(1) All citizens of the U.S.S.R. are entitled to an education.

(2) Petrov is a citizen of the U.S.S.R

(3) Petrov is entitled to an education.

From general statement (1), together with particular statement (2), we obtain particular statement (3).

The process of obtaining general statements from particular statements is called induction. Inductive reasoning may lead to false as well as to true conclusions. We shall clarify this point by two examples.

FIRST EXAMPLE.

(1) 140 is divisible by 5.

(2) All numbers ending in zero are divisible by 5.

General statement (2), obtained from particular statement (1), is true.

SECOND EXAMPLE.

(1) 140 is divisible by 5.

(2) All three-place numbers are divisible by 5.

In this case, general statement (2), derived from particular statement (1), is false.

How can induction be used in mathematics so that only true general statements are obtained from particular statements? The answer to this question is given in this booklet. ²

1. The Method of Mathematical Induction

1. EXAMPLES OF UNSOUND INDUCTION IN MATHEMATICS

First let us consider two examples of the sort of induction which is inadmissible in mathematics.

EXAMPLE 1. Let

The following equalities are easy to verify:

On the basis of these four results, one might conclude that for all natural numbers n it is true that

EXAMPLE 2. Next let us consider the trinomial x² + x + 41, first considered by the famous mathematician L. Euler.¹ If we replace x by the number 0 in this trinomial, we obtain the prime number 41. If we replace x by the number 1, we again obtain a prime number, namely 43. If we continue in this manner and replace x by the numbers 2, 3, 4, 5, 6, 7, 8, 9, 10, successively, we obtain in each case a prime number: 47, 53, 61, 71, 83, 97, 113, 131, 151, respectively. On the basis of these results one might conclude that for any nonnegative integer x, the value of the trinomial is a prime number.

Why is the reasoning used in these examples inadmissible in mathematics? In what way is the reasoning invalid?

In both the examples the reasoning employed led us to assert a general statement referring to any n (or any x) on the basis that the statements had been found true for certain particular values of n (or of x). It so happens that the general statement obtained in Example 1 is true, as we shall see below in Example 5; however, the general statement obtained in Example 2 is false. Indeed, while it can be shown that the trinomial x² + x + 41 yields prime numbers for x = 0, 1, 2, 3, ... , 39, for x = 40 the value of the trinomial is seen to be 41², which is a composite number.

Induction has wide applications in mathematics, but it must be used with care or it may lead to erroneous conclusions.

1. MORE EXAMPLES OF UNSOUND INDUCTION

We have encountered in Example 2 a statement which proves to be true in forty instances, but which is not true in general. We shall give two additional examples of statements which are true in some particular instances without being true in general.

EXAMPLE 3. The binomial xn – 1 (where n is a natural number) is of great interest to mathematicians as it is closely related to the geometric problem of dividing a circle into n equal parts. Hence, it is not surprising that this binomial has been studied with great care, with particular attention to the question of resolving it into factors with integral coefficients.

In studying these factorizations for many particular values of n, mathematicians noted that in each of the cases studied, the absolute values of the coefficients of the factors never exceeded the number 1. Thus,

Tables of coefficients were made, and in each case the coefficients had the property mentioned above. Nevertheless, all attempts to prove the statement true for all values of n failed.

The problem was finally solved in 1941 by V. Ivanov with the following result: If n < 105, the binomial xn – 1 has the above property. One of the factors of x¹⁰⁵ – 1, however, is the polynomial

which no longer has this property.

EXAMPLE 4. Into how many parts is space divided by n planes which pass through the same point, but no three of which intersect in the same straight line?

Let us consider the simplest special cases of this problem: One plane divides space into 2 parts. Two planes passing through a common point divide space into 4 parts. Three planes passing through a common point, but having no line in common, divide space into 8 parts.

At first glance it may appear that as the number of planes increases by 1, the number of parts into which they divide space is doubled, so that 4 planes would divide space into 16 parts, 5 planes into 32 parts, and so on; or, in general, that n planes would divide space into 2n parts.

Actually, this is not the case: 4 planes divide space into 14 parts, 5 planes into 22 parts. In general, n planes divide space into n(n – 1) + 2 parts.¹

These examples illustrate the following simple but important fact: A statement may be true in many special instances and yet not be true in general.

1. THE PRINCIPLE OF MATHEMATICAL INDUCTION

Now the following question arises: Suppose that we have a statement involving natural numbers which we have found to be true in some particular instances. How can we determine whether the statement is true in general; or, to be more specific, how can we determine whether the statement is true for all natural numbers n = 1, 2, 3, ... ?

This question can sometimes be answered by using a special method of reasoning called the method of mathematical induction (complete induction), based on the following principle:

A statement is true for every natural number n if the following conditions are satisfied:

Condition 1. The statement is true for n = 1.

Condition 2. The truth of the statement for any natural number n = k implies its truth for the succeeding natural number n = k + 1.

Proof We want to show that if conditions 1 and 2 hold, then the statement must be true for every natural number n. We give an indirect proof: If it were not true for every natural number, there would be a smallest natural number, call it m, for which the statement is false. By condition 1, m ≠ 1. Thus, m > 1, so that m – 1 is a natural number. Recalling that m is the smallest natural number for which the statement is false, we see that the statement is true for m – 1 but false for the succeeding natural number (m – 1) + 1 = m. But this contradicts condition 2. Therefore, the statement must be true for every natural number.

Remark. In our proof of the principle of mathematical induction, we used the property of natural numbers that every set of natural numbers contains a smallest number. One can easily show that this property in turn can be deduced from the principle of mathematical induction. Hence, the two propositions are equivalent: Either one can be taken as an axiom defining the sequence of natural numbers; the other statement is then a theorem.

1. PROOF BY MATHEMATICAL INDUCTION

A proof by mathematical induction necessarily consists of two parts, that is, proof that the statement satisfies the two independent conditions given in section 3.

EXAMPLE 5. Find the sum (see Example 1)

SOLUTION. We know that

This time we shall not repeat the erroneous reasoning used in Example 1, and we shall not