<s>[INST] Why is $\sum_{r=1}^n r^{\overline{a+1}}(r+b)=\big(\sum_{r=1}^n r^{\overline{a+1}}\big)\big(An+B\big)$? 
Why is 
  $$\sum_{r=1}^n r^{\overline{a+1}}(r+b)=\bigg(\sum_{r=1}^n r^{\overline{a+1}}\bigg)\bigg(An+B\bigg)=\frac{n^{\overline{a+2}}}{a+2}\cdot (An+B)$$
  where $A, B$ are rational numbers?
  ?

It is clear that LHS is a polynomial in $n$ of order  $a+3$, but that does not necesarily imply that $\sum_{r=1}^n r^{\overline{a+1}}$ is a factor.

By extension, is it true that
  $$\sum_{r=1}^n r^{\overline{a+1}}P(r)=\bigg(\sum_{r=1}^n r^{\overline{a+1}}\bigg)Q(n)=\frac{n^{\overline{a+2}}}{a+2}\cdot Q(n)$$
  where $P(\cdot), Q(\cdot)$ are polynomials of the same degree?

 [/INST] $$\begin{align}
\sum_{r=1}^n r^{\overline{a+1}}(r+b)
&=\sum_{r=1}^n r^{\overline{a+1}}(r+a+1)+ r^{\overline{a+1}}(b-a-1)\\
&=\sum_{r=1}^n r^{\overline{a+2}}+(b-a-1)\sum_{r=1}^n r^{\overline{a+1}}\\
&=\frac {n^{\overline{a+3}}}{a+3}+(b-a-1)\cdot \frac {n^{\overline{a+2}}}{a+2}\\
&=(n+a+2)\cdot \frac {a+2}{a+3}\cdot \frac {n^{\overline{a+2}}}{a+2}+(b-a-1)\cdot \frac{n^{\overline{a+2}}}{a+2}\\
&=\frac {n^{\overline{a+2}}}{a+2}\;\;\left[(n+a+2)\cdot \frac {a+2}{a+3}+(b-a-1)\right]\\
&=\frac {n^{\overline{a+2}}}{a+2}\;\;\left[\frac {a+2}{a+3}n+\frac {(a+2)^2-(a+1)(a+3)+b(a+3)}{a+3}\right]\\
&=\frac {n^{\overline{a+2}}}{a+2}\;\;\bigg[\underbrace{\frac {a+2}{a+3}}_A n+\underbrace{b+\frac 1{a+3}}_B\bigg]\\
&\equiv\left(\sum_{r=1}^n r^{\overline{a+1}}\right)\ \bigg(An+B\bigg)
\end{align}$$

For the general case, using consider the case where $P(\cdot)$ is of degree $m$, i.e. 
$$P(r)=r^m+\lambda_1 r^{m-1}\lambda_2 r^{m-2}+\cdots +\lambda_m$$
This can be converted to a factorial polynomial of the same degree, i.e. 
$$P(r)=r^\overline{m}+\mu_1 r^\overline{m-1}+\mu_2 r^\overline{m-2}+\cdots+\mu_m$$
Hence 
$$\begin{align}\sum_{r=1}^n r^\overline{a+1}P(r)
&=     \sum_{r=1}^n  r^\overline{a+m+1}
+\mu_1 r^\overline{a+m}
+\mu_2 r^\overline{a+m-1}
+\cdots
+\mu_m r^\overline{a+1}\\
&=\frac {n^\overline{a+m+2}}{a+m+2}
+\mu_1 \frac {n^\overline{a+m+1}}{a+m+1}
+\mu_2 \frac {n^\overline{a+m}}{a+m+1}+\cdots
+\mu_m \frac {n^\overline{a+2}}{a+2}\\
&=\frac {n^\overline{a+2}}{a+2}\cdot Q(n)
\end{align}$$
since $\frac {n^\overline{a+2}}{a+2}$ is a factor of $\frac {n^\overline{a+i}}{a+i}$ for $i=3,4,5,\cdots, m+1$.
</s>