Proof by Induction

9 Key excerpts on "Proof by Induction"

• 

  eBook - ePub

  Discrete Mathematics with Ducks

  • sarah-marie belcastro(Author)
  • 2018(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Induction

  4.1 Introduction and Summary

  This proof technique is more complicated than the previous techniques, so it merits a chapter of its own. But there’s only so much to say about mathematical induction, and then you just have to practice this proof technique for yourself. The basic idea is to reduce a theorem to a smaller case of the same theorem, and then to a smaller case, and so on to a small case you can deal with manually. Example 4.2.4 is particularly important, first because it shows why one must reduce to a previously known case (rather than building up from a known case), and second because it is a result we will use regularly in Chapters 10–13.

  Unlike the previous topics addressed in this book, there are no everyday applications of induction. It instead applies to most of mathematics and computer sciences—as a proof technique, it arises frequently in each field at all levels.

  4.2 Induction

  We will begin with an example of a Proof by Induction using only basic arithmetic, then describe induction in general, and then give an extended example of a Proof by Induction about sets.

  Example 2.1 Do you believe that if

  n > 0

  , then

  2 n

  > n

  ? Let’s check to see whether this statement holds for a few values of n .

  When

  n = 1

  , we see that

  2 1

  = 2

  , and

  2 > 1

  .

  When

  n = 2

  , we see that

  2 2

  = 4

  , and

  4 > 2

  .

  When

  n = 423

  , we see that

  2 423

  = 14 , 134 , 776 , 518 , 227 , 074 , 636 , 666 , 380 , 005 ,

  943, 348, 126, 619, 871, 175, 004, 951, 664, 972, 849, 610, 340, 958, 208 and that is certainly greater than 423.

  Yes, the statement if

  n > 0

  , then

  2 n

  > n

  seems to be true. We have checked it for small values of n , which are known as base cases .

  To prove the statement, we will first suppose that when n is less than or equal to some indeterminate k (but greater than 0),

  2 n

  > n

  . This is called the inductive hypothesis .

  If we can show that this assumption allows us to prove that

  2

  k + 1

  > k + 1

  , then we will have proved that

  2 n

  > n

  for all

  n > 0

  . This process is known as the inductive step

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Journey into Mathematics

  An Introduction to Proofs

  • Joseph J. Rotman(Author)
  • 2013(Publication Date)
  • Dover Publications

    (Publisher)

  Chapter 1

  Setting Out

  INDUCTION

  So, naturalists observe, a flea Hath smaller fleas that on him prey; And these have smaller still to bite ’em; And so proceed ad infinitum. Jonathan Swift

  There are many styles of proof, and mathematical induction is one of them. We begin by saying what mathematical induction is not. In the natural sciences, inductive reasoning is based on the principle that a frequently observed phenomenon will always occur. Thus, one says that the sun will rise tomorrow morning because, from the dawn of time, the sun has risen every morning. This is not a legitimate kind of proof in mathematics, for even though a phenomenon occurs frequently, it may not occur always.

  Inductive reasoning is valuable in mathematics, because seeing patterns often helps in guessing what may be true. On the other hand, inductive reasoning is not adequate for proving theorems. Before we see examples, let us make sure we agree on the meaning of some standard terms.

   

  Definition. An integer is one of 0, 1, – 1, 2, – 2, 3, – 3, .⋯

   

  Definition . An integer p ≥ 2 is called a prime number 1 if its only positive divisors are 1 and p . An integer m ≥ 2 which is not prime is called composite .

   

  A positive integer m is composite if it has a factorization m = ab, where a < m and b < m are positive integers; the inequalities are present to eliminate the uninteresting factorization m = m x 1. Notice that a ≥ 2: since a is a positive integer, the only other option is a = 1, which implies b = m (contradicting b < m ); similarly, b ≥ 2.

  The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41. That this sequence never ends is proved in Exercise 2.10. Consider the statement:

  f (n ) = n 2 – n + 41 is a prime number for every n ≥ 1

  (this is really a whole family of statements, one for each positive integer n ). As we evaluate f (n ) for n

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  The Elements of Advanced Mathematics

  • Steven G. Krantz(Author)
  • 2022(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  It turns out that the strong mathematical induction principle is logically equivalent to the ordinary mathematical induction principle enunciated at the outset of this section. But in some instances strong mathematical induction is the more useful tool. An alternative terminology for strong mathematical induction is “the set formulation of mathematical induction.”

  Strong mathematical induction is sometimes more convenient, or more natural, to use than ordinary mathematical induction; it finds particular use in abstract algebra.

  EXAMPLE 2.6.7 Let us show, using strong mathematical induction, that every integer greater than 1 is either prime or the product of primes. [Here a prime number is an integer greater than 1 whose only factors are 1 and itself.]

  For convenience we begin the mathematical induction process at the index 2 rather than at 1.

  (a) Let

  P ( j )

  be the assertion “Either n is prime or n is the product of primes.”

  (b) Then

  P ( 2 )

  is plainly true since 2 is the first prime.

  (c) Now assume that

  P ( ℓ )

  is true for

  2 ≤ ℓ ≤ j

  and consider

  P ( j + 1 )

  . If

  j + 1

  is prime, then we are done. If

  j + 1

  is not prime, then

  j + 1

  factors as

  j + 1 = k · m

  , where k, m are integers less than

  j + 1

  , but at least 2. By the strong inductive hypothesis, each of k and m factors as a product of primes (or is itself a prime). Thus

  j + 1

  factors as a product of primes.

  The strong mathematical induction is done, and the proof is complete. ⋄

  2.7 Other Methods of Proof

  We give here a number of examples that illustrate proof techniques other than direct proof, proof by contradiction, and mathematical induction.

  2.7.1 Proof by cases

  One obvious but powerful method for constructing a proof is to divide the question into cases. We illustrate with some examples.

  EXAMPLE 2.7.1 Let us show that every integer n which is a perfect cube is either (i) a multiple of 9, (ii) one less than a multiple of 9, or (iii) one more than a multiple of 9.

  We consider three cases:

  1. The integer n is the cube of a multiple of 3. So

  n =

  ( 3 j )

  3

  = 27

  j 3

  = 9 · ( 3

  j 3

  )

  . In this case, it is clear that n is a multiple of 9.

  2. The integer n is the cube of one less than a multiple of 3. Hence

  n =

  ( 3 j − 1 )

  3

  = 27

  j 3

  − 27

  j 2

  + 9 j − 1 = 9 ( 3

  j 3

  − 3

  j 2

  + j ) − 1

  . So we see that n

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Mathematics For Primary Teachers

  • Valsa Koshy, Ron Casey, Paul Ernest, Valsa Koshy, Ron Casey, Paul Ernest(Authors)
  • 2014(Publication Date)
  • Routledge

    (Publisher)

  Chapter 8 Mathematical proof

  DOI: 10.4324/9780203984062-10

  In the previous chapter the distinction was made between a sample and a population. A central problem for statisticians is that of devising ways of thinking which guard against ‘jumping to conclusions’ and attributing to a whole population what has been found out about a sample, without a scientific word of caution about the confidence you can legitimately have in such conclusions. In many respects, this is also a central, and much neglected, concern within mathematics. Remember the definitions of the universal and existential quantifiers in Chapter 4 , Section 5. Their use is in emphasising the difference between cases of something being true for all possibilities and something being true for just some possibilities. In this chapter the notion and strategies of proof will be explored. The appreciation of what is involved in designing your own proofs and following the proofs of others will, it is hoped, be enhanced by contrasting proof with strategies of provision of partial evidence for generalisations. The citing of particular examples, the use of diagrams to support general arguments, the contrast between deduction and induction and the process of searching for exceptions to either disprove a generalisation or impose a limitation on it will provide the backdrop to the presentation of mathematical proof.

  8.1 The role of induction

  The phrase ‘jumping to conclusions’ suggests the procedure of concluding that something is true of a large group of things on the basis of believing it is true of a smaller group of things and that such a procedure is flawed or unjustified. Before considering mathematical examples, let us reflect on what is involved in a few non-mathematical cases of our beliefs.

  ‘Night follows day’ is something we believe because of our past experience of days of living. The fact that we have not experienced future days to confirm that day will be followed by night does not undermine our belief. We are justified in our belief because our thinking conforms to the process of induction. Someone who did not share our belief would be thought of as rather peculiar, to say the least. Learning from science that our planet Earth rotates on its axis once every twenty-four hours explains how the position where we live is exposed to sunlight for part of the day and cut off from sunlight for part of the day. This scientific knowledge supports our belief that ‘night follows day’; it justifies our inductive step in saying something about days we have not lived on the basis of our experience of days we have lived through. In mathematical language, the illustration just considered amounts to making a statement beginning with ‘for all’ on the basis of a statement beginning with ‘for some’. Remind yourselves about the use of the universal quantifier, ∀, and the existential quantifier, ∃. However, a statement containing these quantifiers, with ‘x

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  The Induction Book

  • Steven H. Weintraub(Author)
  • 2017(Publication Date)
  • Dover Publications

    (Publisher)

  Chapter 1

  Introducing Induction

  In this chapter we introduce mathematical induction, first informally, and then formally. We then introduce complete induction and well-ordering, and derive the pigeonhole principle. Finally, we give a variety of examples of proofs using these methods.

  1.1 The Principle of Mathematical Induction

  Suppose we have a row of dominoes, with each domino labeled by a positive integer. Suppose also that the dominoes are arranged so that

  (a)If domino n falls, it knocks over domino n + 1.

  Now suppose that (b)The first domino falls. What will be the result? Clearly it will be that All the dominoes fall. This is nothing more or less than the principle of mathematical induction.

  Let us formalize this. Let D(n) be the statement that domino n falls. Condition (a) is the statement that

  If D(n) is true, then D(n + 1) is also true,

  while condition (b) is the statement that

  D(1) is true,

  and our conclusion is the statement that

  D(n) is true for every positive integer n.

  Once we view things in this way, we see there is nothing special about dominoes. By exactly the same logic, we have:

  Axiom 1.1.1 (The Principle of Mathematical Induction). Let P (n) be any proposition about the positive integer n. If

  (1)P (1) is true; and

  (2)If P (n) is true, then P (n + 1) is true;

  then

  P (n) is true for every positive integer n.

  In this statement, a “Proposition” is simply any true-false statement. Also, we have reversed the order of conditions (a) and (b) in our discussion of dominoes in stating conditions (1) and (2) in this statement to conform with usual mathematical practice. Condition (1) is often called the base case, while condition (2) is often called the inductive step

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  A Short Course in Discrete Mathematics

  • Edward A. Bender, S. Gill Williamson, S. Gill Williamson(Authors)
  • 2012(Publication Date)
  • Dover Publications

    (Publisher)

  Unit IS

  Induction, Sequences and Series

  Section 1: Induction

  Suppose A (n ) is an assertion that depends on n. We use induction to prove that A (n ) is true when we show that

  • it’s true for the smallest value of n and
  • if it’s true for everything less than n, then it’s true for n.

  In this section, we will review the idea of Proof by Induction and give some examples. Here is a formal statement of Proof by Induction:

  Theorem 1 (Induction ) Let A (m ) be an assertion, the nature of which is dependent on the integer m. Suppose that we have proved A (n 0 ) and the statement

  “If n > n 0 and A (k ) is true for all k such that n 0 ≤ k < n, then A (n ) is true.”

  Then A (m ) is true for all m ≥ n 0 .19

  Proof: We now prove the theorem. Suppose that A (n ) is false for some n ≥ n 0 . Let m be the least such n . We cannot have m = n 0 because one of our hypotheses is that A (n 0 ) is true. On the other hand, since m is as small as possible, A (k ) is true for n 0 ≤ k < m . By the inductive step, A (m ) is also true, a contradiction. Hence our assumption that A (n ) is false for some n is itself false; in other words, A (n ) is never false. This completes the proof.

  Definition 1 (Induction terminology ) “A (k ) is true for all k such that n 0 ≤ k < n ” is called the induction assumption or induction hypothesis and proving that this implies A (n ) is called the inductive step. A (n 0 ) is called the base case or simplest case.

  Example 1 (Every integer is a product of primes ) A positive integer n > 1 is called a prime if its only divisors are 1 and n . The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23. In another unit, we proved that every integer n > 1 is a product of primes. We now redo the proof, being careful with the induction.

  We adopt the terminology that a single prime p is a product of one prime, itself. We shall prove A (n ):

  “Every integer n ≥ 2 is a product of primes.”

  Our proof that A (n ) is true for all n ≥ 2 will be by induction. We start with n 0

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  An Introduction to the Analysis of Algorithms

  • Michael Soltys(Author)
  • 2018(Publication Date)
  • WSPC

    (Publisher)

  Chapter 9

  Mathematical Foundations

  And out of mathematical reasoning there arises the true philosophical question, the question that no amount of biology could ever solve: namely, what is mathematics about? What in the world are numbers, sets, and transfinite cardinals?

  Sir Roger Scruton [Scruton (2014)], pg. 6

  9.1Induction and Invariance

  9.1.1Induction

  Let ℕ = {0, 1, 2, …} be the set of natural numbers. Suppose that S is a subset of ℕ with the following two properties: first 0 ∈ S, and second, whenever n ∈ S, then n + 1 ∈ S as well. Then, invoking the Induction Principle (IP) we can conclude that S = ℕ.

  We shall use the IP with a more convenient notation; let P be a property of natural numbers, in other words, P is a unary relation such that P(i) is either true or false. The relation P may be identified with a set SP in the obvious way, i.e., i ∈ SP iff P(i) is true. For example, if P is the property of being prime, then P(2) and P(3) are true, but P(6) is false, and SP = {2, 3, 5, 7, 11, …}. Using this notation the IP may be stated as:

  for any (unary) relation P over ℕ. In practice, we use (9.1) as follows: first we prove that P(0) holds (this is the basis case). Then we show that ∀n(P(n) → P(n + 1)) (this is the induction step). Finally, using (9.1) and modus ponens, we conclude that ∀mP(m).

  As an example, let P be the assertion “the sum of the first i odd numbers equals i2 .” We follow the convention that the sum of an empty set of numbers is zero; thus P(0) holds as the set of the first zero odd numbers is an empty set. P(1) is true as 1 = 12 , and P(3) is also true as 1 + 3 + 5 = 9 = 32 . We want to show that in fact ∀mP(m) i.e., P is always true, and so SP = ℕ.

  Notice that SP = ℕ does not mean that all numbers are odd—an obviously false assertion. We are using the natural numbers to index odd numbers, i.e., o1 = 1, o2 = 3, o3 = 5, o4 = 7, …, and our induction is over this indexing (where oi is the i-th odd number, i.e., oi = 2i − 1). That is, we are proving that for all i ∈ ℕ, o1 + o2 + o3 + ··· + o

  i

  = i2 ; our assertion P(i) is precisely the statement “o1 + o2 + o3 + ··· + o

  i

  = i2

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Mathematical Analysis and Proof

  • David S G Stirling(Author)
  • 2009(Publication Date)
  • Woodhead Publishing

    (Publisher)

  can deal with any particular natural number, can’t it? A philosopher might turn this around and ask exactly what you mean by a natural number, which would lead us along an interesting path but not one we wish to follow here. Essentially the idea is that if you start with 1 and repeatedly add 1, giving 1, 1 + 1, 1 + 1 + 1, … , then the principle of mathematical induction is tantamount to saying that this sequence includes all the natural numbers. You can decide that is “obvious”, or you can decide to list it as an assumption. The main thing is that from now on we agree to accept the idea. Appealing to the principle of induction is essentially reminding the reader of this agreement.

  3.5 Examples of Induction

  Example 3.3 Prove that for all natural numbers n , 6n – 1 is a multiple of 5.

  Solution : We let P (n ) be “6n – 1 is a multiple of 5”.

  P (1) is “6 – 1 is a multiple of 5” which is obviously true.

  Suppose 6k – 1 is a multiple of 5, so that 6k – 1 = 5 m for some integer m . (Note that it matters that m is an integer!) Then

  6

  k + 1

  − 1 =

  6.6 k

  − 1 = 6

  5 m + 1

  − 1 = 30 m + 5 = 5

  6 m + 1

  which shows that 6

  k  + 1

  – 1 is a multiple of 5. We have proved P (k ) ⇒ P (k  + 1) (and that this holds for all natural numbers k ).

  Therefore, by induction, for all natural numbers n , 6n – 1 is a multiple of 5.

  In the two examples we have given we have established the result for all natural numbers. It may be that a result is true for all natural numbers n with n  ≥ N , in which case we prove the result is true for N and that, for each k  ≥ N , if the result is true for k then it is true for k  + 1. (In symbols, if P (n ) is a statement about n we prove that (i) P (N ) is true and (ii) for all natural numbers k  ≥ N , P (k ) ⇒ P (k  + 1), then we conclude that for all natural numbers n  ≥ N P (n ) is true.)

  Problem We can adopt the modified form of induction as another assumption, or we can deduce that the form of induction just stated is a consequence of the normal form. (Hint: define the statement Q (n ) to be P (n  + N –1).)

  There are, however, forms of induction which are more substantially different from the original. It is not difficult to see the need for this, in fact, for there are plenty of cases where proving P (k  + 1) directly from P (k ) would be awkward – for example if P (k ) is some statement about the factors of k , for there is no obvious relation between the factors of k  + 1 and those of k

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Real Analysis

  With Proof Strategies

  • Daniel W. Cunningham(Author)
  • 2021(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  1

  Proofs, Sets, Functions, and Induction

  In this introductory chapter, we review and identify the preliminaries that are essential for real analysis. In particular, we review inequalities, sets, functions, and proof by mathematical induction. These preliminary topics should be familiar, as should be the basic proof techniques that are used in mathematics. A review of logic and proof is presented in Appendix C on page 253. The most important proof strategies that are applied in this text can be found in the appendix starting on page 256.

  1.1 Proofs

  1.1.1 Important Sets in Mathematics

  The set concept is frequently used in mathematics. A set is a well-defined collection of objects. The items in such a collection are called the elements or members of the set. The symbol “∈” is used to indicate membership in a set. Thus, if A is a set, we write

  x ∈ A

  to declare that x is an element of A. Moreover, we write

  x ∉ A

  to assert that x is not an element of A. In mathematics, a set is typically a collection of mathematical objects, for example, numbers, functions, or other sets. Certain sets are frequently used in mathematics. The most commonly used ones are the sets of natural numbers, integers, and rational and real numbers. These sets will be denoted by the following symbols:

  1. ℕ = { 1 , 2 , 3 , … }

     is the set of natural numbers.
  2. ℤ = { … , -3 , -2 , -1 , 0 , 1 , 2 , 3 , … }

     is the set of integers.
  3. ℚ is the set of rational numbers. So,

     3 2

     ∈ ℚ

     .
  4. ℝ is the set of real numbers and so,

     π ∈ ℝ

     .

  In this text, we do not consider 0 to be a natural number.

  A set can sometimes be identified by enclosing a list of its elements by curly brackets; for example, the set

  A = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }

  consists of a few natural numbers. More often, one forms a set by enclosing a particular expression within curly brackets, where the expression identifies the elements of the set. To illustrate this method of identifying a set, we can form a set B of even natural numbers, using the above set A

  Sign up to read

  Learn more about book