MathLabs

Problem 6

Let [x][x] denote the greatest integer not exceeding xx. If nn is a positive integer, express [n+12]+[n+24]+[n+48]+⋯[\frac{n+1}{2}]+[\frac{n+2}{4}]+[\frac{n+4}{8}]+\cdots as a function of nn.
Step 4 of 5: Telescope finitely
Previous stepNext step
∑k=0N[n+2k2k+1]=n−[n2N+1]\sum_{k=0}^{N}\left[\frac{n+2^k}{2^{k+1}}\right]=n-\left[\frac n{2^{N+1}}\right]
Detailed analysis

Summing the differences from k=0k=0 to NN leaves the first floor [n]=n[n]=n minus the last floor [n/2N+1][n/2^{N+1}].