Working on a recurrence problem, as follows: \begin{align} f(n) = \begin{cases} a, &\text{for $n=1$}\\ f(n-1)+n^k,&\text{for $n>1$} \end{cases} \end{align} After a bunch of unrolling, I found this series: $f(n) = a + 2^k + \dots + (n-1)^k + n^k$
I'm meant to prove that $f(n) \leq c(n^{k+1})$, but I am stuck at this point and don't know how to further reduce this series.
Hints: Note that $f(n) = (a-1) + \sum\limits_{j=1}^{n}j^k$. Try and show that if $k\in \mathbb{N}$, then there exists a constant $C$ such that $S_k(n):= \sum\limits_{j=1}^{n}j^k \le Cn^{k+1}$ for all $n\in \mathbb{Z}^+$. Note that $j^k \le n^k$ for each $j=1,\ldots,n$.
Once you have shown this, you should be able to show that it follows that there is some constant $c$ such that $f(n)\le cn^{k+1}$ for all $n\in \mathbb{Z}^+$. (E.g. because if $a>1$, then $a-1 \le (a-1)n^{k+1}$ for all $n\in \mathbb{Z}^+$.)