Bound for sum of $a^k$ for $a$ coprime to $b$ and less than $b / 2$ Given integers $b > 2$ and $k \ge 1$, I want to find a bound for the sum
$$
\sum_{\substack{a = 1 \\ \gcd(a, b) = 1}}^{\lfloor b / 2 \rfloor}
a^k,
$$
for which I conjecture that this is bounded by
$$
\int_0^{b / 2} x^k \,\mathrm{d}x
\;=\;
\frac{(b / 2)^{k + 1}}{k + 1}.
$$
If $b$ is even, then half of the possible terms in the summand disappear, and thus for such $b$ the conjecture should hold. Moving over to odd $b$, we have
$$
\sum_{\substack{a = 1 \\ \gcd(a, b) = 1}}^{\lfloor b / 2 \rfloor}
a^k
\;\le\;
\sum_{a = 1}^{(b - 1) / 2}
a^k.
$$
One could expand this last expression using Faulhaber's formula, but that does not give anything that appears to be useful. I have tried induction on odd $b$ (i.e. induction on $r$ for $b = 2 r + 1$), which work out fine for the base case $b = 3$. However, assuming the induction hypothesis I need to show that
$$
\frac{1}{k + 1}
\sum_{j = 0}^k \binom{k + 1}{j} (b / 2)^j
\;\ge\;
\Bigl( \frac{b + 1}{2} \Bigr)^k,
$$
which I am not able to.
How can I proceed? Or does my conjecture not hold? By numerical evaluation, it appears to hold for at least $b \le 1000$ and $k \le 100$.
(I know that I can (1) bound the sum by $\int_1^{\lfloor b / 2 \rfloor + 1} x^k \mathrm{d} x$ and also (2) bound the sum by introducing the Möbius function after using Faulhaber's formula to obtain sums of the divisor function. However, these expressions will not help me as much as the conjectured bound.)
 A: Since the problem that this originates from allows me to choose $b$, I will for this answer let $k$ be given.
The case $k = 1$ can be proven by ease since $\sum_{k = 1}^n k$ has a simple formula, and so I will proceed assuming that $k \ge 2$.
Assume that we have odd $b$ and let $n = (b - 1) / 2$. Then
$$
\sum_{\substack{a = 1 \\ \gcd(a, b) = 1}}^{\lfloor b / 2 \rfloor}
a^k
\;\le\;
\sum_{a = 1}^n
a^k,
$$
where we want to show that this is less than
$$
\frac{
(n + 1 / 2)^{k + 1}
}{
k + 1
}
.
$$
By the binomial theorem and Faulhaber's formula, we equivalently want to show that
$$
\frac{1}{2^{k + 1}}
+
\sum_{j = 2}^k
\binom{k + 1}{j}
n^{k + 1 - j}\;
\biggl( \frac{1}{2^j} - B_j \biggr)
\;\ge\;
0
.
$$
Here
\begin{align*}
\frac{1}{2^2} - B_2 &= \frac{1}{12}
\\
\frac{1}{2^3} - B_3 &= \frac{1}{8}
\\
\frac{1}{2^4} - B_4 &= \frac{23}{240}
\\
\frac{1}{2^5} - B_5 &= \frac{1}{32}
\\
\frac{1}{2^6} - B_6 &= -\frac{11}{1344}
\\
&\;\;\vdots
\end{align*}
and for big enough $n$ this should hold. However, since $B_j$ grows in magnitude as $j$ gets bigger, bigger $k$ implicates that bigger $n$ might be needed.
