How Are the Solutions for Finite Sums of Natural Numbers Derived? So, I've been learning set theory on my own (Lin, Shwu-Yeng T., and You-Feng Lin. Set Theory: An Intuitive Approach. Houghton Mifflin Co., 1974.) and have come across infinite sums of natural numbers.  Since I took Algebra II many years ago, I've known of the results of these sums for the purpose of solving summations.  (I also know of the formula (and its flaws) which states the sum of the set of natural numbers is $-1/12$).  Just for reference, I've listed six infinite series of natural numbers below (they are the six listed in the 44 year old textbook I'm using): 
$$\sum_{k=1}^{n}k=\frac{n(n+1)}{2}$$
$$\sum_{k=1}^{n}k(k+1)=\frac{n(n+1)(n+2)}{3}$$
$$\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}$$
$$\sum_{k=1}^{n}k^3=\frac{n^2(n+1)^2}{4}=\frac{n^4}{4}+\frac{n^3}{2}+\frac{n^2}{4}$$
$$\sum_{k=1}^{n}(2k-1)=n^2$$
$$\sum_{k=1}^{n}\frac{1}{k(k+1)}=\frac{n}{n+1}$$
Now that I've started learning set theory, I now know how to prove these results using mathematical induction (which admittedly, I had a lot of fun doing).  However, I still have a few questions about this. Firstly, through my own research, I found a list of mathematical series on Wikipedia, but this list does not have all the series listed in the textbook.  So, is there a list elsewhere of all series of natural numbers, and if so then where?  (Now that I think of it, what if there is an infinite amount of infinite series; although this may be the case, obviously not all of them would be practical, as many maybe could be simplified into general cases).  Second (and most important), although I know how to prove these results using mathematical induction, I do not know how to derive them.  How would one go about actually deriving such a result for an infinite series?  The method could not possibly be trial and error by using mathematical induction on random expressions.  I cannot think of a method myself at this time, but I know there must be some way of doing this.  And lastly, if you can think of a better title for the question, please let me know, since I did have trouble coming up with a suitable title.  Thank you in advance to whoever is able to help!  

For fixed $m$, write
$$
k^m=a_0\binom{k}{0}+a_1\binom{k}{1}+a_2\binom{k}{2}\dotsb+a_m\binom{k}{m}\tag{1}
$$
for some $a_i\in\mathbb{R}$. To find $a_0$, let $k=0$ in (1). Having found $a_0, a_1,\dotsc,a_{j-1}$ observe that
$$
a_j=j^m-a_0-a_1\binom{j}{1}-\dotsb-a_{j-1}\binom{j}{j-1}.\quad (j\geq 1)
$$
That the equality in (1) results from our choice of $a_i$ amounts to noticing that two polynomials of degree $m$ agree at $m+1$ points ($k=0, \dotsc, m$) and hence must be equal. In essence, we have expressed a polynomial in $k$ in terms of the binomial coefficient basis. Now recall the identity
$$
\sum_{k=0}^n\binom{k}{j}=\sum_{k=0}^n\left[\binom{k+1}{j+1}-\binom{k}{j+1}\right]
=\binom{n+1}{j+1}
$$
where we have used Pascal's identity and telescoping. Then we can write
$$
\sum_{k=0}^nk^m=\binom{n+1}{1}a_0+a_1\binom{n+1}{2}+\dotsb+a_m\binom{n+1}{m+1}.
$$
by (1) For example
$$
k=\binom{k}{1}\implies \sum_{k=0}^{n}k=\binom{n+1}{2}=\frac{n(n+1)}{2}.
$$
Similarly,
$$
k^2=\binom{k}{1}+2\binom{k}{2}\implies\sum_{k=0}^nk^2=\binom{n+1}{2}+2\binom{n+1}{3}=\frac{n(n+1)(2n+1)}{6}.
$$
Also
$$
k^3=\binom{k}{1}+6\binom{k}{2}+6\binom{k}{3}\implies\sum_{k=0}^nk^3=\binom{n+1}{2}+6\binom{n+1}{3}+6\binom{n+1}{4}=\frac{n^2(n+1)^2}4{}
$$
and so on from which computing partial sums of polynomials is immediate.
