MHB Can You Solve This Sum of Floor Functions Challenge?

[anemone]

Here is next week's (23th December 2019) POTW:

-----

Evaluate $$\left\lfloor{\frac{1}{3}}\right\rfloor+\left\lfloor{\frac{2}{3}}\right\rfloor+\left\lfloor{\frac{2^2}{3}}\right\rfloor+\left\lfloor{\frac{2^3}{3}}\right\rfloor+\cdots+\left\lfloor{\frac{2^{1000}}{3}}\right\rfloor$$, without the help of a calculator.

-----

Remember to read the https://mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to https://mathhelpboards.com/forms.php?do=form&fid=2!

 

[anemone]

Congratulations to the following members for their correct solution!

1. castor28
2. kaliprasad
3. MegaMoh

Solution from castor28:

Spoiler

Let us define:

• $\displaystyle S = \sum_{k=0}^{1000}{\left\lfloor\frac{2^k}{3}\right\rfloor}$. This is the expression to be evaluated.
• $\displaystyle T = \sum_{k=0}^{999}{\left\lfloor\frac{2^k}{3}\right\rfloor}$. This is the same as $S$, without the last term.
• $\displaystyle U = \sum_{k=0}^{999}{\frac{2^k}{3}}$. This is the same as $T$ without the floor function.

$U$ is a geometric progression, with sum $\dfrac{2^{1000}-1}{3}$.

Since $2^{2k}\equiv1\pmod{3}$ and $2^{2k+1}\equiv2\pmod3$, we have:
$$
\left(\frac{2^{2k}}{3} + \frac{2^{2k+1}}{3}\right)-\left(\left\lfloor\frac{2^{2k}}{3}\right\rfloor+\left\lfloor\frac{2^{2k+1}}{3}\right\rfloor\right)=\frac13+\frac23=1
$$
As $T$ and $U$ contain $500$ such pairs of consecutive terms, we have $T = U - 500 = \dfrac{2^{1000}-1}{3}-500$.

As $ S = T + \left\lfloor\dfrac{2^{1000}}{3}\right\rfloor = T + \dfrac{2^{1000}-1}{3}$, we have $S = \dfrac{2(2^{1000}-1)}{3} - 500$.