# Answer to popular mathematical riddle

I recently run into a question that asked me to find a number $n$ if for $k$ times, $n$ has been halved and subtracted $0.5$ and, at the end, $n$ becomes $0$. I don't know if this is of any relevance but the question was about people in a bus and in every stop, half of the people plus half a person would leave the bus until the bus is empty.

Given $k$, the answer was just $2^{k-1}$, I don't quite understand how to get there, the only thing I got was:

$$\left(\sum_{i=1}^{k}\frac{n+1-2^{i-1}}{i^2}\right)+\frac{k}{2}=n$$

I would appreciate any help.

P.D.: I'm positive this is very basic to almost all of you, but I'm trying to get started in the mathematical world as I've found it to be extremely interesting.

If we count an extra person to the people in the bus, who never gets off (say, the bus driver), then we observe that exactly half of the people get off. Then it should be clearer that - including the bus driver - the numbers are always powers of two.

• Great answer I think! Note that if $u_n$ is the number at step $n$, we have $u_{n+1}=\frac{u_n}{2}-\frac{1}{2}$ and we look for $u_0$ knowing that $u_k=0$. To find a closed form for $u_n$, the usual method is to consider the fixed point $a$ of $f(x)=\frac{x}{2}-\frac{1}{2}$, and show that $v_n=u_n$ is geometric. Here, $a=-1$, so adding the driver is a very nice illustration of the general method! – Taladris May 12 '14 at 15:44
• Very nice observation, really. Thanks for the answer! @Taladris thanks for the explanation! – probablynotfranco May 12 '14 at 15:58
• I cannot edit my comment. $v_n$ should be defined as $v_n=u_n-a$. – Taladris May 12 '14 at 16:04

We will find a recurrence relation to solve the problem.

$n(k)/2 -0.5=n(k-1)$,

So,$n(k)=2n(k-1)+1$ and $n(1)=1$

Solving, we get $n(k)=2^k-1$

• Nice solution, thank you very much. If we take the number of people we start with for k iterations, halve it and substract one, we are left with the number of people with start for k-1 iterations. – probablynotfranco May 12 '14 at 16:11

For $k=1$, you just work backwards. Let the number of people for $k$ operations be $p(k)$. For $p(1)$, we are told $\frac 12p(1)-\frac 12=0$ and discover that $p(1)=1$ Now we use induction. I claim that for $k$ operations we start with $2^k-1$ people. I have shown it is true for $k=1$ Now assume it is true for $k$, that we start with $2^k-1$ people. Then $\frac 12p(k+1)-\frac 12=2^k-1$ and we can solve it to find $p(k+1)=2^{k+1}-1$

• Thanks for the answer. I have a doubt as to how did you come up with 2^k-1. Did you choose it because you see it works for 2^1-1 = 1? – probablynotfranco May 12 '14 at 16:00
• I've seen this one. To find $2^k-1$ initially, I would calculate for the first few $k$'s. Getting $1,3,7,15$ (and probably not waiting for the $15$) would convince me to try an prove it. I would then prove it this way. – Ross Millikan May 12 '14 at 21:13