# Closed form for the sum $\sum_{k=0}^n a^k \left\lfloor\frac{k}{p}\right\rfloor$

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?

• 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. – Brian M. Scott Jun 8 '15 at 16:46
• You’re welcome. It looks like an interesting problem, though maybe not very easy. – Brian M. Scott Jun 8 '15 at 16:50

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

• $c=\left\lfloor\dfrac{n}{p}\right\rfloor$ is correct? – hxthanh Jun 8 '15 at 17:35
• While $c=\left\lfloor\dfrac{n+1}{p}\right\rfloor$ is corrected! Tested with $(a,p,n)=(2,3,5)$ – hxthanh Jun 8 '15 at 17:36
• 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. – Martin Argerami Jun 8 '15 at 17:37
• In particular, with $(2,3,5)$ both formulas work. – Martin Argerami Jun 8 '15 at 17:38
• If anyone wants to fiddle with the two values of c, here is a simple script that performs the calculations. – Martin Argerami Jun 8 '15 at 19:14

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

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

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