Water and wine mixing problem

Question

This is a well-known problem involving a water barrel and a wine barrel, described here. The trick to solving the puzzle is that one need not make the calculations for each stage of the liquid movement. But if one does...

The units here are the quantity of liquid moved each time, e.g. cupfuls. At the end of each "take out/put back" movement, the amount of wine in one barrel is the same as the amount of water in the other, so we can consider just the two volumes of liquid without caring about what they are made from.

At the beginning the two volumes are $0$ and $n$, say.

After the first movement the volumes are $$\frac{n}{n+1}\text{ and }\frac{n^2}{n+1}.$$ After the second the volumes are $$\frac{n(2n)}{(n+1)^2}\text{ and }\frac{n(n^2+1)}{(n+1)^2}.$$ After the third the volumes are $$\frac{n(3n^2+1)}{(n+1)^3}\text{ and }\frac{n(n^3+3n)}{(n+1)^3}.$$ There is a pattern here suggesting that after $t$ goes the volumes are
$$\frac{n}{(n+1)^t}\sum_{k=0}^{t/2-1}{\binom{t}{t-2k}n^{2k}}$$ and $$\frac{n}{(n+1)^t}\sum_{k=0}^{t/2}{\binom{t}{t-2k-1}n^{2k+1}}.$$ As more liquid is moved the two volumes will each start to approach $\dfrac{n}{2}$.
To my question: how do we show that the two volumes above both tend to $\dfrac{n}{2}$ as $t\rightarrow\infty$?

Answer 1

If you have $\frac{n}{2}+w$ water in the water tank before a transfer, after a transfer each direction you have $\frac{n}{2}+w\frac{n-1}{n+1}$, so $w$ is driven to zero.

Answer 2

The upper limits on the summations should be $\lfloor t/2 \rfloor$ and $\lceil t/2 \rceil$, and you can simplify the binomial coefficients to get $$\frac{n}{(n+1)^t}\sum_{k=0}^{\lfloor t/2 \rfloor}\binom{t}{2k}n^{2k}\text{ and }\frac{n}{(n+1)^t}\sum_{k=0}^{\lceil t/2 \rceil}\binom{t}{2k+1}n^{2k+1}.$$

Now $$(n+1)^t = \sum_{k=0}^t \binom{t}{k}n^k\text{ and }(n-1)^t = \sum_{k=0}^t\binom{t}{k}(-1)^{t-k}n^k,$$ so $$\begin{align*} \frac12\left((n+1)^t+(n-1)^t\right) &= \frac12\sum_{k=0}^t\binom{t}{k}\left((1+(-1)^{t-k}\right)n^k\\ &= \begin{cases} \sum_{k=0}^{\lfloor t/2\rfloor}\binom{t}{2k}n^{2k},&\text{if }t\text{ is even}\\ \sum_{k=0}^{\lceil t/2\rceil}\binom{t}{2k+1}n^{2k+1},&\text{if }t\text{ is odd}, \end{cases} \end{align*}$$ and $$\begin{align*} \frac12\left((n+1)^t-(n-1)^t\right) &= \frac12\sum_{k=0}^t\binom{t}{k}\left((1-(-1)^{t-k}\right)n^k\\ &= \begin{cases} \sum_{k=0}^{\lfloor t/2\rfloor}\binom{t}{2k}n^{2k},&\text{if }t\text{ is odd}\\ \sum_{k=0}^{\lceil t/2\rceil}\binom{t}{2k+1}n^{2k+1},&\text{if }t\text{ is even}. \end{cases} \end{align*}$$

It follows that $$\sum_{k=0}^{\lfloor t/2\rfloor}\binom{t}{2k}n^{2k} = \begin{cases} \frac12\left((n+1)^t+(n-1)^t\right),&\text{if }t\text{ is even}\\ \frac12\left((n+1)^t-(n-1)^t\right),&\text{if }t\text{ is odd} \end{cases}$$

and $$\sum_{k=0}^{\lceil t/2\rceil}\binom{t}{2k+1}n^{2k+1} = \begin{cases} \frac12\left((n+1)^t+(n-1)^t\right),&\text{if }t\text{ is odd}\\ \frac12\left((n+1)^t-(n-1)^t\right),&\text{if }t\text{ is even}. \end{cases}$$

(This is a useful trick to bear in mind when you have alternate binomial coefficients.)

Thus, for every $t$ the numbers $$\frac{n}{(n+1)^t}\sum_{k=0}^{\lfloor t/2 \rfloor}\binom{t}{2k}n^{2k}\text{ and }\frac{n}{(n+1)^t}\sum_{k=0}^{\lceil t/2 \rceil}\binom{t}{2k+1}n^{2k+1}$$ are $$\frac{n}{2(n+1)^t}\left((n+1)^t+(n-1)^t\right)\text{ and }\frac{n}{2(n+1)^t}\left((n+1)^t-(n-1)^t\right)$$ in one order or the other. These are $$\frac{n}{2}\pm\left(\frac{n-1}{n+1}\right)^t = \frac{n}{2}\pm\left(1-\frac2{n+1}\right)^t,$$ which clearly approach $\dfrac{n}2$ as $n\to \infty$.

Answer 3

The sums you write can be evaluated in closed forms: $$ \frac{1}{(n+1)^t} \sum_{k=0}^{t/2} \binom{t}{t-2k} n^{2k+1} = \frac{1}{(n+1)^t} \sum_{k=0}^{t/2} \binom{t}{2k} n^{2k+1} = \frac{n}{2} \left( 1 + \frac{(1-n)^t}{(n+1)^t} \right) $$ from which the property you seek to establish is apparent.

Now to establish the formula $$ \sum_{k=0}^{t/2} \binom{t}{2k} n^{2k+1} = \sum_{k=0}^{t} \frac{1}{2}\left(1 + (-1)^k \right)\binom{t}{k} n^{k+1} = \frac{n}{2}\left( (n+1)^t + (1-n)^t \right) $$