19 thoughts on “Why proof by pattern of examples doesn’t work”

John Venier

You bring up a fascinating philosophical question — the problem of induction, one of the great problems of (at least Western) philosophy. I think it is fascinating because there is no way to reason from first principles that inductive reasoning should apply, and yet all of science (by which I mean the experimental variety, as opposed to theoretical) relies on it utterly. Moreover we all personally depend on it constantly, and life or existence without being able to rely on it is difficult to imagine. It is also the basis for eliciting prior information in Bayesian statistics.

I suspect the answer to this riddle is deep indeed.

Besides being an example where inductive reasoning fails, your observation is a good example of why I hate the “What’s the next (or missing) value in the sequence of integers?” puzzles, or problems on IQ tests. They are of course incorrigably ill-posed problems, except perhaps trivially by supplying the answer while posing the problem, or constraining the possible answers so that only one number fits the constraints. Anyway, while they can be constructed to minimize the difficulty in most cases, sometimes the constructor does not even know that there is a difficulty. This seems especially the case in elementary school work.

I thought that at one time I sat through a rigorous proof of why proof by induction was valid. Like in an undergrad number theory class. I could be mistaken though.

John

The problem here isn’t induction in the mathematical sense. It’s an example of induction in the colloquial sense of extrapolating a pattern based on tuition.

Say we conjecture that n points leads to 2^(n-1) regions. A rigorous mathematical proof would establish the theorem for a base case, say n = 2. Next it would prove that if the theorem holds for any m >= 2 then it also holds for m+1. But in this case, the inductive step isn’t true and so it cannot be proven and neither can our conjecture.

John Venier

Well sure, what’s called “proof by induction” in math is fine.

The kind of induction I was writing about is concluding that because you have cracked open 100 eggs and seen a yolk inside, the next one you crack open will have a yolk inside.

Unfortunately I don’t have a broad enough vocabulary to know a term that distinguishes this reasoning from mathematical induction. Similarly, although I could write that there is no logical reason to believe the 101st egg will have a yolk inside it (and this is true) some folks would read “logical” as “sensible” and come to the opposite conclusion.

For some reason I find it difficult to discuss — probably my paucity of terms with unambiguous meanings. Also, inductive reasoning is so ingrained our consciousness, science, even the behavior of living organisms (in as much as they can be held capable of belief, expectation, or reasoning; if anthropomorphised their behavior clearly reflects it) that it is difficult to percieve it itself. This means that unless someone has thought about it previously, they are unlikely to be persuaded in a short conversation that it is different from deductive reasoning, present company excluded of course

John

JV: I agree with your skepticism regarding test questions of the form “What number is next in this sequence?” I hated those questions in school. I wanted to justify my answer, which of course you can’t do on a multiple choice test on a bubble form. If I were grading such an exam, I would reward someone who could give a good defense for an unusual answer. Of course standardized tests punish such original thought.

John Venier

[N.B. This and my previous comment are directed primarly at Kate Nowak, even though it looks like I am commenting incoherently on John’s comment :-)]

Maybe this article will help. I haven’t read it thoroughly but it seems to be on the right track. Note in particular the bit at the end about mathematical induction.

John Venier

John: Absolutely. I think that the only reasonable way to ask those number-seuqence problems is to treat them like essay questions, where the quality of your argument is being assessed rather than the conclusion you draw. When you get down to it, the number-sequence problems are asking an opinion, like what the best ice cream flavor is. In that case most folks would get the right answer if the choices were appropriately limited, even though in principle there is no one correct answer.

John Venier

Hey John, you were wondering a while back about a better term than Bayesian for Bayesian statistics. How about referring to frequentist statistics as ‘deductive statistics’ and Bayesian statsitics as ‘inductive statistics’

The two types of induction are sometimes called mathematical induction and statistical induction. There are several types of mathematical induction (weak induction, strong induction, transfinite induction, etc.) and all of them are special types of deductive reasoning. Statistical induction is not deductive. Often types of reasoning are carved up into four classes: deductive, inductive, abductive, and analogical. See:

It reminds me of what I am told regarding the Syadvada system of Jain logic, where there are seven logical states: true, false, true or false, indeterminate, true or indeterminate, false or indeterminate, true or false or indeterminate.

We tend to assume that ways of thinking which seem fundamental to us are universal. From what I can tell, this is far from accurate.

I was told that a certain evangelical organization contracted with the Gallup organization to prove that regardless of particular religion or culture, most people believe in some kind of God. The evangelicals knew this to be true, but wanted evidence to present to skeptics. The Gallup folks polled the Japanese, and found that a majority didn’t believe in any sort of God.

