Find the value of $ [1/ 3] + [2/ 3] + [4/3] + [8/3] +\cdots+ [2^{100} / 3]$

Solution 1:

I think I have an answer. Look at $\frac{1}{3}$ in binary format and you will notice that it is $0.\overline{01}$.
This tells us something, namely that $[2^{2i}/3]+[2^{2i+1}/3] = 4^i-1$. This immediately tells me that your sum reduces to: $$\sum \limits_{i=0}^{50} [2^{2i}/3]+\sum \limits_{i=0}^{49} [2^{2i+1}/3]=\sum \limits_{i=0}^{49} [2^{2i}/3]+\sum \limits_{i=0}^{49} [2^{2i+1}/3]+[2^{100}/3]$$ $$\sum \limits_{i=0}^{49} [2^{2i}/3]+\sum \limits_{i=0}^{49} [2^{2i+1}/3]+[2^{100}/3]=\sum(4^i-1)+[2^{100}/3]=\frac{4^{50}-151}{3}+[2^{100}/3]$$

Edit 1: Added after I knew what to shoot for:
I suppose we can simplify this by noting that $4 \bmod 3 = 1$ thus $[2^{2i}/3] = \frac{2^{2i}-1}{3}$. This would give us:
$$\frac{4^{50}-151}{3}+2^{100}/3 - 1/3 = \frac{2^{101}-152}{3}$$

Edit 2: Going for a more general solution (boring but useful I guess)
Consider $m=2n+1$ odd: $$\sum \limits_{i=0} ^{2n+1} \lfloor\frac{2^i}{3}\rfloor = \sum \limits_{i=0} ^n (4^i-1) = \frac{4^{n+1}-3n-4}{3}=\frac{2^{m+1}-3\frac{m-1}{2}-4}{3} =\frac{2^{m+2}-3 m-5}{6} $$ For $m=2n$ even: $$\sum \limits_{i=0} ^{2n} \lfloor\frac{2^i}{3}\rfloor = \sum \limits_{i=0} ^{n-1} (4^i-1) + \lfloor \frac{4^n}{3} \rfloor = \frac{2^{2n+1}-3n-2}{3}=\frac{2^{m+1}-\frac{3m}{2}-2}{3}=\frac{2^{m+2}-3m-4}{6} $$

We can then rewrite this as:

$$\frac{2^{m+3}-6m-9+(-1)^{m}}{12}$$

Solution 2:

The sequence of $[2^n/3]$ for $n\in \mathbb{N}$ and $n\geq 2$ would be like this:

$$1,\ 2,\ 5,\ 10,\ 21,\ 42,\ 85,\ \cdots $$

So, comparing the numbers in the sequence successively, you may guess that it is a recursive sequence like

$a_1=1$, and for $n>1$, we have $a_n=\begin{cases} 2a_{n-1} & \text{if } n\ \text{ is even, }\\ 2a_{n-1}+1 & \text{if } n\ \text{ is odd. } \end{cases}$

Using recursion, you can find the sequence as follows: $$a_n=\frac16\left(2^{n+2}-3-(-1)^n\right)$$

Now, you just need to compute

$$\sum_{n=1}^{100}a_n$$

PS: To show why the recursion works for the sequence, we first note that $a_n=[2^{n+1}/ 3]$. Then, using binary exhibition, we have

$$\begin{align*} a_1&=1\\ a_2&=10\\ a_3&=101\\ a_4&=1010\\ a_5&=10101\;, \end{align*}$$

and then considering $\frac23=0.\overline{10}_{\text{two}}$, we have $$\begin{align*} 2\cdot\frac23&=1.\overline{01}_{\text{two}}\\ 2^2\cdot\frac23&=10.\overline{10}_{\text{two}}\\ 2^3\cdot\frac23&=101.\overline{01}_{\text{two}}\\ 2^4\cdot\frac23&=1010.\overline{10}_{\text{two}}\\ 2^5\cdot\frac23&=10101.\overline{01}_{\text{two}}\;, \end{align*}$$

and so it is concluded that

$$a_n=\left\lfloor 2^n\cdot\frac23\right\rfloor=\left\lfloor\frac{2^{n+1}}3\right\rfloor\;.$$

I should say that I get this proof from a part of a solution to another problem here, given by Brian M. Scott.