Zeno's Achilles & Tortoise - Where exactly is the proof wrong? (For those who don't know what this paradox is see Wikipedia  or the Stanford Encyclopedia of Philosophy.)
Let us define $a_i$ and $b_i$ recursively
$$
a_0 = 0\\
b_0 = 1\\
a_i = a_{i-1} + (b_{i-1} - a_{i-1})\\
b_i = b_{i-1} + (b_{i-1} - a_{i-1})/2
$$
It is easy to prove that $b_i>a_i\  \forall i$ using induction.
Thus while $|b_i-a_i|$ tends to $0$ , we will never have $a_i>b_i$.
We can now just replace $a_0$ as Achilles start position and $b_0$ as Tortoise start position. And then subsequent positions of Achilles is given by $a_i$s (Achilles new position is = Tortoise old position, which is the $1^{st}$ recursion). And Tortoise is assumed to move at half the speed of Achilles. Tortoise positions are represented by $b_i$s. (So, new position of Tortoise = Old Position + 1/2 the distance traveled by Achilles, which is the $2^{nd}$ recursion.)
Given, we have proven $b_i>a_i\  \forall i$, thus I claim Achilles will always be behind Tortoise (He will come closer and closer but will never overtake).
Obviously, I'm wrong but exactly where / which step of the proof above? (Please provide the exact mathematical step/argument where I went wrong.)
Some further discussion:
Basis the responses I got (which I'm unable to find fully convincing - and it maybe just me that I don't understand them well enough) I would like to add - In my opinion, the way I have defined $a_i$ and $b_i$ it is just a subset of positions that Achilles and Tortoise can take. In that subset what I have proved is correct i.e. Achilles cannot overtake Tortoise. But just in that subset <- And I think this is the key
Note that my $a_i$ and $b_i$ are all rational. I can embed infinite rationals between any 2 points on the real line. I think fundamentally the error in my proof is that I use induction on continuous variables. I'm not formally trained to express that mathematically in a precise way - Hence this question.
My question is not to challenge/discuss that Achilles will overtake or not etc or to come-up with another proof - My precise question is where exactly is my proof wrong.
Thanks
 A: The issue is as follows. You have constructed an infinite sequence of times, at all of which Achilles is behind the tortoise. However, that doesn't mean that Achilles will always be behind the tortoise, because the set of times you have constructed is bounded.  Suppose Achilles has unit speed. Then they reach positions $a_1$ and $b_1$ at time $1$, $a_2$ and $b_2$ at time $3/2$, $a_3$ and $b_3$ at time $7/4$, and so on. It is easy to verify that all these times are less than $2$, so your argument only implies the tortoise is ahead for $t<2$. (Indeed, $t=2$ is exactly when Achilles overtakes the tortoise.)
A: There's a reason Zeno's Paradoxes are still famous after all this time.
You need a frame shift to solve this paradox. If you follow Zeno's argument, you will prove Zeno's argument. The "thing" is not inside the logic, all of that is sound and has been argued a million times.
You need to step outside the frame to spot the problem. In this particular paradox, that is a non-constant time axis, while our reality flows (as we experience it) with constant time.
If you follow the paradox in linear time, you would look at the positions a and b at time 1, then 2, then 3, and then Achilles overtakes the tortoise at 4.
But if you follow the paradox in its artfully manipulated internal frame, you look at the positions of a and b at time 1, then 1.5, then 1.75, then 1.1875...
Instead of wondering why a never reaches b you should be wondering why the timer never reaches 2. The beauty of the paradox is that, like a stage magician, it misdirects your attention to the entirely wrong question.

expanding on my original answer, a crude attempt to visualize:

