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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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