# 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]$$

• I would start by observing that $x - 3[x/3] = (x$ mod $3)$; then look for a pattern in $2^n$ mod $3$. – Chas Brown Jun 20 '16 at 23:07
• If you add the first two terms, the next two terms, the next two terms, and so on you get $0,3,15,63,\dots$, which may suggest a pattern. – André Nicolas Jun 20 '16 at 23:17
• One can write the floor under $x$ as $\lfloor x\rfloor$, coded as \lfloor x\rfloor. If you write \left\lfloor \int_0^{}\pi/2 \tan x\,dx \right\rfloor, then the use of \left and \right makes the delimeters adapt to the size of the expression that they enclose, thus: $$\left\lfloor \int_0^{\pi/2} \tan x\,dx \right\rfloor$$ I suspect this notation for the floor function was introduced by Donald Knuth. But maybe it's older than that. Similarly \lceil \rceil. $\qquad$ – Michael Hardy Jun 20 '16 at 23:33
• @ChasBrown : $(x\bmod 3)$ is coded as x\bmod 3. The "b" is for "binary", meaning the spacing and formatting are those appropriate for binary operation symbols. $\qquad$ – Michael Hardy Jun 20 '16 at 23:35
• @Michael Hardy: Thanks; figured there was something better than what I wrote... – Chas Brown Jun 21 '16 at 5:04

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}$$

• the answer is actually (2^(101) - 152) / 3 – uzumaki Jun 20 '16 at 23:21
• @uzumaki It's very likely that that answer and the one given are the same. – MCT Jun 20 '16 at 23:23
• Using mathematica (ugh!) they are in fact numerically the same. – Kitter Catter Jun 20 '16 at 23:24
• Yes they are same, I've just calculated them bouth. If it is interesting for someone, the numerical value is $845100400152152934331135470200$. – Anton Grudkin Jun 20 '16 at 23:24
• what I wanted to convey was that, there must be some other way to get a more compact solution – uzumaki Jun 20 '16 at 23:25

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}

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.

• Is there an explanation for the recursion? Without it I would hesitate to call this an answer. – MCT Jun 20 '16 at 23:31
• @Soke Actually, I could not find the common term, and so I put the question here to find the answer. I will put the link if I get any answer. – Majid Jun 21 '16 at 0:33
• @lhf Thanks. I made the revision. – Majid Jun 21 '16 at 0:34
• @Soke you may see some answers here: math.stackexchange.com/questions/1833959/… – Majid Jun 21 '16 at 1:18
• I don't care for the explicit solution to the sequence, I was saying you ought to explain why the recursion works and not just state it because of a pattern. – MCT Jun 21 '16 at 15:10

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}