Answer to popular mathematical riddle

Question

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.

Answer 1

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.

Answer 2

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$

Answer 3

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$