Mathematics
Proof and Mathematical Induction
Proof and mathematical induction are fundamental concepts in mathematics. Proof involves demonstrating the truth of a statement using logical reasoning and previously established facts. Mathematical induction is a technique used to prove that a statement holds for all natural numbers by showing it holds for a base case and then demonstrating that if it holds for one case, it holds for the next.
Written by Perlego with AI-assistance
Related key terms
12 Key excerpts on "Proof and Mathematical Induction"
eBook - ePubElementary Point-Set Topology
A Transition to Advanced Mathematics
- Andre L. Yandl, Adam Bowers, Adam Bowers(Authors)
- 2016(Publication Date)
- Dover Publications(Publisher)
Chapter 1Mathematical Proofs and Sets1.1 Introduction to Elementary LogicIn everyday language, terms are defined using other terms, which inevitably leads to circular definitions. In mathematics, we begin with some terms that are undefined terms. Using these, we then introduce defined terms. Using undefined and defined terms, we make statements that are universally accepted as either true or false. Such statements are called propositions. We must stress the fact that a statement may be a proposition even though it may not be possible to verify whether it is true or false. For example, the statement “President John F. Kennedy drank exactly three glasses of wine on his twenty first birthday” is either true or false, hence a proposition; however, we may never be able to determine if it is true or if it is false.In a mathematical theory, propositions that are accepted as true without proof are called axioms or postulates. The truth of all other propositions must be proved using the axioms as a start and rules of logic that have been carefully stated. Propositions that have to be proved true are called theorems. Theorems that are stated and proved as preliminaries for the main theorem are called lemmas. Theorems that follow from the main theorem are called corollaries. In mathematics, once we accept the truth of the original assumptions (the axioms), we must accept the truth of all theorems that are derived from them. Research mathematicians state propositions they suspect to be true. These are called conjectures. When the truth of a conjecture has been demonstrated, the conjecture becomes a theorem. However, if someone succeeds in demonstrating one situation in which the conjecture is not true, then this situation is called a counterexample to the conjecture, and the conjecture is regarded as false.In this section, and the next two, we introduce the rules of logic and methods of proof that will be followed in proving theorems. Some propositions are simple in the sense that they do not contain other propositions as components. However, new propositions can be formed using simple propositions and logical connectives. It is convenient to define compound propositions by displaying their truth values for all possible truth values of their components in tables called truth tables. We will see later that if a compound proposition has n components, then there are 2n possible combinations of truth values of the components. For example, if a proposition has 3 components, then there are 8 possible combinations of truth values for these components. (See Example 1.1.5
eBook - ePub- Valsa Koshy, Ron Casey, Paul Ernest, Valsa Koshy, Ron Casey, Paul Ernest(Authors)
- 2014(Publication Date)
- Routledge(Publisher)
Chapter 8 Mathematical proofDOI: 10.4324/9780203984062-10In 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
eBook - ePubBecoming the Math Teacher You Wish You'd Had
Ideas and Strategies from Vibrant Classrooms
- Tracy Johnston Zager(Author)
- 2023(Publication Date)
- Routledge(Publisher)
11 Mathematicians ProveDOI: 10.4324/9781032680637-11A proof should be an epiphany from the gods, not a coded message from the Pentagon.—Paul Lockhart, A Mathematician’s LamentWhat Is Proof?
Proof has multiple meanings to mathematicians, and those meanings have evolved over time. The most formal usages emphasize objective, airtight, written arguments in which each step follows logically from the one before it, yielding deductive certainty. While modern mathematicians certainly strive for flawless arguments, many have pushed back against traditional, formal definitions, arguing they are reductive and do not convey the essence, experience, or reality of what mathematicians do. For example, Ian Stewart wrote:After wondering about a richer, fuller description, Stewart decided on this one:A proof, they tell us, is a finite sequence of logical deductions that begins with either axioms or previously proved results and leads to a conclusion, known as a theorem ... This definition of “proof” is all very well, but it is rather like defining a symphony as “a sequence of notes of varying pitch and duration, beginning with the first note and ending with the last.” Something is missing. Moreover, hardly anybody ever writes a proof the way the logic books describe. (2006, 89)Oxford mathematician Marcus du Sautoy explained proofs using a different analogy, but with a similarly enticing description of the audience’s experience:A proof is a story. It is a story told by mathematicians to mathematicians, expressed in their common language ... If a proof is a story, then a memorable proof must tell a ripping yarn ... When I can really feel the power of a mathematical storyline, something happens in my mind that I can never forget. (2006, 89-94)A successful proof is like a set of signposts that allow all subsequent mathematicians to make the same journey. Readers of the proof will experience the same exciting realization as its author that this path allows them to reach the distant peak. Very often a proof will not seek to dot every i and cross every t, just as a story does not present every detail of a character’s life. It is a description of the journey and not necessarily the re-enactment of every step. The arguments that mathematicians provide as proofs are designed to create a rush in the mind of the reader. (2015)
- Dieter Probst, Peter Schuster, Dieter Probst, Peter Schuster(Authors)
- 2016(Publication Date)
- De Gruyter(Publisher)
φ and all members of it either belong to the set of presumed axioms or are consequences of previous members of the sequence according to one of the accepted rules of inference. Observe that this concept of a formal proof has a syntactic character and does not refer to any semantical notions such as meaning or interpretation.As a result of the described development one has to deal nowadays in mathematics with at least two concepts of a proof: the formal one, used mainly by logicians and specialists in metamathematics in the foundational studies aswell as by computer scientists (cf. modern theorem provers) and on the other hand the “ normal” , “ usual” concept of a proof used in mathematical research practice. What are the relations between them? Is the metamathematical concept a precise explication of the “ everyday” concept? Do they play similar roles in mathematics or not? To what extent does the concept of a formal proof reflect the main features and the nature of an informal proof used by mathematicians in their researches?3 Informal proofs and their role
Mathematics was and is developed in an informal way using intuition and heuristic reasonings – it is still developed in fact in the spirit of Euclid (or sometimes of Archimedes) in a quasi-axiomatic way. Moreover, informal reasonings appear not only in the context of discovery but also in the context of justification. Any correct methods are allowed to justify statements. But what does it mean “ correct” ? In the research practice this was and is decided by the community of mathematicians. Consequently the criteria of being correct have been changing in the history and in the process of developing mathematics. The concept of proof was and is in fact not an absolute notion but it was and is culturally and sociologically dependent and motivated, it had and has a cultural and sociological components. The main aim of a mathematician is always to convince the audience that the given result is justified, correct and true (the latter concept being used in an intuitive and vague way) and not to answer the question whether it can be deduced from stated axioms. In the research practice a proof is in fact an argumentation that should indicate the correctness of a claimed thesis –
eBook - ePub- 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 thatIf D(n) is true, then D(n + 1) is also true,while condition (b) is the statement thatD(1) is true,and our conclusion is the statement thatD(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;thenP (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
eBook - ePub- 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) LetP ( j )be the assertion “Either n is prime or n is the product of primes.”(b) ThenP ( 2 )is plainly true since 2 is the first prime.(c) Now assume thatP ( ℓ )is true for2 ≤ ℓ ≤ jand considerP ( j + 1 ). Ifj + 1is prime, then we are done. Ifj + 1is not prime, thenj + 1factors asj + 1 = k · m, where k, m are integers less thanj + 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). Thusj + 1factors 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. Son =. In this case, it is clear that n is a multiple of 9.= 27( 3 j )3j 3= 9 · ( 3j 3)2. The integer n is the cube of one less than a multiple of 3. Hencen =. So we see that n= 27( 3 j − 1 )3j 3− 27j 2+ 9 j − 1 = 9 ( 3j 3− 3j 2+ j ) − 1
eBook - ePubPhilosophy of Mathematics
Classic and Contemporary Studies
- Ahmet Cevik(Author)
- 2021(Publication Date)
- Chapman and Hall/CRC(Publisher)
modus tollens. Proposition (vi) states the transitivity property of propositional logic. For this, consider the statements “If I put ice in the glass, the water will spill over” and “if the water spills over, then the table gets wet”. From these two statements, we can conclude that “If I put ice in the glass, the table will get wet”. The explanation of the rest of the tautologies is left to the reader as an exercise.Now we introduce the methods of proof. Roughly defined, a logical/ mathematical proof consists of a finite sequence of propositions. When proving any statement, we have to start our argument with a statement and so we need initial assumptions. These assumptions are called axioms. According to Oxford English Dictionary, the word axiom refers to a statement or proposition which is regarded as being established, accepted, or self-evidently true. If we can deduce in finitely many steps, using the rules of inference, the desired statement from a given collection of axioms, then this sequence of propositions constitutes a proof of the desired statement. We give the formal definition as follows.Definition 2.2 Let S be a collection of propositions. If for any sequence of propositionsin S,B 1, … ,B n(is a tautology, then we say that SprovesA. In this case, the sequenceB 1∧ … ∧B n) → Ais a proof of A from S.B 1, … ,B nAlthough mathematical proofs in daily practice are given in natural language, they all, in principle, can be seen formally as a sequence of propositions. Proving a theorem formally can be very tedious. Mathematicians do not prove theorems in the formal manner as formal proofs are in most cases used by computer programmes or formal axiomatic systems for verification and automation purposes. Fortunately, we do not need to worry about formal proofs in this book.2.2.1 Direct proof
eBook - ePub- Alan H. Schoenfeld, Alan H. Sloane, Alan H. Schoenfeld, Alan H. Sloane(Authors)
- 2016(Publication Date)
- Routledge(Publisher)
7The Role of Proof in Problem Solving
Susanna S. Epp DePaul UniversityIt is widely accepted that the kind of thinking done by mathematicians in their own work is distinctly different from the elegant deductive reasoning found in mathematics texts. In this era of public candor people freely admit things they might once have seen as compromising their dignity. When discussing the process of mathematical discovery, mathematicians now openly acknowledge making illogical leaps in arguments, wandering down blind alleys or around in circles and formulating guesses based on analogy or on examples that are hidden in the later, formalized exposition of their work. Enthusiasm for this more human view of mathematical thinking has led some to relegate proof to the position of an ex post facto , often unintuitive, somewhat pedantic justification for statements already known to be true to the intuition, a dull checking of final details. The view that intuitive understanding is separate from and precedes proof is sometimes given as a reason for presenting mathematics informally during the first two college years, leaving proof to junior and senior courses.While I wholeheartedly agree that intuition is of major importance in mathematical discovery, I believe it is profoundly misleading to suggest that proof is mere formalism. Indeed, I believe that deductive reasoning occupies such a central position in mathematical problem solving that mathematicians are often unaware they are using it, taking their chains of inferences as much for granted as their breathing. This is not to imply that the discovery process is a straightforward linear progression from problem formulation to solution or that mathematicians do not become confused and sometimes make mistakes. I certainly do. But my experience working closely and interactively with students over many years has convinced me that the “illogical” thoughts of research mathematicians are different at least in number if not always in kind from those of most of their students. I propose that learning ways to help such students become better deductive reasoners deserves the attention of mathematics teachers and researchers in mathematics education, at least as much as do other aspects of mathematical thinking.
eBook - ePub- Michael Detlefsen(Author)
- 2005(Publication Date)
- Routledge(Publisher)
Section III are not in place—there is rather more phenomenological work yet to be done here. The major block is that philosophers have not yet secured a sufficiently powerful and subtle sense of the understanding. Mainly I will consider some very simple (but nevertheless not easy) examples, hoping that they might prove suggestive to the reader. But let me be just a bit clearer about what the thesis is.Given a mathematical proof. Typically this proof will depend on theorems or lemmas that have been proven elsewhere. The thesis being considered here in Section III is that, typically, if we trace backwards we will find that, in the end, there have been no unproven assumptions. I actually mean by this something which might look weaker, but, if you think about it, is not— there is nothing in the proof that needs to be proved. Of course what I have in mind is that there are no postulates underlying mathematical proof. Mathematical demonstration is, typically, not founded on unproven assumptions. Of course, it is sometimes of interest to a mathematician to derive consequences of, say, the postulates of mathematical ring or field theory (or whatever). So one can consider, perhaps, that here, at least, the mathematician is proving something on the basis of postulates. But is this so? It might be thought that postulates framing natural numbers or sets or calculable functions might somehow be evident on the basis of certain semi-mental entities usually called “concepts.” And this is not implausible. But the concepts of mathematical groups, rings, fields, etc., emerge from the isolation of significant mathematical structures and really cannot be thought of as somehow available in advance through concepts giving a basis on which axioms characterizing those structures would be evident. But what is important from our present point of view is that the proof that such and such follows from, say, the field axioms is not the same as a formal derivation from the axioms (gapless formal-logical derivations are extremely rare and usually far too long) but, rather, a proof that either there is a formal derivation or else a proof that the theorem follows from the axioms, as in Hilbert’s Foundations of Geometry. Such proofs will typically not contain unproven assumptions— assumptions in need of proof, or so I claim. Even in the case that what is at issue is a formallogical system, a given formallogical derivation will not count as a proof of its own existence; rather, that it is a correct formallogical derivation is something that must be demonstrated, and certainly not by a formal-logical derivation! By what then? by a series of observations that lets us see/find that it is a formal-logical derivation of a sentence from the axioms according to given rules of inference. Where there is a formalaxiomatic system, the genuinely mathematical theorems and proofs are not formal derivations from the axioms (generally, mathematicians do not want to see such things!) but rather proofs that there exists such and such a formal derivation of such and such from such and such axioms according to such and such rules. Far from formal derivations being adequate to represent proofs, they themselves as it were need proofs—need to be proved to exist!8
eBook - ePubReal Analysis
With Proof Strategies
- Daniel W. Cunningham(Author)
- 2021(Publication Date)
- Chapman and Hall/CRC(Publisher)
1Proofs, 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 writex ∈ Ato declare that x is an element of A. Moreover, we writex ∉ Ato 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 , 2 , 3 , … }is the set of natural numbers.
- ℤ = { … , -3 , -2 , -1 , 0 , 1 , 2 , 3 , … }is the set of integers.
- ℚ is the set of rational numbers. So,.3 2∈ ℚ
- ℝ 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 setA = { 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
eBook - ePub- sarah-marie belcastro(Author)
- 2018(Publication Date)
- Chapman and Hall/CRC(Publisher)
Induction
4.1 Introduction and SummaryThis 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.
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.4.2 InductionExample 2.1 Do you believe that if, thenn > 0? Let’s check to see whether this statement holds for a few values of n .2 n> nWhen, we see thatn = 1, and2 1= 2.2 > 1When, we see thatn = 2, and2 2= 4.4 > 2When, we see thatn = 423943, 348, 126, 619, 871, 175, 004, 951, 664, 972, 849, 610, 340, 958, 208 and that is certainly greater than 423.2 423= 14 , 134 , 776 , 518 , 227 , 074 , 636 , 666 , 380 , 005 ,Yes, the statement if, thenn > 0seems to be true. We have checked it for small values of n , which are known as base cases .2 n> nTo prove the statement, we will first suppose that when n is less than or equal to some indeterminate k (but greater than 0),. This is called the inductive hypothesis .2 n> nIf we can show that this assumption allows us to prove that, then we will have proved that2> k + 1k + 1for all2 n> n. This process is known as the inductive stepn > 0
- S.G. Shanker(Author)
- 2013(Publication Date)
- Routledge(Publisher)
To be sure, this picture suggests that the distinction we are searching for between mathematical and scientific ‘tests’ lies in the logical demarcation between deductive and inductive inference; but it none the less raises serious questions in its wake. The first is simply: is it warranted? Or to put this another way: why must every proof be part of a deductive system? There might well be strong reasons for such a condition: the question is whether this is a theme which can merely be assumed? Forgoing until Chapter 8 any discussion of the hazards involved in what would amount to the ‘postulational method’ if we were to abandon this important premise, the objection which surfaces here is that such an argument does little to clarify the logical character of proof: the question of how deductive inference renders mathematical truth ‘absolutely certain’, and in what the distinguishing feature of a successful proof consists. It may seem tempting to dismiss this as a self-evident matter, but it is important to bear in mind that many philosophers who share Kline’s explanation — and indeed Kline himself — see no conflict between this premise and the conclusion that ‘proof is subject to a constant process of criticism and revalidation. Errors, ambiguities, and misunderstandings are cleared up by constant exposure. Proof is respectability. Proof is the seal of authority.’ 16 But how there can be any room for doubt as far as the status of a proof is concerned? Is this simply a case of human fallibility, and if so, how can we ever be absolutely certain that a proof can be accepted as such? A ‘seal of authority’ which can always be overruled is at best a token device, forever waiting to be discarded. Thus Wittgenstein stressed that perhaps our main objective here is to clarify why it is that ‘to say, e.g.: we must be able to be certain, it must hold as certain for us, that we have not overlooked a sign in the course of the proof
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.
