show that $$\large \sum\limits_{i=0}^{\infty} \left\lfloor \frac{n+2^i}{2^{i+1}}\right\rfloor = n$$

for all positive integers $n$

Question

show that $$\large \sum\limits_{i=0}^{\infty} \left\lfloor \frac{n+2^i}{2^{i+1}}\right\rfloor = n$$

for all positive integers $n$

empty · Answer

Interesting I want to think about this, don't reveal the answer or anything!

ganeshie8 · Answer

Okay :) I wont say a word because I don't really have a proof for this
I have been working on this for a while though, hopelessly..

empty · Answer

Oh in that case tell me everything you know, I thought this was like something you had some clever answer to, but now it sounds like we're gonna need all the help we can get to figure this out.

ganeshie8 · Answer

I tried to see if this has some connection to the legendre formula for highest exponent of a prime in the prime factorization of $n!$ http://www.artofproblemsolving.com/wiki/index.php/Legendre's_Formula couldn't use it to my advantage, so i paused on this and trying to use greatest integer function properties and induction

empty · Answer

It seems like it's related to counting in base 2.

empty · Answer

Yeah Legendre's actually sounds like a great idea! I just don't know how to make that work either hmm...

ganeshie8 · Answer

yeah the successive divisions by 2 clearly has something got to do with base2, but again the numerator expression is not constant.. so its a bit complicated

empty · Answer

I'm trying to see if there's a pattern in here, also where did you find this problem just out of curiosity? https://www.desmos.com/calculator/sydso2ebqk

empty · Answer

We can lower the bound to a finite number. By separating the two terms on top, we can see that these terms will be 0.

$$\frac{n}{2^{i+1}} < \frac{1}{2}$$
$$\log_2(n)<i$$

So maybe this helps us out to write it this way: 
$$n=\sum_{i=0}^{\lfloor \log_2(n) \rfloor} \left\lfloor \frac{n+2^i}{2^{i+1}}  \right\rfloor$$

empty · Answer

I am also looking at this, but it seems to take us nowhere interesting:

$$a+b=\sum_{i=0}^{\infty} \left\lfloor \frac{a+b+2^i}{2^{i+1}}  \right\rfloor=\sum_{i=0}^{\infty} \left\lfloor \frac{a+2^i}{2^{i+1}}  \right\rfloor+\left\lfloor \frac{b+2^i}{2^{i+1}}  \right\rfloor$$

ganeshie8 · Answer

that animation looks interesting, this is from bs grewal's advanced mathematics practice problems

ganeshie8 · Answer

Adding to that, can we use below consecutive integers property to our advantage
Let $$S_n =\sum\limits_{i=0}^{\infty} \left\lfloor \frac{n+2^i}{2^{i+1}}\right\rfloor $$

Clearly $S_1=1$, so it should be sufficient to show that $$S_{n+1}-S_n = 1$$