Recurrence for the number of steps required to get one ball in each box

Question

Given $n$ balls, all of which are initially in the first of $n$ numbered boxes, $a(n)$ is the number of steps required to get one ball in each box when a step consists of moving to the next box every second ball from the highest-numbered box that has more than one ball.

Not so long ago I proposed this sequence to the OEIS, where during the discussion Jon E. Schoenfield proposed a formula for $n=2^k$ (already proven here), as well as the following recurrent formula:

$$a(n)=\frac{n(n-1)}{2}-b(n)$$ $$b(n)=[n>3](b\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+c\left(\left\lceil\frac{n}{2}\right\rceil-2\right)+\left\lfloor\frac{n}{2}\right\rfloor-1)$$

Here $c(n)$ is A181132, i.e., $c(0)=0$; thereafter $c(n) = $ total number of $0$'s in binary expansions of $1, \cdots, n$.

It looks very likely that this formula is correct. To verify it one may use this PARI prog:

a(n)=my(A, B, v); v=vector(n, i, 0); v[1]=n; A=0; while(v[n]==0, B=n; while(v[B]<2, B--); v[B+1]+=v[B]\2; v[B]-=v[B]\2; A++); A
c(n)=n + sum(k=1, n, logint(k, 2) - hammingweight(k))
b(n)=if(n>3, b(n\2) + c(ceil(n/2) - 2) + n\2 - 1)
a1(n)=n*(n-1)/2 - b(n)

Is there a way to prove it?

Answer 1

Generalise $a$: $a(n, k)$ is the number of steps to perform this process with $n+k$ boxes and balls starting with $n \ge 1$ balls in the first box and one ball each in the next $k$ boxes. Then the original $a(n)$ is $a(n, 0)$.

Clearly $a(1, k) = 0$. If $n > 1$ then we propagate $\lfloor \tfrac n2 \rfloor$ balls right one box, process that tail, and then return to the head. So we have $$a(n, k) = \begin{cases} 0 & \textrm{if } n = 1 \\ 1 + a(\lfloor \tfrac n2 \rfloor, 0) + a(\lceil \tfrac n2 \rceil, \lfloor \tfrac n2 \rfloor) & \textrm{if } n > 1 \wedge k = 0 \\ 1 + a(1+\lfloor \tfrac n2 \rfloor, k-1) + a(\lceil \tfrac n2 \rceil, k + \lfloor \tfrac n2 \rfloor) & \textrm{if } n > 1 \wedge k > 0 \end{cases}$$

---

If we were to propagate the balls one at a time, it's easy to see that we would require $\frac{n(n-1)}2$ steps. Therefore if we define $b(n, k) = \frac{n(n-1)}2 - a(n, k)$ it counts the total "excess" over one ball per group of the groups propagated. Using the same structural argument as for the cases of $a(n,k)$ we therefore find

$$b(n, k) = \begin{cases} 0 & \textrm{if } n = 1 \\ \lfloor \tfrac n2 \rfloor - 1 + b(\lfloor \tfrac n2 \rfloor, 0) + b(\lceil \tfrac n2 \rceil, \lfloor \tfrac n2 \rfloor) & \textrm{if } n > 1 \wedge k = 0 \\ \lfloor \tfrac n2 \rfloor - 1 + b(1+\lfloor \tfrac n2 \rfloor, k-1) + b(\lceil \tfrac n2 \rceil, k + \lfloor \tfrac n2 \rfloor) & \textrm{if } n > 1 \wedge k > 0 \end{cases}$$

Then the conjecture is equivalent to $$b(\lceil \tfrac n2 \rceil, \lfloor \tfrac n2 \rfloor) \stackrel?= c(\lceil \tfrac n2 \rceil - 2)$$

---

$c(m)$ is noted in https://oeis.org/A181132 to have recurrence (which I've relabelled)

$$c(m) = \begin{cases} 0 & \textrm{if } m = 0 \\ c(j) + c(j-1) + j & \textrm{if } m = 2j \\ c(j) + c(j) + j & \textrm{if } m = 2j+1 \end{cases}$$

which we could rewrite as $$c(n) = \begin{cases} 0 & \textrm{if } n = 0 \\ c(\lfloor \tfrac n2 \rfloor) + c(\lceil \tfrac n2 \rceil - 1) + \lfloor \tfrac n2 \rfloor & \textrm{otherwise} \end{cases}$$

---

Finally, we prove by strong induction over $n$ that $$\forall n > 1, k \ge \lfloor \log_2 n \rfloor - 1 : b(n, k) = c(n - 2)$$

Base cases: $n \in \{2,3\}$. We only ever propagate one ball at a time, so $b(2, k) = b(3, k) = 0$.

Inductive step: let $n \ge 4$ and suppose the given property holds for all $n' < n$. Let $k \ge \lfloor \log_2 n \rfloor - 1$. Then $$\begin{eqnarray*}b(n, k) &=& \lfloor \tfrac n2 \rfloor - 1 + b(1+\lfloor \tfrac n2 \rfloor, k-1) + b(\lceil \tfrac n2 \rceil, k + \lfloor \tfrac n2 \rfloor) \\ &=& \lfloor \tfrac n2 \rfloor - 1 + c(\lfloor \tfrac n2 \rfloor - 1) + c(\lceil \tfrac n2 \rceil - 2) \\ &=& c(n - 2) \end{eqnarray*}$$ as desired.

---

Going beyond what was asked in the question, this then lets us derive $$b(n) = b(\lfloor \tfrac n2 \rfloor) + c(n-2) - c(\lfloor \tfrac n2 \rfloor - 1)$$ from which, by induction, we have $$b(n) = c(n-1) - \sum_{a \ge 0} \textrm{A080791}\left(\left\lfloor \frac n{2^a} \right\rfloor - 1\right)$$ where A080791 is the sequence summed by $c$.