If you make the time an explicit parameter, you can see more clearly what is going on. Assuming linear time, it is obvious that Achilles reaches and overtakes the tortoise at time 2.0
But Zeno messes with the time. The paradox describes the bottom scenario, and you can see that Achilles never overtakes the tortoise - but the reason is in the blue line: Time essentially slows down in this frame as you approach the event that never happens.
The closest that we believe to happen in physical reality is falling into a Black Hole. From the outside, nothing special happens. You just fall in and disappear. But from the inside frame, time slows down as you approach the event horizon and you never experience the actual fall. Not because it doesn't happen, but because your frame of reference doesn't reach it, because time slows down to infinity - but only for you.
So, in summary, we can conclude that the tortoise is really, really massive and made from Neutronium... :-)
A: Summary
Your proof is completely correct, there's no mistake in it. The mistake lies in your interpretation of the result that you prove.
Mistake
Before I pinpoint your mistake, note that
$$b_n<2\:\:\forall \:n\in\mathbb N\quad \rm and \quad a_n<2\:\:\forall \:n\in\mathbb N$$
which immediately implies that whatever you're going to conclude from your proof holds true only for the time interval where the displacement of Achilles and the tortoise, both, is less than $2$ units. After that, your series cannot provide us any information on how the distance between them will change.
Now you correctly concluded that $a_n<b_n \:\:\forall \:n\in\mathbb N$, but this only holds true for $a,b<2$. And now if we translate this mathematical argument to our paradox, we see that our proof states that Achilles will stay behind the tortoise as long as both of them haven't reached the $2$ unit mark. As they slowly get closer and closer to the $2$ unit mark, the displacement between them will start getting smaller and smaller, until they reach the $2$ unit mark. At this point, our series formulation is of no use, since $a=b=2$ is outside the "domain" of our series. And physically we know that it is at this point ($2$ unit mark) that Achilles will overtake the tortoise.
So, all in all, the equations just told you that Achilles will stay behind the tortoise up till the $2$ unit mark. This conclusion, as we know, is completely true and matches with the physical reality that we expected.
Conclusion
Thus, neither your mathematical formulation, nor what it "really" predicts is at fault here. In fact, nothing is fallacious at all because the math agrees with the reality. You were just drawing the wrong conclusions.
A: The sequence of positions you've constructed also has a corresponding sequence of times when it happens. This sequence of times, let's call it $t_i$, is increasing and infinite, but it is bounded.
All your proof shows is that at these times $t_i$, the tortoise is ahead of Achilles. To show that it will always be ahead, you would have to show that it is ahead at any time. That doesn't follow from the fact that it will be ahead in some infinite increasing sequence.
I think the implicit (and faulty) assumption Greek mathematicians of those times had, is that they thought an infinite sum of positive numbers should be infinite. The tortoise is ahead for $0.5 + 0.25 + …$ seconds, therefore it's always ahead.
Obviously they knew there's something wrong somewhere along their reasoning... but it took some formalization and study of the concept of infinite sequences/sums to realize that it doesn't really make sense to say that an infinite sum of positive numbers is always infinite.
A: You are asking two different questions:

*

*Given Achille and the Tortoise have respectively the positions $a_i$ and $b_i$ and $b_0 > a_0$, will Achille ever catch up with the Tortoise?

*Given Achille moving twice as fast as the Tortoise, and the Tortoise having a head start, will Achill ever catch up with the Tortoise?

You correctly prove that the answer to question 1 is "No". However you never prove that both question are equivalent.
If you could prove that in scenario 2 Achille and the Tortoise can only have positions given by $a_i$ and $b_i$ respectively, then your reasonning would hold and Achille could never catch the Tortoise.
In short you proof is correct, but does not prove what you claim it does.
A: "I claim Achilles will always be behind Tortoise." But what is the interpretation of always? It certainly refers to time and I think it means that Achilles cannot overtake Tortoise in finite time.
Your argument (and Zenon's 2500 years ago) reads pointedly in the following trivial form:

As long as Achilles is behind Tortoise, Achilles stays behind Tortoise for a sufficiently small additional running distance.

In fact, we know that Achilles catches up Tortoise exactly at time $t^* = 2$ and position $p^* = 2$. If Achilles has reached, at time $t < 2$, a position $A(t)$ behind Tortoise's position $T(t)$, and you give him additonal time $\tau < 2 - t$, then at time $t +\tau$ he will have reached position $A(t+\tau)$ which is trivially behind Tortoise's position $T(t+\tau)$. Your argument is an infinite iteration of this step with special values of $t$ and $\tau$: You start with $t_0 = 0 < 2$ where $A(t_0) = a_0 = 0, T(t_0) = b_0 = 1$. Then you give time $\tau_0 = 1$, so that for $t_1 = t_0 + \tau_0< 2$ you have $A(t_1) = T(t_0) < T(t_1)$. Next you give time $\tau_1 = 1/2$, so that for $t_2 = t_1 + \tau_1< 2$ you have $A(t_2) = T(t_1) < T(t_2)$, etc. Now time is eliminated from this construction and you get your sequence of positions $b_i= T(t_i)$ and $a_i =A(t_i) = b_{i-1}$. Clearly $a_i < b_i$ for all $i$ and $(b_i - a_i) \to  0$ as $i \to \infty$.
Doing so means that always is understood in the sense of for all $i$, i.e. essentially in the sense of as long as $t < 2$ which is equivalent to as long as $A(t) < T(t)$. But this is trivial and has nothing to do with always understood as in finite time.
The philosophical background is an uneasy feeling concerning the concept of infinity: How is it possible to pass infinitely many positions in finite time? But if one thinks that is a problem, then the whole argument is self-contradictory: It accepts that Achilles can pass infinitely many intermediate positions in finite time to reach a certain position like $a_1 = 1$, but simultaneously denies that he can pass infinitely many positions $a_i$ in finite time. To illustrate this, let us consider a second Tortoise $T'$ starting at position $1/2$ with the same speed as $T$. Zenon's argument applied to $T'$ shows that Achilles is always behind $T'$, on the other hand Zenon's argument applied to $T$ invokes the fact that Achilles reaches the position $1$. But at position $1$ Achilles is no longer behind $T'$.
In my opinion Zenon's paradox can be regarded as an early instance of the philosophical struggle "potential infinity" vs. "actual infinity". See https://en.wikipedia.org/wiki/Actual_infinity.
By the way, with his arrow paradox Zenon tries to prove that motion is impossible. This would be the most convincing explanation why Achilles will always be behind Tortoise ;-)
Edited:
You edited your question and state

