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$
6
  • 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
    Commented Jun 20, 2016 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$ Commented Jun 20, 2016 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$ Commented Jun 20, 2016 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$ Commented Jun 20, 2016 at 23:35
  • 1
    $\begingroup$ @Michael Hardy: Thanks; figured there was something better than what I wrote... $\endgroup$
    – Chas Brown
    Commented Jun 21, 2016 at 5:04

4 Answers 4

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

$\endgroup$
7
  • $\begingroup$ the answer is actually (2^(101) - 152) / 3 $\endgroup$
    – uzumaki
    Commented Jun 20, 2016 at 23:21
  • $\begingroup$ @uzumaki It's very likely that that answer and the one given are the same. $\endgroup$
    – MT_
    Commented Jun 20, 2016 at 23:23
  • $\begingroup$ Using mathematica (ugh!) they are in fact numerically the same. $\endgroup$ Commented Jun 20, 2016 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$ Commented Jun 20, 2016 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
    Commented Jun 20, 2016 at 23:25
5
$\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.

$\endgroup$
6
  • $\begingroup$ Is there an explanation for the recursion? Without it I would hesitate to call this an answer. $\endgroup$
    – MT_
    Commented Jun 20, 2016 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
    Commented Jun 21, 2016 at 0:33
  • $\begingroup$ @lhf Thanks. I made the revision. $\endgroup$
    – Majid
    Commented Jun 21, 2016 at 0:34
  • $\begingroup$ @Soke you may see some answers here: math.stackexchange.com/questions/1833959/… $\endgroup$
    – Majid
    Commented Jun 21, 2016 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$
    – MT_
    Commented Jun 21, 2016 at 15:10
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}

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .