Evaluate the sums $$S_n=\sum_{k\geqslant1}\lfloor n/2^k+1/2\rfloor$$
The answer key stated that for n and n-1 all the terms would be equal except for k where $$n=2^{k-1}q$$ and q is odd. This seems to me it comes from nowhere.
From high level I understand that there should be some critical $k$ value that will cause $S_n$ and $S_{n-1}$ different and that will be the only differences as well between adjacent terms. But I can get the details sorted. Could someone give me a hint here? Thanks.
Assuming $n$ is an integer.
$n = 2^{k-1}q$ means that, in $S_n$ the $k$th term is
$$\left\lfloor\frac{n}{2^k} + \frac12\right\rfloor = \left\lfloor\frac{q}{2} + \frac12\right\rfloor = \left\lfloor\frac{q+1}{2}\right\rfloor $$
while in $S_{n-1}$, the corresponding term is
$$\left\lfloor\frac{n-1}{2^k} + \frac12\right\rfloor = \left\lfloor\frac{q+1}{2} - \frac 1{2^k}\right\rfloor $$
$\frac{q+1}2$ is an integer, so these two floors are different.
For terms before the $k$th one, call that term $1\le k'<k$. In $S_n$,
$$\left\lfloor\frac{n}{2^{k'}} + \frac12\right\rfloor = \left\lfloor2^{k-1-k'}q + \frac 1{2}\right\rfloor$$
In $S_{n-1}$,
$$\left\lfloor\frac{n-1}{2^{k'}} + \frac12\right\rfloor = \left\lfloor2^{k-1-k'}q + \frac 1{2}-\frac{1}{2^{k'}}\right\rfloor$$
$2^{k-1-k'}q$ is an integer, and $\frac12 \ge \frac{1}{2^{k'}}$, so the two floors are the same.
For terms after the $k$th one, call that term $k'' > k$. In $S_n$,
$$\left\lfloor\frac{n}{2^{k''}} + \frac12\right\rfloor = \left\lfloor\frac{q}{2^{k''-k+1}} + \frac 1{2}\right\rfloor = \left\lfloor\frac{q+2^{k''-k}}{2^{k''-k+1}}\right\rfloor$$
The numerator is odd and the denominator is even, so the fraction inside the floor is not an integer. Its fractional part is at least $\frac{1}{2^{k''-k+1}}$:
$$\begin{align*} \frac{q+2^{k''-k}}{2^{k''-k+1}} &> a&a\in\mathbb Z\\ q+2^{k''-k} &> 2^{k''-k+1}a\\ q+2^{k''-k} &\ge 2^{k''-k+1}a + 1\\ \frac{q+2^{k''-k}}{2^{k''-k+1}} -a&\ge \frac{1}{2^{k''-k+1}}\\ \end{align*}$$
While in $S_{n-1}$,
$$\left\lfloor\frac{n-1}{2^{k''}} + \frac12\right\rfloor = \left\lfloor\frac{q}{2^{k''-k+1}} + \frac 1{2}-\frac{1}{2^{k''}}\right\rfloor = \left\lfloor\frac{q+2^{k''-k}}{2^{k''-k+1}}-\frac{1}{2^{k''}}\right\rfloor$$
The least fractional part mentioned above $\frac{1}{2^{k''-k+1}}\ge \frac1{2^{k''}}$, so the two floors are the same.