Find the value of $ [1/ 3] + [2/ 3] + [4/3] + [8/3] +\cdots+ [2^{100} / 3]$ Assume that [x] is the floor function. I am not able to find any patterns in the numbers obtained. Any suggestions?
$$[1/ 3] + [2/ 3] + [4/3] + [8/3] +\cdots+ [2^{100} / 3]$$
 A: 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.
A: Starting from $n=0$, even-$n =2k$ terms are $(4^k - 1)/3$ and the subsequent odd-$n = 2k+1$ terms are $2\times (4^k- 1)/3$. So overall:
\begin{align}
\sum_{k=0}^{49}\left[(1+2)\frac{4^{k} - 1}{3}\right] + \frac{4^{50}-1}{3} &= \sum_{k=0}^{49}(4^{k} - 1) + \frac{4^{50}-1}{3} \\
& = \sum_{k=0}^{49}(4^{k}) + \frac{4^{50}-1}{3}-50 \\
&=  \frac{4^{50}-1}{3}+ \frac{4^{50}-1}{3}-50 \\
&= \frac{2}{3}(4^{50}-1)-50 \\
&=845100400152152934331135470200 \tag{W|A}
\end{align}
A: Just to better asses the solution given by Kitter Catter, premised that
$$
\eqalign{
  & x = \left\lfloor x \right\rfloor  + \left\{ x \right\}  \cr 
  & \left\lfloor { - x} \right\rfloor  =  - \left\lceil x \right\rceil   \cr 
  & \left\lceil x \right\rceil  = \left\lfloor x \right\rfloor  + \left\lceil {\left\{ x \right\}} \right\rceil  \cr} 
$$
with $\left\lfloor x \right\rfloor $ being the floor, $\left\lceil x \right\rceil $ the ceil, 
and $\left\{ x \right\}$ the fractional remaining
then:
$$
\eqalign{
  & \left\lfloor {{{2^{\,n + 1} } \over 3}} \right\rfloor \quad \left| {\;0 \le n} \right.\quad  = \left\lfloor {2{{2^{\,n} } \over 3}} \right\rfloor  = \left\lfloor {2^{\,n}  - {1 \over 3}2^{\,n} } \right\rfloor  =   \cr 
  &  = 2^{\,n}  + \left\lfloor { - {{2^{\,n} } \over 3}} \right\rfloor  = 2^{\,n}  - \left\lceil {{{2^{\,n} } \over 3}} \right\rceil  = 2^{\,n}  - \left\lfloor {{{2^{\,n} } \over 3}} \right\rfloor  - \left\lceil {\left\{ {{{2^{\,n} } \over 3}} \right\}} \right\rceil  =   \cr 
  &  = 2^{\,n}  - \left\lfloor {{{2^{\,n} } \over 3}} \right\rfloor  - 1 \cr} 
$$
A: 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}$$
