9
$\begingroup$

I want a closed form for the sum $$S=\sum_{k=0}^n a^k \left\lfloor\frac{k}{p}\right\rfloor$$ where: $a\ne 1<p<n;\quad p\in\mathbb Z$

I know a related identity,

$$\quad\displaystyle \sum_{k=0}^n\left\lfloor\frac{k}{p}\right\rfloor=\left(n+1-\frac{p}{2}\right)\left\lfloor\frac{n}{p}\right\rfloor-\frac{p}{2}\left\lfloor\frac{n}{p}\right\rfloor^2\quad\;,$$

but I can't apply it to this problem!

Result for this sum:

$$\quad\displaystyle S=\dfrac{a^{n+1}}{a-1}\left\lfloor\frac{n+1}{p}\right\rfloor-\dfrac{a^p\left(a^{p\left\lfloor\frac{n+1}{p}\right\rfloor}-1\right)}{(a-1)(a^p-1)}$$

Can you prove it?

$\endgroup$
  • 1
    $\begingroup$ The related identity is not for a part of the sum; it’s for a different but somewhat similar sum. That’s why I changed the wording when I fixed the English. I displayed the formulas, because it makes them easier to read. $\endgroup$ – Brian M. Scott Jun 8 '15 at 16:46
  • $\begingroup$ You’re welcome. It looks like an interesting problem, though maybe not very easy. $\endgroup$ – Brian M. Scott Jun 8 '15 at 16:50
5
$\begingroup$

Write $n=cp+r$, with $c,r\in\mathbb N\cup\{0\}$, and $r<p$. Then, for $k\leq n$, $$ \left\lfloor\frac kp\right\rfloor=\begin{cases}0,&\ 0\leq k<p\\ 1,&\ p\leq k<2p,\\ \vdots\\ m,&\ mp\leq k<(m+1)p\\ \vdots\\ c,&\ cp\leq k\leq n \end{cases} $$ Then $$ S=\sum_{k=0}^na^k\,\left\lfloor\frac kp\right\rfloor=\sum_{m=0}^{c-1}\sum_{k=mp}^{(m+1)p-1}ma^k\,+\sum_{k=cp}^{n}ca^k =\sum_{m=1}^{c-1}m\,\sum_{k=mp}^{(m+1)p-1}a^k\,+\sum_{k=cp}^{n}ca^k\\ =\sum_{m=1}^{c-1}m\,\frac{a^{mp}-a^{(m+1)p}}{1-a}+c\,\frac{a^{cp}-a^{n+1}}{1-a}. $$ Note that in the first sum, if we put together the negative term for index $m$ and the positive for $m+1$, we get $$ -ma^{(m+1)p}+(m+1)a^{(m+1)p}=a^{(m+1)p}. $$ So $$ (1-a)S=\sum_{m=1}^ca^{mp}-ca^{n+1}=\frac{a^p-a^{(c+1)p}}{1-a^p}-ca^{n+1}, $$ or $$ S=\frac{ca^{n+1}}{a-1}-\frac{a^{(c+1)p}-a^p}{(a^p-1)(a-1)}=\frac{ca^{n+1}}{a-1}-\frac{a^p(a^{pc}-1)}{(a^p-1)(a-1)}. $$ Where $$ c=\left\lfloor \frac np\right\rfloor. $$

$\endgroup$
  • $\begingroup$ $c=\left\lfloor\dfrac{n}{p}\right\rfloor$ is correct? $\endgroup$ – hxthanh Jun 8 '15 at 17:35
  • $\begingroup$ While $c=\left\lfloor\dfrac{n+1}{p}\right\rfloor$ is corrected! Tested with $(a,p,n)=(2,3,5)$ $\endgroup$ – hxthanh Jun 8 '15 at 17:36
  • $\begingroup$ I spent the last 10 minutes testing numerically with both values of $c$, and I couldn't find an example where they differ. Not saying that it doesn't exist; it might be I'm just bad as thinking of combinations, but I tried many. $\endgroup$ – Martin Argerami Jun 8 '15 at 17:37
  • $\begingroup$ In particular, with $(2,3,5)$ both formulas work. $\endgroup$ – Martin Argerami Jun 8 '15 at 17:38
  • 1
    $\begingroup$ If anyone wants to fiddle with the two values of c, here is a simple script that performs the calculations. $\endgroup$ – Martin Argerami Jun 8 '15 at 19:14