Multi-valued logics are all types of deductive logic. Other types of deductive logic are temporal or tense logic (the logic of time — and there are many different logics of time), modal logic (the logic of possibility and necessity — and there are many different modal logics), intuitionist logic (denies the law of the excluded middle), relevance logic (the logic of relevant implication — many varieties), and so on.

John V.

Fascinating! In classical Hindu philosophy they likewise have eight or so methods of proof, IIRC.

When I was a kid I tried to construct a three-valued logic system for a science fiction story I was writing. One of the hypotheses for the story was that we (as humans) use two-valued logic and generally binary ways of thinking because we are bilaterally symmetric. Assuming that, I wondered, how would sentient beings who were trilaretally symmetric construct their understanding of the world? I decided to call the truth states red, yellow, and blue to avoid bias. I was merrily constructing logical operation tables when I heard that this had already been done, for arbitrary (n) values of truth. I lost interest after that.

I guess the philosophy of logic is much deeper and broader than I thought!

Why does proof induction work? Why should it work at all? It seems like induction is the same sort of reasoning – although I do see the difference I dont understand what makes induction so much stronger. How does one actually prove proof by induction yields a valid result? As I understand it in my own research, it is simply regarded as an axiom of mathematical reasoning.

Proof by induction is just “finding a pattern”… the same sort of fallacy youre referring to in your post.

John

Cogito: Mathematical induction is not the same as induction in the colloquial sense. A proof by mathematical induction ultimately reduces to mathematical axioms just as any other proof. It’s a perfectly rigorous technique.

My complaint about mathematical induction is that sometimes it establishes the truth of a theorem without giving much intuition for why the theorem holds or how one might extend it.

@John – I don’t think you understand my point though. Let me ask you this… how do you prove that proof by induction works? I cant seem to find a proof for the technique. Most so-called “mathematicians” simply say its an axiom of mathematical reasoning. I don’t see why it should work as a general technique in every case.

Frankly, I don’t agree with your definition of the word “induction” used in this post. More like “intuition” in many respects.

Don’t get me wrong, your post demonstrated prejudice perfectly… an assumption about the truth from a few observations. But is a hypothesis ever wrong? Its valid, just as any postulate is, until finally proven or disproven.

I’m not disputing that “induction” from observation can be wrong… I just don’t perceive any real difference between it done here in a mathematical context and it done elsewhere in a mathematical context. Sometimes you call it invalid and sometimes not. But here, it took a contradictory example for you to declare with certainty that the induced theorem was wrong. Now, when induction is used “validly” in other contexts… how do we know its right? No one can prove how or why induction works in the first place. And you certainly cannot go through every possible example to check that they all work.

I understand the technique perfectly. My problem is “why induction works”. Because if you cant prove to me why it works except to demonstrate the few cases where it does then how do we know there aren’t stipulations and conditions for its use? How do we know that there aren’t entire classes of problems for which proof by induction simply will not work?

No offence… and I know that I am not articulating my question very well… but you are trivializing my inquiry by hiding behind your relative education instead of appreciating the conceptual depth I believe my question has. As most people do, I might add, when I ask a question. Very rarely does someone ever admit to me that my question has insight or implication, very rare does anyone ever truly grasp my question, and then they are usually stumped at answering. Then again, maybe I really am misconceiving the notion… but considering as to how I use it and have been using the technique for many years, I doubt I am stumbling over the basics here. There is a certain philosophy to what I’m asking. Not just blind mathematical rigor, for whatever that is really worth.

My biggest pet peeve about proof by induction is that it only works for integer increments of a particular argument. You cannot generalize it to all real numbers, or all complex numbers. Typically only the whole numbers are involved.

Jonathan

A standard mathematical proof by induction is equivalent to a proof by well-ordering. If we accept that the natural numbers are well-ordered (which is an axiom), the validity mathematical induction on the natural numbers immediately follows.

Ben N

I remember participating in a conversation in college in which a friend and I convinced ourselves that either inductive reasoning works or we are just doomed (because if the future won’t resemble the past we can’t get an empirical handle on the world at all). Of course, the world could operate consistently up to a point and then “stop operating consistently” (in the sense of doing something we had not previously observed) and doom us — this is Taleb’s Black Swan. But the general idea was that in a world in which epistemology can’t be grounded in inductive empiricism, it probably can’t be grounded at all.

John V.

The first time I came across this point I was shocked. I think it is good to keep in the back of your mind, but of course the only reasonable choice is to behave as if the sun will come up tomorrow just like it did today ;-).

You bring up a fascinating philosophical question — the problem of induction, one of the great problems of (at least Western) philosophy. I think it is fascinating because there is no way to reason from first principles that inductive reasoning should apply, and yet all of science (by which I mean the experimental variety, as opposed to theoretical) relies on it utterly. Moreover we all personally depend on it constantly, and life or existence without being able to rely on it is difficult to imagine. It is also the basis for eliciting prior information in Bayesian statistics.

