The series $\sum_{n=1}^\infty\frac{1}{k^{\lfloor{\log_m(n)}\rfloor}}$

Question

This may be quite simple, but I am having trouble proving the closed form of this sum.

$$S(m,k)=\sum_{n=1}^\infty\frac{1}{k^{\lfloor{\log_m(n)}\rfloor}}$$

which converges for $m \lt k$.

From experimenting, it appears that the solution is $S(m,k)=\frac{km-k}{k-m}$ but how would we prove it.

Answer 1

The point is that because of the floor function in the exponent, the sum consists of groups of equal terms which can easily be added. Specifically,

• for $n$ from $1$ to $m-1$ there are $m-1$ terms, each equal to $\frac1{k^0}=1$;
• for $n$ from $m$ to $m^2-1$ there are $m^2-m$ terms, each equal to $\frac1{k^1}$;
• for $n$ from $m^2$ to $m^3-1$ there are $m^3-m^2$ terms, each equal to $\frac1{k^2}$;
• and so on. The total turns out to be a geometric series: $$S(m,k)=(m-1)+\frac{m^2-m}{k}+\frac{m^3-m^2}{k^2}+\cdots =\frac{m-1}{1-\frac mk} =\frac{km-k}{k-m}\ .$$

Answer 2

$$S(m,k)=\sum_{n=1}^\infty\frac{1}{k^{\lfloor{\log_m(n)}\rfloor}}$$

Note that $\lfloor\log_m(n)\rfloor$ for increasing $n$ has the same value first $m^1-m^0$ times, then $m^2-m^1$ times, then $m^3-m^2$ times, etc... And those values it takes on are $0, 1, 2, \dots$.

So we can rewrite the sum:

$$S(m,k)=\sum_{n=0}^\infty \frac{m^{n+1} - m^{n}}{k^n} = \frac{km - k }{k-m}$$