Timeline for Does a proof by induction have to explicitly refer to the principle of mathematical induction?
Current License: CC BY-SA 4.0
44 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 28, 2023 at 13:04 | answer | added | Louis | timeline score: 3 | |
| Nov 26, 2023 at 22:30 | comment | added | Will Orrick | @FerencBeleznay I apologize for putting words in your mouth. I agree with much of what you say, especially regarding interactions with students. I suspect there are some philosophical differences between us having to do with shades of meaning of words like "know", "prove", and "understand", and with the relative emphases placed on intuition and formalism, in particular as they relate to teaching. | |
| Nov 26, 2023 at 14:12 | comment | added | Ferenc Beleznay | ... In my comment I do say that the procedural part is the formal application of the method of induction. What you are describing is a student who discovers an important intuitive property of natural numbers (namely that they can build up the general rule this way), which they take for granted. | |
| Nov 26, 2023 at 14:03 | comment | added | Ferenc Beleznay | @WillOrrick You are really reading things in my comment which is not there. It is a fact that there are students who continuously ask for rules. I meet them all the time. I am not saying this as a judgement, just stating it. I am perfectly OK with this. When I ask "how would you prove it", I am not asking for a proof, I am giving an opportunity for them to think deeper. If they don't want to do it, that is fine. What you are describing is the approach of a student, who is interested beyond procedures. This is not in contradiction to what I was saying. On the contrary. ... | |
| Nov 26, 2023 at 6:50 | comment | added | Will Orrick | ...following rules in a way that a student who has the--historically contingent--piece of knowledge that arithmetic has been axiomatized in a particular way isn't? Really what I was reacting to with these comments was David Roberts' surprising assertion that there is no pre-formal understanding of induction. | |
| Nov 26, 2023 at 6:50 | comment | added | Will Orrick | @FerencBeleznay I'm sure it's not what you intended, but I find the description, "interested in mathematics in a way that is more than a procedural application of rules", to be dismissive of the mathematical insight of ordinary people. What if, rather than confessing that they have no proof, they attempt an explanation? What if, perhaps of their own initiative, perhaps with some prodding, the student comes up with the idea that 1+1+1 is the number following 1+1 and that 1+1+1+1 is the number following 1+1+1 and that they can build up the general rule in that way? How are they procedurally... | |
| Nov 26, 2023 at 5:29 | comment | added | Ferenc Beleznay | @WillOrrick For me, it is fine if a student tells that it is clear that $\sum_{i=1}^n 1=n$, and I would not instruct them that it is not clear. However, from a student who is interested in mathematics in a way that is more than a procedural application of rules, I would expect to at least think it over if I ask "How would you prove it?" I would not expect a proof (that is the procedural part, if they know for example induction). I would expect a realization that there are things we accept without proof. | |
| Nov 25, 2023 at 18:52 | answer | added | user52817 | timeline score: 3 | |
| Nov 25, 2023 at 14:38 | comment | added | Will Orrick | @DavidRoberts I thought I could leave this alone, but I'm finding I cannot. If a student ignorant of induction tells us it's clear that $\sum_{i=1}^n1=n$, are we to instruct them that it's not clear and that if they believe it to be clear they must be confused about something? If yes, what educational purpose is being served by doing so? I can see a student with a thirst to know mathematics feeling chastened and going off to learn what they need to know in order to grasp the issue at hand, which for some might take a long time. But I can also see a student being turned off of mathematics. | |
| Nov 25, 2023 at 14:01 | comment | added | user12357 | @WillOrrick "Maybe because it seems circular" — that is certainly one of the stumbling blocks, in my experience. Students yet unused to proofs lose sight of quantifiers. The student has to prove $P(n)$. So they assume $P(n)$ or $P(k)$ according to the induction step formula. Now they have to prove $P(k+1)$. Since they know $P(k)$ is true, why not plug $k+1$ into $P(k)$ and get $P(k+1)$ immediately, just as they've always been allowed to do in algebra class? [That's the student's question; I know the answer.] | |
| Nov 24, 2023 at 15:42 | comment | added | Robbie Goodwin | Thanks Ferenc and doesn't it seem that as long as there are enough doubts out there for queries such as Dan and Stef's to case so much comment in a place like this, some people would be helped and no-one hindered by always using 'by induction', with or without a leading 'Hence'? | |
| Nov 24, 2023 at 6:06 | comment | added | David Roberts | @WillOrrick I don't claim it consciously bothers them. But the fact we cannot give an argument/proof of how induction works/why it's justified means suddenly students are faced with a fact that cannot be treated in the same way as everything they'd seen up to that point (well, more or less: even addition and multiplication are informally justified by recourse to manipulables and counting etc). | |
| Nov 24, 2023 at 5:17 | comment | added | Will Orrick | @DavidRoberts For a "pre-formal" argument would you accept a metamathematical argument? You have an algorithm for constructing (increasingly long) valid proofs of $P(2)$, $P(3)$, and so on. So for any $n$ one cares to ask about, there's a valid proof for that $n$, which you know how to construct. This seems convincing to me. The subtle point is that reasoning within the system does't allow you to go from this algorithm for constructing valid proofs for each $n$ to the universally quantified statement $\forall n P(n)$. But I don't think that is what bothers most students. | |
| Nov 24, 2023 at 4:32 | comment | added | David Roberts | That said, the biggest hurdle at a nuts-and-bolts level is knowing what it means to prove an implication (that is, the single step P(n) => P(n+1)). But that is an independent issue from have a reason to "believe in" induction (as in, to have a well-founded trust that it really does work). | |
| Nov 24, 2023 at 4:31 | comment | added | David Roberts | @WillOrrick What I mean is that you cannot prove to students why induction is a legitimate argument from things they already know. In my experience students are not certain about how it's ok, because we cannot prove why it's ok. It's just presented as a fait accompli, which is more or less is. By saying "people just don't get it" only sweeps the reason they don't get it under a different rug. By saying "maybe it seems circular", you are closer to the mark. I think students want a reason why it works. I don't mean from the other axioms of Peano Arithmetic, but even a pre-formal argument. | |
| Nov 24, 2023 at 3:13 | comment | added | Will Orrick | @DavidRoberts "...the hardest part about teaching induction is that it cannot be proved from simpler principles, it is literally an axiom..." If this is your experience then it's not my place to argue, but my experience is that induction is hard to teach because people simply don't get it--maybe because it seems circular. Once they catch on, I think it's easy for them to accept that there should be such a principle. That the principle doesn't follow from the other axioms of Peano arithmetic and needs to be assumed is an interesting point about formalization, but not a barrier to understanding, | |
| Nov 23, 2023 at 16:20 | comment | added | user12357 | @Dominique According to the OED, induction (as meaning generalization from particulars) came into English in the 1500s from Aristotle, epagoge (epi*+*agoge, on+leading, or leading on from particulars to the general), via Cicero's translation as inductio. Possibly mathematics borrowed the term from induction in natural science, which had become prominent due to Francis Bacon (Nova Organum, 1620). The phrase "mathematical induction" first appears in an article on induction by De Morgan in the Penny Cyclopedia (1838), which first calls it "successive induction," a better name, imo. | |
| Nov 23, 2023 at 11:54 | vote | accept | Dan | ||
| Nov 22, 2023 at 8:13 | comment | added | Dominique | I believe it's very interesting to realise that "induction" comes from "indūcere", which means "to lead someone inside (a building or a room)". I guess it means that the person does not accompany his guest inside. From there you have the physical meaning "to cause an effect inside something (without actually going inside)", but how does the word "induction" gets it mathematical meaning? | |
| Nov 22, 2023 at 3:04 | comment | added | Ferenc Beleznay | @RobbieGoodwin I am not sure I understood your comment correctly, but in my previous reply the word "hence" in step 3 means (at least in IBDP examination markschemes) that the work done in step 1 and step 2 imply somehow the claim in step 3. This "somehow" is the principle of mathematical induction. With the wording in my previous reply we use it without explicitly referring to it. If I change the wording in step 3 to "Hence, by the principle of mathematical induction, P(n) is true for all nonnegative integer n", then we use it with an explicit reference. | |
| Nov 21, 2023 at 22:48 | answer | added | user1815 | timeline score: 6 | |
| Nov 21, 2023 at 21:54 | comment | added | Robbie Goodwin | @FerencBeleznay Thanks and while it's clear that Comment uses it, are you suggesting it refers to the principle? | |
| Nov 21, 2023 at 11:10 | comment | added | Ferenc Beleznay | @RobbieGoodwin I cannot post an example in a comment, but here is an outline. Step 1: checking P(0). Step 2: proving that P(k) implies P(k+1). Step 3: "Hence, P(n) is true for all nonnegative integer n" | |
| Nov 21, 2023 at 11:05 | comment | added | Ferenc Beleznay | @Stef It is not about "blindly" following markschemes. Students can get a surprise if I (as a teacher) consistently tell students that they do not have to refer to the principle explicitly, but at the end of their two year study (in the IBDP system) they get a centralized exam, where examiners do require it (just because in that particular year they felt it that way). Of course, this can be avoided with consistently requiring an explicit reference. | |
| Nov 21, 2023 at 5:31 | comment | added | printf | When teaching, it would definitely be a good idea to mention induction explicitly, every time it is used. It will help students familiarise themselves with the notion. However when examining, or grading coursework, one should not penalise students for not mentioning induction by name, if their answers, otherwise, use induction arguments correctly. | |
| Nov 21, 2023 at 2:22 | answer | added | ac15 | timeline score: 2 | |
| Nov 21, 2023 at 0:20 | comment | added | David Roberts | It's important to know that the hardest part about teaching induction is that it cannot be proved from simpler principles, it is literally an axiom of how natural numbers are formally defined. I'm always honest with students and tell them about this fact. I tell them it is indeed subtle, and that the recognition that this is actually such an axiom was only codified near the 19th century, a loooong time after people have been using numbers for all sorts of things. | |
| Nov 20, 2023 at 23:49 | comment | added | David Roberts | When I learned induction at high school, you needed to use a very precise and long phrase at the end of the proof, something along the lines of "Since P(0) is true, and whenever P(k) is true, P(k+1) is true, then by the principle of mathematical induction, P(n) is true for all n" (and this was over two decades ago, and I've never used it since). If you didn't include this precise phrase, you lost marks, regardless of whether the proof was correct or not. Personally, I'd love to see the death of the phrase "principle of mathematical induction", in favour of plain "induction". | |
| Nov 20, 2023 at 19:17 | comment | added | Robbie Goodwin | Can you Post some examples? Can you show how you'd use proof by induction, without referring to it? | |
| Nov 20, 2023 at 12:24 | comment | added | Stef | Also, the most important thing here is probably how consistent you, the teachers, are with your students. If you explicitly tell them that proofs are expected to use the word "induction" explicitly, then there is no surprise. But if you're sometimes very strict about it and sometimes don't care, because you're following inconsistent mark schemes blindly, then the pedagogical impact will be awful for the students. | |
| Nov 20, 2023 at 11:49 | comment | added | Stef | If a student doesn't refer to the pigeonhole principle explicitly, how do you know that they were using the pigeonhole principle at all? Likewise, if a proof ends with "and thus 1 = 0" and doesn't conclude "and this shows by proof by contradiction that square root of 2 cannot be rational", how are you going to know that it was a proof by contradiction and what it is that was proven? | |
| Nov 19, 2023 at 22:24 | answer | added | user52817 | timeline score: 3 | |
| Nov 19, 2023 at 21:59 | comment | added | Robbie Goodwin | Isn't 'by the principle of mathematical induction' needed only when various steps have been skipped? If induction does have to be an axiom, where is the rather complicated expression shown by that link included in the list of axioms? | |
| Nov 19, 2023 at 17:59 | answer | added | Yiab | timeline score: 3 | |
| Nov 19, 2023 at 16:05 | comment | added | Robert Columbia | One way to approach this is to ask what professional mathematicians do. If I open up a math journal and see a proof by induction, will it assume that I will recognize that it is a proof by induction or will it have verbiage such as "by the principle of induction"? | |
| Nov 19, 2023 at 6:26 | comment | added | Justin Meiners | I don't know what "should" and "have to" mean in this context. There are no official rules for what constitutes a proof or not. They are written to convince an audience. The question that's relevant is whether requiring your students to do this helps them learn the material better and avoid mistakes. | |
| Nov 19, 2023 at 5:26 | answer | added | Ferenc Beleznay | timeline score: 5 | |
| Nov 18, 2023 at 22:12 | answer | added | Humberto José Bortolossi | timeline score: 2 | |
| Nov 18, 2023 at 11:05 | history | became hot network question | |||
| Nov 18, 2023 at 8:47 | answer | added | Tommi | timeline score: 3 | |
| Nov 18, 2023 at 6:38 | history | edited | Dan | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Nov 18, 2023 at 4:31 | answer | added | Dan Christensen | timeline score: -3 | |
| Nov 18, 2023 at 3:25 | answer | added | Justin Skycak | timeline score: 26 | |
| Nov 18, 2023 at 3:05 | history | asked | Dan | CC BY-SA 4.0 |