Looking for a recurrence relation ot combinatorial way to calculate initial number

Question

A flock of birds migrating south flies above seven lakes. Half of the birds in the flock, plus half a bird(I'm guessing the initial flock contained an odd number of birds, say 5, so in the first lake $\frac{5}{2}+\frac{1}{2} =3$ left), are leaving the flock- wanting to lend in the lake below. After the seventh lake is passed- there are no birds left in the flock.
Find how many birds started the journey.
What I did: I denoted the initial number of birds with $n$ and the calculated how many birds left for each lake. It was something like that: $$(\frac{n}{2}+\frac{1}{2})+(\frac{n-(\frac{n}{2}+\frac{1}{2})}{2}+\frac{1}{2})...$$ Assuming I could sum this up and then do something, but it's way to tidious a nd naive.
Can I do it more logically, smarter and more importantly faster?
Maybe a recursion? Any tips/hint will be welcomed.

Answer 1

Just start with the last lake: Let $n_i$ be the number of birds left before coming to the $i$-th lake (so $n_0$ is the total number of birds). In other words $n_I$ is the number of birds that fly between lake $i-1$ and lake $i$. Obviously $n_8 = 0$ since there were no birds left. But

$n_8 = n_7 - (n_7/2 +1/2)$ (the half of $n_7$ plus a half left at the $7$-nth sea, so $n_7$ minus that number is still left. This recursion holds also for the rest:

$n_{i+1} = n_i - (n_i/2+1/2) = (n_i-1)/2$.

So $n_8 = 0 \implies n_7 = 1 \implies n_6 = 3 \implies \ldots$

(And I recommend trying to find an explicit formula for this sequence. Perhaps just number the indices in reverse, that might make it easier.)