Formula for the first base-$n$ digit of $n^{d+1}-\sum_{i=1}^{n}i^d$

Solution 1:

Your conjecture doesn't always hold based on the stated conditions. For example, $n = 2, d = 3$ results in

$$\sum_{i=1}^{n}i^d = \sum_{i=1}^{2}i^3 = 1 + 2^3 = 9 \tag{1}\label{eq1A}$$

$$k = n^{d+1} - \sum_{i=1}^{n}i^d = 2^4 - 9 = 7 = (111)_2 \tag{2}\label{eq2B}$$

Thus, $l = 3$ and $n_l = n_3 = 1$. However,

$$n - \left\lceil\frac{\sum_{i=1}^n i^d}{n^d}\right\rceil = 2 - \left\lceil\frac{9}{2^3}\right\rceil = 2 - 2 = 0 \neq n_l = n_3 = 1 \tag{3}\label{eq3A}$$

This fails because $\frac{\sum_{i=1}^n i^d}{n^d} \gt 1$, so the ceiling result is always $\ge 2$, meaning the final result is always $\le n - 2$, but this gives $0$ for $n = 2$. However, your conjecture does work by changing the restriction to be $n \ge 3$.

Note that to prove your conjecture, it's sufficient to prove

$$\sum_{i=1}^n i^d \le n^{d+1} - n^d \; \iff \; \sum_{i=1}^{n-1} i^d \le n^{d+1} - 2n^d \tag{4}\label{eq4A}$$

The left inequality with $d = 1$ gives $\frac{n(n+1)}{2} \le n^2 - n \iff n + 1 \le 2(n - 1) \iff 3 \le n$, so it holds.

Next, consider the remaining cases of $d \ge 2$ with $n \ge 3$. Note that $i^d = \int_{i}^{i+1}i^d dx$. Since $\lfloor x \rfloor = i$ for $x \in [i, i + 1)$, we also have $i^d = \int_{i}^{i+1}(\lfloor x \rfloor)^d dx$. In addition, since for non-integral $x$ means that $\lfloor x \rfloor \lt x$, we have $\int_{i}^{i+1}(\lfloor x \rfloor)^d dx \lt \int_{i}^{i+1}x^d dx$. Using these results and summing over the various values of $i$ gives

$$\sum_{i=1}^{n-1} i^d = \int_{1}^{n}(\lfloor x \rfloor)^d dx \lt \int_{1}^{n}x^d dx = \left. \frac{x^{d+1}}{d+1} \right|_{1}^{n} = \frac{n^{d+1} - 1}{d+1} \tag{5}\label{eq5A}$$

To prove the right side of \eqref{eq4A}, it's sufficient to prove

$$\begin{equation}\begin{aligned} \frac{n^{d+1} - 1}{d+1} & \le n^{d+1} - 2n^d \\ n^{d+1} - 1 & \le (d + 1)n^{d+1} - 2(d + 1)n^d \\ -1 & \le dn^{d+1} - 2(d + 1)n^d \\ -1 & \le n^d(dn - 2d - 2) \\ -1 & \le n^d(d(n-2) - 2) \end{aligned}\end{equation}\tag{6}\label{eq6A}$$

Since $d \ge 2$ and $n \ge 3$ means $d(n-2) - 2 \ge 0$, the inequality above holds, so \eqref{eq4A} also holds. This means \eqref{eq4A} is true for all $d \ge 1$ and $n \ge 3$. Note this gives $-\sum_{i=1}^n i^d \ge - n^{d+1} + n^d \; \to \; n^{d+1} - \sum_{i=1}^n i^d \ge n^d$. Thus, $n^d \le k \lt n^{d+1}$ so, expressed in base $n$, we have $l = d + 1$ and

$$\begin{equation}\begin{aligned} n_l & = \left\lfloor \frac{k}{n^d} \right\rfloor \\ & = \left\lfloor \frac{n^{d+1} - \sum_{i=1}^n i^d}{n^d} \right\rfloor \\ & = \left\lfloor n - \frac{\sum_{i=1}^n i^d}{n^d} \right\rfloor \\ & = n + \left\lfloor -\frac{\sum_{i=1}^n i^d}{n^d} \right\rfloor \\ & = n - \left\lceil \frac{\sum_{i=1}^n i^d}{n^d} \right\rceil \end{aligned}\end{equation}\tag{7}\label{eq7A}$$

For going to the last step, note if $x$ is any integer then $\lfloor -x \rfloor = -x = -\lceil x \rceil$, while if $x$ is non-integral so $x = m + r$ with $m \in \mathbb{Z}$ and $0 \lt r \lt 1$, then $\lfloor -x \rfloor = \lfloor -m - r \rfloor = -m - 1 = -(m + 1) = -\lceil x \rceil$. Thus, for all real $x$, we have $\lfloor -x \rfloor = -\lceil x \rceil$.