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:

$$\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.

share|improve this question

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! –  franco_caceres 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

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. –  franco_caceres May 12 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$

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? –  franco_caceres 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

Your Answer

 
discard

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.