0
$\begingroup$

Let us suppose the positive integers $a$, $b$ and $n$ with $a<b$. Is it possible to simplify the following sum:

$$2 \left\lfloor \frac{an}{b} \right\rfloor b + \frac{2^2}{3} \sum_{j=1}^{n-2} 3^j \left\lfloor \frac{a(n-j)}{b} \right\rfloor b $$ ?

I've found a related post: Infinite sum of floor functions but this seems quite different.

Thank you in advance.

$\endgroup$
0
$\begingroup$

Hint:

Let us leave on the side the terms and coefficient that cause no problem, to focus on

$$\sum b\lfloor\frac abk\rfloor 3^k.$$

We have $$b\lfloor\frac abk\rfloor=ak-b\{\frac abk\}=ak-ak\bmod b.$$

For the left term, which is dominant, there is a closed formula:

$$S=\sum_{k=1}^nkr^k,$$ then

$$S=\sum_{k=0}^{n-1}(k+1)r^{k+1}=r+\sum_{k=1}^n(k+1)r^{k+1}-(n+1)r^{n+1}\\ =r+rS+\sum_{k=1}^nr^{k+1}-(n+1)r^{n+1}\\ =r+rS+\frac{r^{n+2}-r^2}{r-1}-(n+1)r^{n+1}$$ from which you can deduce $S$.

For the right term, $ak\bmod b$ takes all values in range $[0,b)$, scrambled in some order, and repeating peridodically. If $n$ exceeds $b$, full periods will appear, allowing to form groups

$$G_0=\sum_{k=0}^{b-1}(ak\bmod b)r^k,$$ then

$$G_b=\sum_{k=b}^{2b-1}(ak\bmod b)r^k=\sum_{k=0}^{b-1}(ak\bmod b)r^{k+b}=r^bG_0,$$

and more generally

$$G_{mb}=r^{mb}G_0$$ that forms a geometric progression.

For the remaining terms not filling a whole period, there is nothing much better you can do than keeping the original sum.

$\endgroup$
  • $\begingroup$ Thanks very much Yves. This is very interesting. I have some questions. 1) Why you consider $\sum b\lfloor\frac abk\rfloor 3^k$? Since the exponent of $3$ shoud be different from $k$. 2) To what exactly refers the closed formula $S$? Thanks again. $\endgroup$ – Dingo13 Jul 25 '16 at 16:20
  • $\begingroup$ @Dingo13: 1) Sorry I don't get your question. 2) $S$ is for the sum of $k3^k$. $\endgroup$ – Yves Daoust Jul 25 '16 at 16:42
  • $\begingroup$ Thanks @YavesDaoust My first question was the following: My sum is $\sum_{j=1}^{n-2} 3^j \left\lfloor \frac{a(n-j)}{b} \right\rfloor b$. Your sum is $\sum_{k=1}^n b\lfloor\frac abk\rfloor 3^k$. They are different, but the results are the same? I have $j$ and $n-j$, and you $k$ at both sides. $\endgroup$ – Dingo13 Jul 25 '16 at 18:07
  • $\begingroup$ @Dingo13: just reverse the terms, this is a minor change. $\endgroup$ – Yves Daoust Jul 25 '16 at 18:51

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.