I claim Achilles will always be behind Tortoise (He will come closer and closer but will never overtake).

Never makes clear that you mean at no time. That's the error, you only consider a certain sequence of points in time at which Achilles is trivially behind Tortoise.
A: So let me formulate your 'proof' in precise steps so that I can tell where exactly the problem lies.
Step 1) We denote the position of Achilles and tortoise at time $t_i$ to be $a_i$ and $b_i$ respectively where $t_i$ is defined as
$$t_i = 1 - \frac{1}{2^n}$$ (This can also be given as the sum of $\frac{1}{2^i}$'s.)
Step 2) We observe that at each $t_i$, the $a_i$'s and $b_i$'s are as given in the question and thus $$b_i > a_i$$ for every $i$.
Step 3) Now, we observe that the sequence $t_i$ is an increasing sequence.
Step 4) Due to the fact that $t_i$ is an increasing sequence of time, we claim that and $b_i>a_i$ in each moment before $t_i$, for each $i$, it is possible to claim that $b_t>a_t$ for any time $t$ where $a_t$ and $b_t$ are positions of Achilles and tortoise respectively at time $t$.
Now, as our hypothesis is completed in steps I can show you where the mistake occurs. It is in the claim in Step 4). This is because, the observations made before, only suggests that $a_t<b_t$ for $t< \lim  t_i = 2$ and not any further in time. Thus it is possible for Achilles to cross the tortoise after $t=2$.
A: You write "Given, we have proved $b_i > a_i, \forall i$ ,thus I claim Achilles will always be behind Tortoise (He will come closer and closer but will never overtake)."  This contains two sentences.  The first sentence may or may not be false, depending on your meaning of "always".  The parenthetical sentence is unambiguously false.
You have proven that for all $i \in \{0,1,\dots\}$, $b_i > a_i$.  You have not related $i$ to time.  You have not, in fact, incorporated time in your model at all.  Thus, the only sense of "always" leading to a valid first sense is "for all nonnegative $i$".
"He will come closer and closer but will never overtake."  cannot be concluded from "$i \in \{0,1,\dots\}$, $b_i > a_i$".  All you can say is, for the times corresponding to nonnegative values of $i$, he will come closer and closer and not overtake.  Your derivation is completely mute to times not corresponding to nonnegative $i$.
Your argument sees a sequence of snapshots of Achilles successively approaching the Tortoise's position, but the times at which Achilles passes the Tortoise and subsequently leads the Tortoise are not visible.  In fact, the data your argument uses cannot falsify the following:  In fact, Achilles is moving vastly faster than expected  in each time interval bounded by the instants modelled by the pair of indices $i,i+1$ for $i \geq 0$ -- starting from the position specified at the time corresponding to the index $i$, he runs forward, passing the Tortoise by 100 meters, then turns around, runs back to the position specified at the time corresponding to the index $i+1$, then turns around to face in the forward direction, completing the turn at the time corresponding to the index $i+1$.
Although each index corresponds to a time, there is nothing in your argument indicating that the set of times includes the time when Achilles passes the Tortoise, or any time afterwards.  In short, the argument speaks to a specific set of times, but does not apply to all times.
A: Since you did not, let me try to map your $i$ variable to time.
Let's assume that both Achilles and the Tortoise have constant speed (this is important), and Achilles speed is 1 m/s. Thus, from your definition of $a_i$ and $b_i$, is easy to see that Tortoise speed must be 0.5 m/s.
You defined $a_i$ and $b_i$ as recursive functions, but it is also possible to define them as a continuous, real valued functions. The natural extension to your definition is:
$$
a_i = 2 - 2^{(1 - i)}\\
b_i = 2 - 2^{-i}
$$
Since Achilles speed is 1 m/s, we have that the time is:
$$
t(i) = \frac{a_i}{1 \text{m/s}} = 2 - 2^{(1 - i)}
$$
We can already see the problem, which is $t: \mathbb{R} \rightarrow (-\infty, 2)$, i.e. $t(i) < 2\  \forall i \in \mathbb{R}$. This means that, no matter the value of $i$, it can never describe a world where $t \ge 2$. This becomes clear if we graph $a$, $b$ and $i$ regarding to position and time:

