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?
 A: 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.
$$
A: 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*}
A: 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$.
