11
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ I would start by observing that $x - 3[x/3] = (x $ mod $ 3)$; then look for a pattern in $2^n$ mod $3$. $\endgroup$ – Chas Brown Jun 20 '16 at 23:07
  • 3
    $\begingroup$ 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. $\endgroup$ – André Nicolas Jun 20 '16 at 23:17
  • 3
    $\begingroup$ 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$ $\endgroup$ – Michael Hardy Jun 20 '16 at 23:33
  • 1
    $\begingroup$ @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$ $\endgroup$ – Michael Hardy Jun 20 '16 at 23:35
  • 1
    $\begingroup$ @Michael Hardy: Thanks; figured there was something better than what I wrote... $\endgroup$ – Chas Brown Jun 21 '16 at 5:04
11
$\begingroup$

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

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

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}

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is there an explanation for the recursion? Without it I would hesitate to call this an answer. $\endgroup$ – MCT Jun 20 '16 at 23:31
  • $\begingroup$ @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. $\endgroup$ – Majid Jun 21 '16 at 0:33
  • $\begingroup$ @lhf Thanks. I made the revision. $\endgroup$ – Majid Jun 21 '16 at 0:34
  • $\begingroup$ @Soke you may see some answers here: math.stackexchange.com/questions/1833959/… $\endgroup$ – Majid Jun 21 '16 at 1:18
  • $\begingroup$ 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. $\endgroup$ – MCT Jun 21 '16 at 15:10
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.