Mathematics
Proof by Induction
Proof by induction is a mathematical technique used to prove that a statement holds for all natural numbers. It involves two steps: establishing a base case and proving that if the statement holds for a particular number, it also holds for the next number. This method is commonly used to prove properties of sequences, series, and other mathematical structures.
Written by Perlego with AI-assistance
Related key terms
1 of 5
10 Key excerpts on "Proof by Induction"
eBook - PDF- Owen D. Byer, Deirdre L. Smeltzer, Kenneth L. Wantz(Authors)
- 2018(Publication Date)
- American Mathematical Society(Publisher)
6 Induction Induction makes you feel guilty for getting something out of nothing, and it is artificial, but it is one of the greatest ideas of civilization. —Herbert Wilf (1931–2012) Recall that in Example 60 of Chapter 4, we encountered a sequence (namely, 1, 2, 4, 8, 16, … ) that could be obtained by letting ? ? denote the number of regions created when ? points are placed on a circle and connected, with no three segments meeting at a point. Although the first five terms can be expressed as powers of 2 ( ? 1 = 1 = 2 0 , ? 2 = 2 = 2 1 , ? 3 = 4 = 2 2 , ? 4 = 8 = 2 3 , and ? 5 = 16 = 2 4 ), the pattern does not hold beyond ? 5 , since ? 6 = 31 . On the other hand, we saw in Chapter 3 that a sequence with the same first five terms can be created by letting ? ? represent the number of subsets of a set with ? elements; in that case, however, ? ? = 2 ? for all positive integer values of ? . This raises the question of how one verifies that a statement about integers holds for infinitely many consecutive positive integers. Proof by mathematical induction is a technique that is frequently used for establishing that a conjecture is true for all pos-itive integers beyond a particular starting value. We will see that this proof technique involves two steps: first, showing that the statement is true for a smallest value; sec-ond, demonstrating that if the statement holds for a given positive integer, it must also hold for the next integer. Before looking at the Principle of Mathematical Induction in detail, though, we will examine the role of induction more generally in science and mathematics. 6.1 Inductive and Deductive Thinking Within the physical sciences (biology, chemistry, physics, astronomy), inductive rea-soning is used on an everyday basis to derive a general conclusion after examining many specific cases.
- Tony Gardiner, Alexandre Borovik(Authors)
- 2019(Publication Date)
- Open Book Publishers(Publisher)
This idea is what lies behind “ proof by mathematical induction”, where we prove that some assertion P p n q holds for all n ě 1 – so demonstrating infinitely many separate statements at a single blow. The validity of this method of proof depends on a fundamental property of the positive integers , or of the counting sequence “1, 2, 3, 4, 5, . . . ”, namely: The Principle of Mathematical Induction : If a subset S of the positive integers • contains the integer “1”, and has the property that • whenever an integer k is in the set S , then the next integer k ` 1 is always in S too, then S contains all positive integers. 286 Infinity: recursion, induction, infinite descent 6.1. Proof by mathematical induction I When students first meet “Proof by Induction”, it is often explained in a way that leaves them feeling distinctly uneasy, because it appears to break the fundamental taboo: never assume what you are trying to prove. This tends to leave the beginner in the position described by d’Alembert’s quote at the start of the chapter: they may “press on” in the hope that “understanding will follow”, but a doubt often remains. So we encourage readers who have already met Proof by Induction to take a step back, and to try to understand afresh how it really works. This may require you to study the solutions (Section 6.10), and to be prepared to learn to write out proofs more carefully than, and rather differently from, what you are used to. When we wish to prove a general result which involves a parameter n , where n can be any positive integer , we are really trying to prove infinitely many results all at once . If we tried to prove such a collection of results in turn, “one at a time”, not only would we never finish, we would scarcely get started (since completing the first million, or billion, cases leaves just as much undone as at the start).
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Orange Apple(Publisher)
________________________ WORLD TECHNOLOGIES ________________________ Chapter- 5 Mathematical Proof Methods Mathematical induction An informal description of mathematical induction can be illustrated by reference to the sequential effect of falling dominoes. Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers (non-negative integers). It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one. ________________________ WORLD TECHNOLOGIES ________________________ The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction should not be misconstrued as a form of inductive reasoning, which is considered non-rigorous in mathematics. In fact, mathematical induction is a form of rigorous deductive reasoning. History In 370 BC, Plato's Parmenides may have contained an early example of an implicit inductive proof. The earliest implicit traces of mathematical induction can be found in Euclid's proof that the number of primes is infinite and in Bhaskara's cyclic method. An opposite iterated technique, counting down rather than up, is found in the Sorites paradox, where one argued that if 1,000,000 grains of sand formed a heap, and removing one grain from a heap left it a heap, then a single grain of sand (or even no grains) forms a heap. An implicit proof by mathematical induction for arithmetic sequences was introduced in the al-Fakhri written by al-Karaji around 1000 AD, who used it to prove the binomial theorem and properties of Pascal's triangle.
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Library Press(Publisher)
________________________ WORLD TECHNOLOGIES ________________________ Chapter 8 Mathematical Proof Methods Mathematical induction An informal description of mathematical induction can be illustrated by reference to the sequential effect of falling dominoes. Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers (non-negative integers). It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one. ________________________ WORLD TECHNOLOGIES ________________________ The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction should not be misconstrued as a form of inductive reasoning, which is considered non-rigorous in mathematics. In fact, mathematical induction is a form of rigorous deductive reasoning. History In 370 BC, Plato's Parmenides may have contained an early example of an implicit inductive proof. The earliest implicit traces of mathematical induction can be found in Euclid's proof that the number of primes is infinite and in Bhaskara's cyclic method. An opposite iterated technique, counting down rather than up, is found in the Sorites paradox, where one argued that if 1,000,000 grains of sand formed a heap, and removing one grain from a heap left it a heap, then a single grain of sand (or even no grains) forms a heap. An implicit proof by mathematical induction for arithmetic sequences was introduced in the al-Fakhri written by al-Karaji around 1000 AD, who used it to prove the binomial theorem and properties of Pascal's triangle.
eBook - PDFSets, Groups, and Mappings
An Introduction to Abstract Mathematics
- Andrew D. Hwang(Author)
- 2019(Publication Date)
- American Mathematical Society(Publisher)
The technique of mathematical induction allows us to resolve such questions with a finite proof. The idea is to break the statement “For every natural number ? , the sum of the first ? odd positive integers is equal to ? 2 ” into an infinite list of statements. Here, 71 72 5. Induction and Recursion we take ?(?) 1 + 3 + 5 + ⋯ + (2? − 1) = ? 2 . To say ?(100) is true, for example, means the sum of the first hundred odd integers is equal to 10, 000 = 100 2 . (An “empty” sum is 0 , so ?(0) reads 0 = 0 .) The original statement may be rephrased “For every natural number ? , ?(?) is true.” This single statement ? encapsulates the infinite list of statements: ?(0) is true, ?(1) is true, ?(2) is true, etc. In order to establish the truth of ? , it suffices to prove ?(0) is true (the base case ), and to prove ?(?) implies ?(?+1) for every ? in 𝐍 (the inductive step ). The legal contract is as follows. Theorem 5.1 (Principle of Mathematical Induction) . Let ?(?) , with ? = 0 , 1 , 2 , ..., be a family of statements. If ?(0) is true, and if ?(?) implies ?(? + 1) for each ? ≥ 0 , then ?(?) is true for all ? ≥ 0 . Remark 5.2. It is sometimes convenient to take an index ? 0 > 0 for the base case. In this event, one must prove ?(? 0 ) is true, and establish that ?(?) implies ?(? + 1) for ? ≥ ? 0 . The conclusion is, ?(?) is true for ? ≥ ? 0 . To see intuitively why the base case and inductive step are enough, consider the consequences of “ ?(0) is true, and ?(?) implies ?(? + 1) for all ? ≥ 0 ”. Taking ? = 0 , the inductive step says ?(0) implies ?(1) . But ?(0) is true by the base case, so ?(1) is also true by the inductive step. Now repeat the argument, taking ? = 1 . By the inductive step, ?(1) implies ?(2) , but ?(1) is true , so ?(2) is also true. Continuing in this fashion, ?(3) is true, and ?(4) , and so forth, ad infinitum . The chain of deduction may be represented as a sequence of arrows: ?(0) ⏟ Base case ⟹ ?(1) ⟹ ?(2) ⟹ ?(3) ⟹ … ⟹ ?(?) ⟹ ?(? + 1) ⟹ … .
eBook - PDF- John Taylor, Rowan Garnier(Authors)
- 2016(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 8 Mathematical Induction 8.1 Introduction In this chapter we consider in some detail one particular method of proof, called proof by mathematical induction, which may be used to prove state-ments about the natural numbers or positive integers. In other words, the method will apply to the proofs of propositions of the form ∀ n • P ( n ) where the universe for n is the set of natural numbers N or the set of positive inte-gers Z + . The following are examples of the kinds of results that we may prove using the method of mathematical induction. 1. The sum of the first n positive integers is 1 2 n ( n + 1); symbolically, for all n ∈ Z + , 1 + 2 + 3 + · · · + n = 1 2 n ( n + 1) . 2. For every n ∈ N , the expression 5 n + 3 is divisible by 4. 3. For all finite sets A , if A has cardinality n , then its power set P ( A ) has cardinality 2 n . The first of these is clearly of the form ∀ n ∈ Z + • P ( n ) and the second is of the form ∀ n ∈ N • P ( n ). However, the third statement is not obviously of one of these two forms. Note that, to say that a set A is finite means it has cardinality | A | = n where n is some natural number. This means we could rephrase the third statement as ‘for all n ∈ N , if A is a set with cardinality | A | = n , then its power set has cardinality | P ( A ) | = 2 n ’ and this is of the form ∀ n ∈ N • P ( n ). This is not unusual. Sometimes a statement is not obviously one about N or Z + , but is more naturally about some other mathematical object such as a set, function, group, graph or whatever. But, by rethinking the statement, it may be rephrased to be one about say the positive integers; the advantage of this is that it brings into play the possibility of using the powerful method of mathematical induction. Despite its name, any proof by mathematical induction uses deductive rea-soning, which is the basis of all mathematical proofs; it does not rely on the kind of inductive reasoning described in section 1.3. 303
eBook - PDFExploring Mathematics
An Engaging Introduction to Proof
- John Meier, Derek Smith(Authors)
- 2017(Publication Date)
- Cambridge University Press(Publisher)
Which of these might have nice proofs by mathematical induction? For those that do, would you use simple or strong induction, and how many base cases would you need? 44 2. Discovering and Presenting Mathematics Exercise 2.32 Use mathematical induction to prove that Bernoulli’s Inequality, (1 + x) n ≥ 1 + nx, holds for all x ≥ −1 and all n ∈ N. Is your proof simple or strong, and how many base cases are needed? R EMARK 2.17. Project 11.2 discusses the two-player game of Chomp, whose analysis leads to an interesting induction argument. It also provides a good example of ‘doing’ mathematics as outlined in Section 2.8. We recommend flipping to the project now, just to do a bit of exploration of the ideas there and to have a first look at the inductive proof outlined in Exercise 11.12. The project right after it, Project 11.3 on the arithmetic– geometric mean inequality, also involves the use of induction, this time in a less standard format. It is worth your time looking at the outline of the argument developed there, just to see another way in which a Proof by Induction can be structured. 2.7. Ubiquitous Terminology Mathematics is written in a concise format that takes a bit of getting used to. In fact, students often struggle because they believe they should just be able to “read” mathe- matics as opposed to “work through” a mathematics text; but a crucial part of your job as a reader of mathematics is to work to fill in details that were either skipped or con- densed as the author wrote up her ideas. More on the process of “doing” mathematics is discussed in the next section. The aim of this section is simply to help you understand how mathematics is usually presented. A mathematical statement is a sentence that is either true or false; it is clear and unambiguous. “Every Fibonacci number is even” is a mathematical statement while “Sure looks like rain” is not.
eBook - PDF- Charles Roberts(Author)
- 2014(Publication Date)
- Chapman and Hall/CRC(Publisher)
That is, if (1) is true, it follows that (2) is true and therefore n + 1 ∈ S . Since the hypotheses (i) and (ii) of the Fundamental Theorem of Mathe-matical Induction are true, the conclusion S = N is true. Consequently, the statement P ( n ) is true for all n ∈ N —that is, 1 + 2 + · · · + n = n ( n + 1) 2 for all n ∈ N . Instead of defining S to be the set of all natural numbers n such that the statement P ( n ) is true, proofs by mathematical induction are usually presented in the following logically equivalent, but less formal, form. Mathematical Induction 233 The Principle of Mathematical Induction For each n ∈ N , let P ( n ) be a statement which is either true or false but not both. If (i) P (1) is true and if (ii) for all n ∈ N , P ( n ) is true ⇒ P ( n + 1) is true, then the statement P ( n ) is true for all n ∈ N . Step (i) above is called the basis step or initial step and step (ii) is called the inductive step . The hypothesis of the inductive step, “ P ( n ) is true,” is known as the inductive hypothesis . Imagine that each statement P ( n ) is a domino in a chain of dominoes. In the induction step, step (ii) of mathematical induction, we are proving that if one domino in the chain, P ( n ), is knocked over, it will knock over the next domino in the chain, P ( n + 1). When dominoes are set up so that when one domino falls, the next domino in the chain will fall, none will fall unless the first domino, P (1), falls. This is why we need the basis step in a proof by mathematical induction. The basis step, step (i), ensures that the first domino will fall, while the inductive step, step (ii), ensures that all dominoes after the first domino will fall. The next example shows how to use the Principle of Mathematical Induction to prove for all n ∈ N that the statement P ( n ) is true. Example 6.1.2 Prove for all n ∈ N that 1 2 +3 2 + · · · +(2 n -1) 2 = n (4 n 2 -1) 3 . Proof: Let P ( n ) be the statement (1) 1 2 + 3 2 + · · · + (2 n -1) 2 = n (4 n 2 -1) 3 .
eBook - PDFDiscrete Mathematics
Proof Techniques and Mathematical Structures
- R C Penner(Author)
- 1999(Publication Date)
- WSPC(Publisher)
A famous anecdote about Example A.5.2 is the story that Carl Friedrich Gauss as a boy was given the tedious assignment of adding all the numbers from 1 to 100. His teacher expected this to be a grueling exercise in addition, but Gauss quickly derived the equality above and gave the correct answer. As the reader can surmise, the two examples above are typical of a whole class of important computational problems involving finite sums, where the basis step is easily checked to be an equality of numbers, and the induction step amounts to some arithmetic manipulation. This routine proof technique is fundamental and must be mastered by the reader. For another example of a Proof by Induction in this mold, we have ■ Example A.5.3 For any natural number n and any number q ^ 1, we have E L i ^ ^ -i V C g -i ) . A sum of the form $Z£ =1 q k ~ x is called a geometric series, and this putative (i.e., alleged or supposedly true) formula for a geometric series is absolutely basic. Proof For the basis step, we find (n+l)(n + 2) 2 A.5 Proofs by Induction for Natural Numbers 17 and for the induction, compute n -l ,n-l A:=l Jk=l n n-l _ i = 2 r i + ? n -1 9 -1 q n-l _ l + q n _ g n -l 9 -1 _ 9 -l where the second equality follows from the inductive hypothesis. q.e.d. Observe that in the examples of induction above, we proved a stated numer-ical equality while in practice, one often does not know the answer in advance in this way. In fact, given a finite sum, one can enumerate (that is, list) the first several values of the sum and on the basis of this data simply guess an expression for the general term. Of course, such inspired guessing is problematic, but having thereby guessed the answer, one can then prove that the guess is correct or discover that it is not correct using a Proof by Induction. ■ Example A.5.4 Consider the sum s n = ^2™ =1 (2i — 1) for n > 1. Listing the first several values, we find si = 1, s 2 = 4, 53 = 9, 54 = 16 and are led to guess that in fact s n = n 2 .
eBook - PDF- Scott A. Taylor(Author)
- 2023(Publication Date)
- American Mathematical Society(Publisher)
. The same four terms repeat forever. ♦ In the previous examples, we say that each sequence was defined recursively. First of all, observe that we begin with a base case where we define the initial term or terms of the sequence. We then assume an inductive hypothesis: The (finite) se- quence 1 , ... , has been defined. Next we define +1 in terms of the previous val- ues 1 , ... , . For an arbitrary ∈ ℕ, we can then compute by computing all the previous terms of the sequence. 11 GNU is a computer operating system like Windows, MacOS, or Unix. The Free Software Foundation, makers of GNU, is dedicated to free software as an important component of a free and open society. Slogan is available under the Creative Commons Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) license. 9.4. Constructing sequences recursively 271 Here is the general method: Defining a sequence recursively To define: A sequence ( ) in a nonempty set so that 1 ∈ and so that ( ) has a property . Structure of Definition and Proof: We define ( ) recursively. Choose some 1 ∈ . Assume that we have defined ∈ for all ∈ {1, ... , } in such a way that we haven’t yet contradicted the possiblity of the final sequence having property . We now define +1 . ⟨ Define +1 ∈ in terms of 1 , ... , . ⟩ We have recursively defined a sequence ( ) in . ⟨ Verify that satisfies . ⟩ □ The astute reader will observe that induction is a method of proving (certain kinds of) theorems to be true, but here we have used its structure to make a definition. Some- thing called the recursion principle ensures that this is mathematically valid. We defer to [75, Chapter 3] for a statement and proof. Here is an example of how to use recursive definitions in a proof. Note the use of induction. A version of this theorem was first remarked by Galileo (see [49, pp 40–41].) The theorem is illustrated in Figure 9.8.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
