alternate deletion of integers between 1 and 128, which is the last one? Math question: 

Write all numbers between 1 and 128 in line. Then begin to delete the
  numbers in this way: delete number 1, leave 2, delete 3, leave 4 and
  so on. Go on to the end of the line and then begin to delete in the
  other direction from the first number not deleted, then leave the
  second and so on. Go on like this until there is only one number left.
  What is this number?

Now, I have an easy solution for this problem. The point is that I have read a different solution which seems cleaner and interesting but which I don't fully understand.
Here the solution which I do not understand:

Let $x_k$ be the last remaining number after proceeding as described
  with the numbers between $1$ and $2^k$. If you proceed with numbers
  between $1$ and $2^{k+1}$, after the first iteration remain only the
  $2^k$ even numbers, and the following $k$ iterations select the even
  number in position $x_k$ counting from the bottom ($x_k^{th}$ even number from the bottom). 
  So we have 
  $$
x_{k+1}=2(2^k-x_k+1)=2^{k+1}-2x_k+2
$$
  Knowing that $x_0=1$, we can easily obtain $x_1$, $x_2$, ..., $x_7$.
  So $x_7=86$ is the solution.

Now my problem is how to motivate the step from $2^k$ to $2^{k+1}$. Any clue?
 A: The recurrence relation
\begin{align*}
x_{k+1}&=\color{blue}{2}(2^k-x_k+1)\qquad\qquad\qquad (k\geq 0)\tag{1}\\
x_0&=1
\end{align*}
can be derived by considering two different situations.

First game: $1,2,\ldots,2^k$:
  
  
*
  
*In this game we start with the numbers $1,2,\ldots 2^k$. We play the game till we find after $k$ steps the element $x_k\in\{1,2,\ldots,2^k\}$.
  

We can now relate the solution $x_k$ from the first game with the solution $x_{k+1}$ in a game consisting of the numbers $1,2,\ldots,2^{k+1}$.

Second game: $1,2,\ldots,2^{k+1}$:
  
  
*
  
*The first step is to eliminate all odd numbers, leaving $2^k$ numbers $2,4,\ldots,2^{k+1}$.
  
*Now we are in a situation very similar to the first game. We have $2^k$ numbers, but there are two differences. Each element is doubled in size and we start from the other side with element $2^{k+1}=2\cdot 2^k$ since this is the second step in this game. 
  
  
*
  
*We have $2^k$ numbers, namely $2,4,6,\ldots,2^{k+1}$, each number twice as big as in the first game. This explains the factor $\color{blue}{2}$ in (1) marked in blue.
  
*The position $x_k$ which was derived in the first game when starting from $1$ has to be exchanged with $2^k-x_k+1$ which is the corresponding position when starting from the other side.

This explains the recurrence relation (1) giving:
\begin{align*}
(x_k)_{k\geq 0}=(1,2,2,6,6,22,22,\color{blue}{86},86,342,342,\ldots)
\end{align*}
A: The binary representation method used elsewhere works more smoothly if we first subtract $1$ from each number so now they go from $0$ to $127$ -- better rendered as $0000000$ to $1111111$ base two.  Now the bits in each place alternate between $0$ and $1$ with equal length blocks of identical bits in each place value (one-number blocks in the ones bit, two-number blocks in the twos bit, etc). This guarantees that all numbers removed in the first step have $0$ in the ones bit, those removed in the second step (in reverse order) have $1$ in the twos bit, all numbers removed in the third step have $0$ in the fours bit,  and so on in this alternating fashion.  The number with the surviving bits after seven deletions is $1010101_2$.  Adding $1$ to restore the original sequence of numbers and translating back to base ten gives $86$ as the winner.
