Timeline for Paradox - What is wrong with this proof that proves a false assertion?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 11, 2013 at 17:16 | comment | added | Thomas Andrews | What you've shown is that your algorithm is $O(n)$, not that any algorithm, when given an input of $n$, computes $a_n$, is $O(n)$. @CraigFeinstein | |
| Mar 11, 2013 at 17:15 | comment | added | Craig Feinstein | OK, that makes sense. | |
| Mar 11, 2013 at 17:15 | vote | accept | Craig Feinstein | ||
| Mar 11, 2013 at 17:12 | comment | added | Thomas Andrews | You are confusing definition with algorithm. $a_1=1, a_{n+1}=a_n+1$ is a definition of a sequence. It is also an implicit algorithm for computing that sequence, but it is not the only algorithm that computes the $n$th element of that sequence. | |
| Mar 11, 2013 at 17:07 | comment | added | Cameron Buie | If recursion were the only way to determine the values of the various $a_n$, then we would need to do an extra computation at each step. It isn't the case here, though. | |
| Mar 11, 2013 at 17:05 | comment | added | Cameron Buie | Why is it necessary to know what $a_{k-1}$ is in order to compute $a_k$? You've not justified this, and you can't, because it isn't true. For example, I can tell you that $a_{1000000}=1000000$ without ever thinking about $a_{999999}$. Your induction step rests on this false assumption, and by assuming that a false statement is true, you allow yourself to draw the false conclusion. | |
| Mar 11, 2013 at 17:00 | comment | added | Craig Feinstein | You've shown that the theorem is false. But why is the proof invalid? In order to compute $a_{k-1}+1$, it is certainly necessary to know what $a_{k-1}$ is, so you have to compute it. Then since $a_k=a_{k-1}+1$, in order to compute $a_k$, you have to compute $a_{k-1}$. | |
| Mar 11, 2013 at 16:46 | history | answered | Cameron Buie | CC BY-SA 3.0 |