There are some points to consider in this graph:

*

*The closer Achilles and the Tortoise gets to the crossing point, at 2 m, your defined $i$ variable quickly tends to infinity. In fact, $\lim_{i\rightarrow \infty} a_i = 2$, which is the crossing point.

*That is to say $i$ curve never crosses the $t=2$ line.

*The inverse function $i(t)$ is not defined in $\mathbb{R}$ for $t \ge 2$, as you can see:
$$
i(t) = \log_2 \left(\frac{2}{2-t}\right)
$$
So, this is where I disagree with your affirmation "Achilles will always be behind Tortoise": it may be true to say "Achilles will be behind Tortoise for all values of $i$", but $i$ can not describe the whole interval of physical time if the speeds are constant. Instead, $i$ is simply not defined for times where Achilles has overtook the tortoise.
A: The step where your proof goes wrong is between

Given, we have proved $b_i > a_i$ ∀

and

thus I claim Achilles will always be behind Tortoise (He will come closer and closer but will never overtake)

The variable $i$ is not time. What you have shown is that, as Achilles overtakes the Tortoise, there is an infinite set of moments where Achilles is still behind the Tortoise, but by smaller and smaller amounts. But you already knew that.
The problem here is that you are trying to find your mistake in the mathematics, but it is actually in how you are interpreting the math as a model of the world. You have proven that something is true for all $i$, but $i$ isn't even meaningful to Achilles and the Tortoise. Time is.
After all, it is also true that there is no $i$ for which Achilles is exactly 1/3 behind the Tortoise. Does that say that Achilles is never exactly that distance away?
It is wrong to say that the problem is with using induction on continuous variables. This is ordinary induction on the discrete variable $i$. The problem is all in the interpretation of your result.
I realize this answer is similar to FakeMod's, but perhaps the perspective is different enough to help.
A: The formula that is given is only valid when $b_i>a_i$. Take for example $a_0=b_0=0$. If they start at the same time, from the same position, it means that the cannot move, since $a_i=b_i=0$. Therefore, in the validity region of your hypothesis, you cannot say anything about the case where the hypothesis is no longer valid.
A: I don't think what I assert is different from what others have already asserted. But here we go for you are not happy :)
\begin{array}{c|c}
\text{What you have written}&\text{What you should write}\\
\hline
(a_0,b_0)_{0s}\equiv (0,1)&a=t,b=\left(\frac t2+1\right)\\
(a_1,b_1)_{1s}\equiv \left(1,1+\frac12\right)\\
(a_2,b_2)_{\left(1+\frac12\right)s}\equiv \left(1+\frac12,1+\frac12+\frac14\right)\\
(a_3,b_3)_{\left(1+\frac12+\frac14\right)s}\equiv \left(1+\frac12+\frac14,1+\frac12+\frac14+\frac18\right)\\
(a_n,b_n)_{\left(\underbrace{1+\frac12+\frac14+\cdots}_{n\text{ terms}}\right)s}\equiv \left(\underbrace{1+\frac12+\frac14+\cdots}_{n\text{ terms}},\underbrace{1+\frac12+\frac14+\cdots}_{\color{red}{(n+1)}\text{ terms}}\right)\\
\end{array}
Although it looks like the left side reaches $(a,b)_{2s}\equiv (2,2)$ after a finite time, it doesn't, no matter what, because there will always be a finite $\color{red}{(n+1)^{\text{th}}}$ term differentiating it from the correct "right" side. To put it in other words, you will always be on the left side of the intersection of $a=t,b=\left(\frac t2+1\right)$ with your sequence doing infinite iterations for a finite time. So, while the left side describes $a=t,b=\left(\frac t2+1\right)$ correctly before the intersection, it never(the word 'never' is defined with respect to iterations) reaches the intersection.
A: My training is as a physicist, and I think of this as a physics problem, so here is how I would think about this from a physics point of view. Mathematically, I think the content of my answer is the same as that of @Especially Lime.
The sequences ${a_n}$, $b_n$ you've written down are discrete snapshots of the positions $x_a(t)$, $x_b(t)$ of Achilles and the tortoise, respectively. Letting the initial time $t_0 = 0$, we have
\begin{align}
a_n &= x_a(t_n)\\
b_n &= x_b(t_n),
\end{align}
where
\begin{align}
x_a(t) &= vt\\
x_b(t) &= x_0 + \frac{v}{2}t
\end{align}
if we choose the initial time $t_0 = 0$. The specific sequence you construct uses units in which $v = 1$ and $x_0 = 1$, but we may as well keep these initial conditions arbitrary.
Your sequence of positions also contains an implicit choice of the sequence of times $t_n$ at which we observe these positions. Let us make this sequence explicit by applying the discrete time-evolution equation to these positions. From the relation $a_n = a_{n-1} + \left[b_{n-1} - a_{n-1}\right] = b_{n-1}$, get
\begin{align}
x_a(t_n) &= x_b(t_{n-1})\\
\rightarrow  vt_n&=x_0+\frac{v}{2}t_{n-1},
\end{align}
so that
\begin{align}
t_n = \frac{x_0}{v}+\frac{1}{2}t_{n-1}.
\end{align}
Starting from the initial time $t_0$, we get
\begin{align}
t_1 = \frac{x_0}{v},\,
t_2 = \frac{3}{2}\frac{x_0}{v},\,
t_3 = \frac{7}{4} \frac{x_0}{v},\,\ldots
\end{align}
Now, as $n\rightarrow \infty$, we have $t_n \rightarrow 2x_0/v$, but for any finite $n$, $t_n < 2x_0/v$.
If we seek the time $t_{\ast}$ at which Achilles overtakes the tortoise, we find
\begin{align}
x_a(t_{\ast}) = x_b(t_{\ast}) \rightarrow vt_{\ast} = x_0 + \frac{v}{2}t_{\ast} \rightarrow t_{\ast} = 2 \frac{x_0}{v}.
\end{align}
Any position captured by your sequence must have $t_n < t_{\ast}$, so it is no surprise that we find $x_a(t_n) < x_b(t_n)$ for any of your $t_n$.
A: Your modeling of the situation is incorrect, as you posit that the sets $\{a_i\}$ and $\{b_i\}$ completely describe the positions of Achilles and the Tortoise, but you have no reason to believe that to be the case.
Indeed, simply observe Achilles at any time between when the race starts and when he reaches the Tortoise's starting position. You will see that Achilles occupies a position which is not described as $a_i$ for any $i \geq 0 $.
If those sets don't completely describe the positions in the situation, then a claim that holds true for all elements of those sets (such as that $b_i > a_i$) doesn't necessarily hold for all positions in the situation.
A: It seems you are a little unsatisfied with the answers given here, so I'll try to give it a go in the hope it'll help things click. (My answer will be more or less exactly the same as the others, but in my experience with those things, a small difference in phrasing can sometimes help internalize a point).
You have proved that $b_i>a_i$ for every $i$. This is correct. But what are $a_i$ and $b_i$? They are the positions of Achilles and the tortoise, respectively, at some point in time. Let's call this point $t_i$. Then $t_i$ increases with $i$ (i.e. $t_1<t_2<t_3<t_4<...$). But this sequence is bounded. (If we knew their exact speed we could calculate what $t_i$ is for every $i$, and see what limit the sequence $(t_1,t_2,t_3,...)$ approaches, but it doesn't really matter).
The fact that each $t_i$ is rational is not important (and it's not necessarily true). What's important is that there is a point in time $T$ at which Achilles will overtake the tortoise; it's just the case (as you have shown) that necessarily $T>t_i$ for every $i$.
I hope this helps a bit, together with the other answers.
A: What is missing in the set-up is the requirement that both Achilles and Tortoise run with constant speed. If they both continually run slower and slower, for example, if each iteration takes the same amount of time, then it is possible that Achilles never catches up.
A: The paradox comes from the fact that you sample infinitely many positions $a_i,b_i$, all preceding the crossing point.
It is your own decision to pick those points, and from their very definition, the sequences do converge to the crossing point.
But that in no way tells you the whole trajectories.
A: There is nothing wrong with your proof… internal to the proof.
In respect of the universe of consideration, what is wrong with your proof is that it adopts a constrained frame of reference.  It declines to consider any value outside of the constraint that Achilles < tortoise.
In other words… as a proof… it proves that Achilles will always be behind the tortoise, given the assumption that Achilles will always be behind the tortoise.
Mathematically, the idea is to follow the approach in Sameer Baheti’s answer [noting that I have not checked the actual maths] — you allow yourself to use a different frame of reference — one that is not artificially constrained.
