Proving that this algorithm distributes a quantity as expected

Question

Background (non-essential)

Let $Q$ be an integer quantity (of say, marbles) to be distributed into $n$ buckets ($B_1$ ... $B_n$) according to weights. Let $w_1$ ... $w_n$ be the non-negative weights, e.g. 100, 0, 28.4, ...

The algorithm someone has proposed to do this is:

1. Find the sum of the weights: $\sum_{j=1}^n{w_j}$
2. Use the obvious formula to determine how much goes to bucket 1: $$B_1 = \frac{Q\cdot w_1}{\sum_{j=1}^n{w_j}}$$
3. Now, instead of using the obvious formula for bucket 2, reduce the quantity to discount the just-now-allocated amount, reduce the sum of the weights to de-represent the just-now-allocated bucket, and only then use the obvious formula: $$B_2 = \frac{(Q-B_1)\cdot w_2}{(\sum_{j=1}^n{w_j})-w_1}$$
4. And so on for the following buckets.

You might wonder we wouldn't just use the obvious formula for all the buckets. The quick answer is that our actual problem is a little more involved, for example needing to distribute in rounded lots (e.g. multiples of 100 marbles) and buckets having minimum requirements (e.g. at least 100 marbles, even if weight doesn't justify). This method of making a bucket "disappear" once it's been given it's marbles, somehow appears to simplify the algorithm quite a bit (compared to other two- or three-pass proposals).

But, I'm reluctant to believe it's distributing correctly, i.e. just as the "obvious formula" would have distributed across the buckets, until I see an algebraic equivalence. So that's what I sought to prove or disprove, and I'm having trouble.

Question

Here's the "obvious formula":

$$B_i = \frac{Q\cdot w_i}{\sum_{j=1}^n{w_j}}$$

Here's our proposed formula (note the sum from $i$, not $1$):

$$ \hat{B}_i = \begin{cases} B_1 & i=1 \\ \frac{(Q-\hat{B}_{(i-1)})\cdot w_i}{\sum_{j=i}^n{w_j}} & i > 1 \end{cases} $$

Are they equivalent?

$$B_i\equiv\hat{B}_i$$

When I think of it intuitively, it seems absolutely correct, again, by picturing it as removing a bucket that's no longer in consideration, and appropriately adjusting the sum of the weights. But my algebraic manipulations keep ending up with growing polynomial expansions that won't simplify.

Answer 1

This is a candidate for induction. The base case is rather trivial, since both formulas are the same for $n=2$.
Proceed by using the $n=2$ and the $n=k$ case to prove the $k+1$ case.

---

WLOG assume $\sum_{k=1}^N \omega_i = 1$.
Let $Q_k := Q - \sum_{i=1}^{k-1} B_i$. We want to demonstrate that the sequences $$B_k := \omega_k Q_k \left(\sum_{i=k}^N \omega_i\right)^{-1}$$ and $$C_k := \omega_k Q$$ are identical.

We prove by induction on $N$, starting at the first nontrivial case $N=2$: $$B_1 = \omega_1 Q_1 / (\omega_1 + \omega_2) = \omega_1 Q = C_1 \qquad \checkmark$$ $$B_2 = \omega_2 Q_2 / \omega_2 = Q_2 = Q - B_1 = (1-\omega_1) Q = \omega_2 Q \qquad \checkmark$$

Now assume the hypothesis holds for $n < N$. Chose $\omega'$ such that $$\begin{align*} \omega'_i & = \omega_i \qquad 1\le i\le N-2\\ \omega'_{N-1} & = \omega_{N-1} + \omega_N \end{align*}$$ Since $B_k$ and $C_k$ only depend on the sum of the weigths of indices $>k$, the so generated sequences $B'_k$ and $C'_k$ coincide with $B_k$ and $C_k$ for $1\le k \le N-2$ by construction. All we need to show now is that the last elements also match. $$B_{N-1} = \omega_{N-1} Q_{N-1}/(\omega_{N-1} + \omega_N)\\ B_N = Q_N = Q_{N-1} - B_{N-1} = (1-\frac{\omega_{N-1}}{\omega_{N-1}+\omega_N})Q_{N-1} = \omega_N Q_{N-1} /(\omega_{N-1}+\omega_N)$$ The final step is thus to show $$Q = Q_{N-1}/(\omega_{N-1} + \omega_N)$$ This is simple, however: $$Q_{N-1} = Q - \sum_{i=1}^{N-2} B_i \stackrel{i.H.}= Q - \sum_{i=1}^{N-2} \omega_i Q = Q\left(1-\sum_{i=1}^{N-2} \omega_i\right) = Q(\omega_{N-1}+\omega_N)$$ Q.E.D.