3
$\begingroup$

My Solution

Apply the Summation by parts, we have: \begin{align*} S=\sum_{k=1}^n a^k\left\lfloor\dfrac{k}{p}\right\rfloor&=\dfrac{1}{a-1}\sum_{k=1}^n\left\lfloor\dfrac{k}{p}\right\rfloor\Delta(a^k) \\ &= \left.\dfrac{1}{a-1}\cdot a^k\left\lfloor\dfrac{k}{p}\right\rfloor\right|_{k=1}^{n+1}-\dfrac{1}{a-1}\sum_{k=1}^n a^{k+1}\left(\left\lfloor\dfrac{k+1}{p}\right\rfloor-\left\lfloor\dfrac{k}{p}\right\rfloor\right) \\ &= \dfrac{a^{n+1}}{a-1}\left\lfloor\dfrac{n+1}{p}\right\rfloor-\dfrac{1}{a-1}\sum_{k=1}^n a^{k+1}\left(\left\lfloor\dfrac{k+1}{p}\right\rfloor-\left\lfloor\dfrac{k}{p}\right\rfloor\right)\end{align*}

Note that: $\left\lfloor\dfrac{k+1}{p}\right\rfloor-\left\lfloor\dfrac{k}{p}\right\rfloor=\begin{cases}1,\quad p\mid k+1\\0,\quad p\nmid k+1\end{cases}=\begin{cases}1,\quad k=mp-1\\0,\quad otherwise\end{cases}$

Therefore: \begin{align*}S&=\dfrac{a^{n+1}}{a-1}\left\lfloor\dfrac{n+1}{p}\right\rfloor-\dfrac{1}{a-1}\sum_{1\le mp-1\le n} a^{mp}\\ &=\dfrac{a^{n+1}}{a-1}\left\lfloor\dfrac{n+1}{p}\right\rfloor-\dfrac{1}{a-1}\sum_{m=1}^{\left\lfloor\frac{n+1}{p}\right\rfloor} \dfrac{a^{p(m+1)}-a^{pm}}{a^p-1} \\&= \dfrac{a^{n+1}}{a-1}\left\lfloor\dfrac{n+1}{p}\right\rfloor-\dfrac{1}{(a-1)(a^p-1)}\sum_{m=1}^{\left\lfloor\frac{n+1}{p}\right\rfloor} \Delta[a^{pm}] \\ &= \dfrac{a^{n+1}}{a-1}\left\lfloor\dfrac{n+1}{p}\right\rfloor-\left.\dfrac{a^{pm}}{(a-1)(a^p-1)}\right|_{m=1}^{\left\lfloor\frac{n+1}{p}\right\rfloor+1}\\&= \dfrac{a^{n+1}}{a-1}\left\lfloor\dfrac{n+1}{p}\right\rfloor-\dfrac{a^p\left(a^{p\left\lfloor\frac{n+1}{p}\right\rfloor}-1\right)}{(a-1)(a^p-1)}\end{align*}

$\endgroup$
  • $\begingroup$ (+1) for using Abel's summation by parts that can make wonders. $\endgroup$ – Sachpazis Stelios Jan 14 '17 at 14:40
1
$\begingroup$

Call the sum above $S_n$ for clarity.

When $n=pm-1$ then $$S_{pm-1} = \sum_{l=0}^{m-1} \left(la^{lp}\sum_{i=0}^{p-1} a^i\right) = \frac{a^p-1}{a-1}\sum_{l=0}^{m-1}la^{lp}$$

You can find the closed form for $\sum_{l=0}^{m-1}la^{lp}$.

When $n=pm-1+j$ with $j=0,1,p-1$ - that is $m=\left\lfloor\frac{n+1}{p}\right\rfloor$ and $j=n-pm+1$, then:

$$S_m = S_{pm-1} + m\sum_{k=0}^{j-1} a^{pm+k}=S_{pm-1}+ma^{pm}\frac{a^j-1}{a-1}$$

So you finally only need a closed form for $\sum_{l=0}^{m-1}lz^l$, which is $z$ times the derivative of $\frac{z^{m}-1}{z-1}$. Then substituted $z=a^p$.

$\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.