I recently learned about Faulhaber's formula, which says that for each integer $p \geq 1,$ we can simplify the finite sum $\sum_{k \in \mathbb{N}}[k<n]k^p$ so that it becomes an (integer-valued) polynomial in the variable $n$. In fact, Faulhaber's formula tells us precisely which polynomial it becomes! I find this side of "number theory" pretty darn interesting.
(But would this even be considered number theory?)
Question. What book(s) can you recommend regarding the evaluation of finite sums of integers and/or other problems of a similar flavor? Also, what are the name(s) of the branches of mathematics that are most directly involved with such problems?
Definitely any decent book on enumerative combinatorics will have plenty of examples. For example Stanley's two volumes are great.
Polynomials actually come up in a lot of (unexpected places). A great example is Ehrhart theory, which is a vast generalization of Pick's theorem. . Take a polytope $P$ in $d$ dimensions and look at dialations $tP$. A dialation is simply a rescaling of the polytope coordinates, so say $t=2$ just doubles all coordinates. An interesting question to ask is how many integer lattice points are there contained in $P$ and $tP$? Thus we're looking at $L_P(t):=|tP\cap \mathbb{Z}^d|$, where for now $t$ is an integer. Ehrhart proved an amazing fact: $L_P(t)$ is a polynomial in $t$.
For example, plot the convex hull: $(0,2),(1,3),(4,2),(2,0)$. Then one can show: that
$$L(t)=\frac{13}{2}t^2+\frac{7}{2}t+1.$$
For example $t=1$ gives the original polygon for a total of 11 points. What's amazing is that despite having fractional coefficients, $L(t)$ always gives an integer for all $t$ (you can prove this easily for this example). More generally it really becomes like voodoo, that these polynomials always give the right answer despite having very strange forms.
Here's another example. Take the standard $d$-simplex, which is given by $\{x\in\mathbb{R}^d_{\geq 0}: \ x_1+x_2+\cdots+x_d\leq 1\}$. So basically it's the convex hull of all positive unit vectors. One can show that
$$L(t)=\binom{t+d}{d}.$$
These polynomials satisfy a large number of other properties and come up as links between enumerative combinatorics, algebraic geometry and a number of other areas.
Take a look at this link, which has a very readable overview.