Answer 2

EDIT: I thought I proved this by induction but upon writing things out I realize I can't. Can someone point out if I'm making an algebraic error somewhere?

---

As per @AlexR's suggestions, here I show

\begin{align} B_i=\hat{B}_i \end{align}

by induction. The case of $i=1$ is already given by definition. We show the truth of the case $i=2$ as the basis step for induction:

\begin{align} B_2&=\hat{B}_2\\ \frac{Q\cdot w_2}{\sum_{j=1}^n{w_j}}&=\frac{\left(Q-\hat{B}_{(2-1)}\right)\cdot w_2}{\sum_{j=2}^n{w_j}}\\ \frac{Q\cdot w_2}{\sum_{j=1}^n{w_j}}&=\frac{\left(Q-\frac{Q\cdot w_1}{\sum_{j=1}^n{w_j}}\right)\cdot w_2}{\sum_{j=2}^n{w_j}}\\ \frac{Q\cdot w_2}{\sum_{j=1}^n{w_j}}&=\left(1-\frac{w_1}{\sum_{j=1}^n{w_j}}\right)\frac{Q\cdot w_2}{\sum_{j=2}^n{w_j}}\\ \frac{1}{\sum_{j=1}^n{w_j}}&=\left(1-\frac{w_1}{\sum_{j=1}^n{w_j}}\right)\frac{1}{\sum_{j=1}^n{w_j}-w_1}\\ \frac{\sum_{j=1}^n{w_j}-w_1}{\sum_{j=1}^n{w_j}}&=\left(1-\frac{w_1}{\sum_{j=1}^n{w_j}}\right)\\ 1-\frac{w_1}{\sum_{j=1}^n{w_j}}&=\left(1-\frac{w_1}{\sum_{j=1}^n{w_j}}\right) \end{align}

Finally, we assume the case to be true for $i=k$ and show the case for $i=k+1$ to also be true:

\begin{align} B_{k+1}&=\hat{B}_{k+1}\\ \frac{Q\cdot w_{k+1}}{\sum_{j=1}^n{w_j}}&=\frac{\left(Q-\hat{B}_{(k)}\right)\cdot w_{k+1}}{\sum_{j=k+1}^n{w_j}}\\ \frac{Q\cdot w_{k+1}}{\sum_{j=1}^n{w_j}}&=\frac{\left(Q-\frac{Q\cdot w_k}{\sum_{j=1}^n{w_j}}\right)\cdot w_{k+1}}{\sum_{j=k+1}^n{w_j}}\\ \frac{Q\cdot w_{k+1}}{\sum_{j=1}^n{w_j}}&=\left(1-\frac{w_k}{\sum_{j=1}^n{w_j}}\right)\frac{Q\cdot w_{k+1}}{\sum_{j={k+1}}^n{w_j}}\\ \frac{1}{\sum_{j=1}^n{w_j}}&=\left(1-\frac{w_k}{\sum_{j=1}^n{w_j}}\right)\frac{1}{\sum_{j=1}^n{w_j}-\sum_{j=1}^k{w_j}}\\ \frac{\sum_{j=1}^n{w_j}-\sum_{j=1}^k{w_j}}{\sum_{j=1}^n{w_j}}&=\left(1-\frac{w_k}{\sum_{j=1}^n{w_j}}\right)\\ 1-\frac{\sum_{j=1}^k{w_j}}{\sum_{j=1}^n{w_j}}&\not=\left(1-\frac{w_k}{\sum_{j=1}^n{w_j}}\right) \end{align}