Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:


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.

share|improve this question
add comment

3 Answers 3

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.

share|improve this answer
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 at 15:44
Very nice observation, really. Thanks for the answer! @Taladris thanks for the explanation! –  dex May 12 at 15:58
I cannot edit my comment. $v_n$ should be defined as $v_n=u_n-a$. –  Taladris May 12 at 16:04
add comment

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$

share|improve this answer
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. –  dex May 12 at 16:11
add comment

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$

share|improve this answer
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? –  dex May 12 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 at 21:13
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.