I suspect the answer to this riddle is deep indeed.

Besides being an example where inductive reasoning fails, your observation is a good example of why I hate the “What’s the next (or missing) value in the sequence of integers?” puzzles, or problems on IQ tests. They are of course incorrigably ill-posed problems, except perhaps trivially by supplying the answer while posing the problem, or constraining the possible answers so that only one number fits the constraints. Anyway, while they can be constructed to minimize the difficulty in most cases, sometimes the constructor does not even know that there is a difficulty. This seems especially the case in elementary school work.

I thought that at one time I sat through a rigorous proof of why proof by induction was valid. Like in an undergrad number theory class. I could be mistaken though.

The problem here isn’t induction in the

mathematicalsense. It’s an example of induction in thecolloquialsense of extrapolating a pattern based on tuition.Say we conjecture that n points leads to 2^(n-1) regions. A rigorous mathematical proof would establish the theorem for a base case, say n = 2. Next it would prove that if the theorem holds for any m >= 2 then it also holds for m+1. But in this case, the inductive step isn’t true and so it cannot be proven and neither can our conjecture.

Well sure, what’s called “proof by induction” in math is fine.

The kind of induction I was writing about is concluding that because you have cracked open 100 eggs and seen a yolk inside, the next one you crack open will have a yolk inside.

Unfortunately I don’t have a broad enough vocabulary to know a term that distinguishes this reasoning from mathematical induction. Similarly, although I could write that there is no logical reason to believe the 101st egg will have a yolk inside it (and this is true) some folks would read “logical” as “sensible” and come to the opposite conclusion.

For some reason I find it difficult to discuss — probably my paucity of terms with unambiguous meanings. Also, inductive reasoning is so ingrained our consciousness, science, even the behavior of living organisms (in as much as they can be held capable of belief, expectation, or reasoning; if anthropomorphised their behavior clearly reflects it) that it is difficult to percieve it itself. This means that unless someone has thought about it previously, they are unlikely to be persuaded in a short conversation that it is different from deductive reasoning, present company excluded of course

JV: I agree with your skepticism regarding test questions of the form “What number is next in this sequence?” I hated those questions in school. I wanted to justify my answer, which of course you can’t do on a multiple choice test on a bubble form. If I were grading such an exam, I would reward someone who could give a good defense for an unusual answer. Of course standardized tests punish such original thought.

[N.B. This and my previous comment are directed primarly at Kate Nowak, even though it looks like I am commenting incoherently on John’s comment :-)]

Maybe this article will help. I haven’t read it thoroughly but it seems to be on the right track. Note in particular the bit at the end about mathematical induction.

John: Absolutely. I think that the only reasonable way to ask those number-seuqence problems is to treat them like essay questions, where the quality of your argument is being assessed rather than the conclusion you draw. When you get down to it, the number-sequence problems are asking an opinion, like what the best ice cream flavor is. In that case most folks would get the right answer if the choices were appropriately limited, even though in principle there is no one correct answer.

Hey John, you were wondering a while back about a better term than Bayesian for Bayesian statistics. How about referring to frequentist statistics as ‘deductive statistics’ and Bayesian statsitics as ‘inductive statistics’

The two types of induction are sometimes called mathematical induction and statistical induction. There are several types of mathematical induction (weak induction, strong induction, transfinite induction, etc.) and all of them are special types of deductive reasoning. Statistical induction is not deductive. Often types of reasoning are carved up into four classes: deductive, inductive, abductive, and analogical. See:

http://plato.stanford.edu/entries/induction-problem/

http://en.wikipedia.org/wiki/Mathematical_induction

http://en.wikipedia.org/wiki/Inductive_reasoning

http://en.wikipedia.org/wiki/Deductive_reasoning

http://en.wikipedia.org/wiki/Abductive_reasoning

http://en.wikipedia.org/wiki/Analogical_reasoning

It can be argued that inductive, deductive, and abductive reasoning are all based on a foundation of analogical reasoning:

http://www.jfsowa.com/pubs/analog.htm

Thanks Peter!

It reminds me of what I am told regarding the Syadvada system of Jain logic, where there are seven logical states: true, false, true or false, indeterminate, true or indeterminate, false or indeterminate, true or false or indeterminate.

We tend to assume that ways of thinking which seem fundamental to us are universal. From what I can tell, this is far from accurate.

I was told that a certain evangelical organization contracted with the Gallup organization to prove that regardless of particular religion or culture, most people believe in some kind of God. The evangelicals knew this to be true, but wanted evidence to present to skeptics. The Gallup folks polled the Japanese, and found that a majority didn’t believe in any sort of God.

