We show that explicit forms for certain polynomials~$ψ^{(a)}_m(n)$ with the property \[ ψ^{(a+1)}_m(n) = \sum_{ν=1}^n ψ_m^{(a)}(ν) \] can be found (here, $a,m,n\in\mathbb{N}_0$). We use these polynomials as a basis to express the monomials~$n^m$. Once the expansion coefficients are determined, we can express the $m$-th power sums~$S^{(a)}_m(n)$ of any order $a$, \[ S^{(a)}_m(n) = \sum_{ν_a = 1}^n \cdots \sum_{ν_2 = 1}^{ν_3} \sum_{ν_1=1}^{ν_2} ν_1^m, \] in a very convenient way by exploiting the summation property of the $ψ_m^{(a)}$, \[ S^{(a)}_m(n) = \sum_k c_{mk} ψ_k^{(a)}(n). \]