For a fixed $k$ what is the value of $\sum_{l=1}^{5^m-1} \Big\lfloor \dfrac{l}{5^k}\Big \rfloor$

Question

For a fixed $k$ what is the value of $\sum_{l=1}^{5^m-1} \Big\lfloor \dfrac{l}{5^k}\Big \rfloor$

By dividing the numbers between $1$ and $5^m$ as intervals of $5^k$, I was getting the following expression:

$$\binom{5^{m-k}}{2}$$ which is not only too good to be true but it turns out it is wrong. Any suggestions on how I should approach this?

Edit: After reading through @heropup's example, I am starting to realize that I may have forgotten $5^k$ term and so the following could be correct.

$$5^k \binom{5^{m-k}}{2}$$

Does that sound correct?

Answer 1

Your original approach of doing casework on intervals works. The key (at least to my method) is to interpret $$\left\lfloor\frac{a}{b}\right\rfloor$$ as the number of positive multiples of $b$ that are less than or equal to $a,$ where $a$ and $b$ are positive integers. Your list of disjoint intervals that cover all of the $l$ is $$[1,5^k -1],[5^k, 2\cdot 5^k -1],[2\cdot 5^k,3\cdot 5^k -1],\ldots, [5^{m-k-1}\cdot 5^k,5^{m-k}\cdot 5^k -1].$$ In the first interval, none of the elements have a positive multiple of $5^k$ less than or equal to the element. For each integer in the $t^{\text{th}}$ interval for $t\ge 2$ the number of positive multiples of $5^k$ that are less than or equal to the element is $t-1.$ There are $5^k$ elements in each interval after first interval. So the answer is \begin{align*} \sum_{n=1}^{5^{m-k}-1}{5^k\cdot n} &= 5^k\cdot\sum_{n=1}^{5^{m-k}-1}{n}\\ &= 5^k \cdot \frac{(5^{m-k}-1)5^{m-k}}{2}\\ &= \frac{5^{m}\cdot (5^{m-k}-1)}{2}. \end{align*} This is the same as $5^k \cdot \binom{5^{m-k}}{2}.$

Answer 2

Try working out some small examples. Say $k = 2$ and $m = 3$. Then $$S(m,k) = \sum_{l=1}^{5^m-1} \left\lfloor \frac{l}{5^k} \right\rfloor = \sum_{l=1}^{124} \left\lfloor \frac{l}{25} \right\rfloor.$$ For $l \le 24$, the summand is zero; for $25 \le l \le 49$, the summand is $1$; and in general, for $25n \le l \le 25(n+1) - 1$, the summand equals $n$. What is the largest such $n$ for this sum? We require $25(n+1) - 1 = 124$, or $n = 4$. So, with the inclusion of an extra initial $0$ term that does not affect the value of the sum, we may write this as $$S(3,2) = \sum_{n=0}^4 \sum_{j=25n}^{25(n+1)-1} n = \sum_{n=0}^4 25n = 25\frac{4(4+1)}{2} = 250.$$ Now that we've worked out this small example, it isn't too difficult to see how to generalize it: I leave it as an exercise for you to show that, if $m > k$, $$S(m,k) = \sum_{n=0}^{5^{m-k}-1} \sum_{j=5^k n}^{5^k(n+1) - 1} n = \ldots?$$

Answer 3

If $m\le k$, that summation is 0. Now suppose that $k=1$ and $m=2$, $$\sum_{l=1}^{5^2-1}\lfloor \frac{l}{5^k}\rfloor=4(0)+5(1)+5(2)+5(3)+5(4)$$ If $k=1$ and $m=3$, $$\sum_{l=1}^{5^3-1}\lfloor \frac{l}{5^k}\rfloor=4(0)+5(1)+\cdots +5(24)$$ Try a couple of more $k$ and $m$, you should be able to generalize it.

Answer 4

Just a hint for an alternative approach.

• write $l$ in quinary base $l= a_0 5^0+a_1 5^1+ \cdots$;

• then $l / 5^k$ will introduce a quinary separator just before digit k;

• $\left\lfloor {l/5^{\,k} } \right\rfloor $ is getting rid of the fractional part;

• you are left with the sum of terms going from $0$ (you can have the sum to start from there) to $5^{m-k}-1$, each repeated $5^k$ times.