There are many varieties of multi-valued logic:

http://en.wikipedia.org/wiki/Multi-valued_logic

Multi-valued logics are all types of deductive logic. Other types of deductive logic are temporal or tense logic (the logic of time — and there are many different logics of time), modal logic (the logic of possibility and necessity — and there are many different modal logics), intuitionist logic (denies the law of the excluded middle), relevance logic (the logic of relevant implication — many varieties), and so on.

Fascinating! In classical Hindu philosophy they likewise have eight or so methods of proof, IIRC.

When I was a kid I tried to construct a three-valued logic system for a science fiction story I was writing. One of the hypotheses for the story was that we (as humans) use two-valued logic and generally binary ways of thinking because we are bilaterally symmetric. Assuming that, I wondered, how would sentient beings who were trilaretally symmetric construct their understanding of the world? I decided to call the truth states red, yellow, and blue to avoid bias. I was merrily constructing logical operation tables when I heard that this had already been done, for arbitrary (n) values of truth. I lost interest after that.

I guess the philosophy of logic is much deeper and broader than I thought!

Why does proof induction work? Why should it work at all? It seems like induction is the same sort of reasoning – although I do see the difference I dont understand what makes induction so much stronger. How does one actually prove proof by induction yields a valid result? As I understand it in my own research, it is simply regarded as an axiom of mathematical reasoning.

Proof by induction is just “finding a pattern”… the same sort of fallacy youre referring to in your post.

Cogito: Mathematical induction is not the same as induction in the colloquial sense. A proof by mathematical induction ultimately reduces to mathematical axioms just as any other proof. It’s a perfectly rigorous technique.

My complaint about mathematical induction is that sometimes it establishes the truth of a theorem without giving much intuition for why the theorem holds or how one might extend it.

@John – I don’t think you understand my point though. Let me ask you this… how do you prove that proof by induction works? I cant seem to find a proof for the technique. Most so-called “mathematicians” simply say its an axiom of mathematical reasoning. I don’t see why it should work as a general technique in every case.

Frankly, I don’t agree with your definition of the word “induction” used in this post. More like “intuition” in many respects.

Don’t get me wrong, your post demonstrated prejudice perfectly… an assumption about the truth from a few observations. But is a hypothesis ever wrong? Its valid, just as any postulate is, until finally proven or disproven.

I’m not disputing that “induction” from observation can be wrong… I just don’t perceive any real difference between it done here in a mathematical context and it done elsewhere in a mathematical context. Sometimes you call it invalid and sometimes not. But here, it took a contradictory example for you to declare with certainty that the induced theorem was wrong. Now, when induction is used “validly” in other contexts… how do we know its right? No one can prove how or why induction works in the first place. And you certainly cannot go through every possible example to check that they all work.

I understand the technique perfectly. My problem is “why induction works”. Because if you cant prove to me why it works except to demonstrate the few cases where it does then how do we know there aren’t stipulations and conditions for its use? How do we know that there aren’t entire classes of problems for which proof by induction simply will not work?

No offence… and I know that I am not articulating my question very well… but you are trivializing my inquiry by hiding behind your relative education instead of appreciating the conceptual depth I believe my question has. As most people do, I might add, when I ask a question. Very rarely does someone ever admit to me that my question has insight or implication, very rare does anyone ever truly grasp my question, and then they are usually stumped at answering. Then again, maybe I really am misconceiving the notion… but considering as to how I use it and have been using the technique for many years, I doubt I am stumbling over the basics here. There is a certain philosophy to what I’m asking. Not just blind mathematical rigor, for whatever that is really worth.

My biggest pet peeve about proof by induction is that it only works for integer increments of a particular argument. You cannot generalize it to all real numbers, or all complex numbers. Typically only the whole numbers are involved.

A standard mathematical proof by induction is equivalent to a proof by well-ordering. If we accept that the natural numbers are well-ordered (which is an axiom), the validity mathematical induction on the natural numbers immediately follows.

I remember participating in a conversation in college in which a friend and I convinced ourselves that

eitherinductive reasoning worksorwe are just doomed (because if the future won’t resemble the past we can’t get an empirical handle on the world at all). Of course, the world could operate consistently up to a point and then “stop operating consistently” (in the sense of doing something we had not previously observed) and doom us — this is Taleb’s Black Swan. But the general idea was that in a world in which epistemology can’t be grounded in inductive empiricism, it probably can’t be grounded at all.The first time I came across this point I was shocked. I think it is good to keep in the back of your mind, but of course the only reasonable choice is to behave as if the sun will come up tomorrow just like it did today ;-).