How Are the Solutions for Finite Sums of Natural Numbers Derived?

Question

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!

Answer 1

Note that

$$\sum_{k=1}^{n}k=\frac{n(n+1)}{2}$$

is a classical result which can be easily proved by the following trick

and also

$$\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}$$

can be derived by a similar trick in 3D

Note that

$$\sum_{k=1}^{n}k(k+1)=\frac{n(n+1)(n+2)}{3}=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}$$

is simply

$$\sum_{k=1}^{n}k(k+1)=\sum_{k=1}^{n}k^2+\sum_{k=1}^{n}k$$

and

$$\sum_{k=1}^{n}(2k-1)=n^2$$

is

$$\sum_{k=1}^{n}(2k-1)=2\sum_{k=1}^{n} k -\sum_{k=1}^{n} 1=2\left(\sum_{k=1}^{n} k\right) - n$$

More in general this kind of sums can be computated by Faulhaber's formula and can be derived one from the previous by a nice telescopic trick.

For example for $\sum k^2$ note that

$$(k+1)^3-k^3=3k^2+3k+1 \implies n^3-1=3\sum_{k=1}^{n} k^2+3 \sum_{k=1}^{n} k +n $$

from which $\sum_{k=1}^{n} k^2$ can be derived.

The latter argument prove that $\sum_{k=1}^{n} k^m$ is expressed by a polynomial of degree $m+1$.

For the last sum $\sum_{k=1}^{n}\frac{1}{k(k+1)}=\frac{n}{n+1}$ refer to the discussion by Ross Millikan.

Answer 2

The first five of your equations all yield to the fact that the sum of a polynomial of degree $n$ is of degree $n+1$. If you collect $n+2$ points there will be only one polynomial of degree $n+1$ or less that passes through them. You can find the polynomial by many approaches, Newton interpolation being one. The last is distinct. It depends on the fact that $\frac 1{k(k+1)}=\frac 1k-\frac 1{k+1}$ and all the terms except the first cancel.

Answer 3

Judging by your examples, I interpret your "infinite series" to mean "sequence of partial sums associated with some sequence". I'll call these "partial sum expressions".

So, is there a list elsewhere of all series of natural numbers, and if so then where?

In fact, this not possible even in principle. Each partial sum expression is associated with a unique sequence $a_{(-)}:\mathbb{N}\to R$, $n\mapsto a_n$. Denote the set of all sequences with a given range $R$ by $R^{\mathbb{N}}$. Listing the elements of $R^{\mathbb{N}}$ (perhaps with repetition) would entail producing a surjection $I\twoheadrightarrow R^{\mathbb{N}}$ from some index set of natural numbers $I\subset \mathbb{N}$ (basically, an "enumeration"). But if $R$ has at least two elements, no such surjection exists!

On the other hand, we can enumerate partial sum expressions that correspond to computable sequences. I'll call these "computable partial sum expressions".

Second (and most important), although I know how to prove these results using mathematical induction...

Even if only computable partial sum expressions are considered, there is no algorithmic procedure for determining when these are equal to a given sequence. That's because such a procedure could tell us when a computable sequence is identically equal to zero—but such a procedure does not exist!

To me, the import of these results is that researching general methods of producing closed forms for partial sum expressions is a lost cause, and that instead one has no choice but to take an ad hoc approach.

Answer 4

There is a discrete analogue of calculus known as the "difference calculus" which provides a method for evaluating finite sums, analogous to the way that integrals are evaluated in calculus. Let $D$ be the forward difference operator which takes a function $f:\mathbb R \to \mathbb R$ as input and returns as output the function $Df$ defined by $$ Df(x) = f(x + 1) - f(x). $$ In calculus, integrals are evaluated using the fundamental theorem of calculus, which states that $\int_a^b f'(x) \, dx = f(b) - f(a)$ (under mild assumptions). The analogous fact in the difference calculus is that $$ \sum_{k=0}^N Df(k) = f(N+1) - f(0). $$ (You can prove this fact easily.) This fact provides a method for evaluating finite sums, analogous to the method for evaluating integrals in calculus.

In calculus, it's useful to create tables of derivatives. Similarly, when studying the difference calculus it is useful to create a table of differences:

\begin{array}{c|c} f(x)& Df(x) \\ \hline g(x) + h(x) & Dg(x) + Dh(x) \\ \hline c g(x) &c Dg(x) \\ \hline \text{constant} & 0 \\ \hline x & 1 \\ \hline x^2 & 2x + 1 \\ \hline \color{red} ? & x \\ \hline \end{array} You can easily check that the entries in this table are correct. Can you fill in the question mark?

To fill in the question mark, we must find a function whose difference is $x$. We see that the difference of $x^2$ looks kind of like $x$ but there is a "+1" and a factor of 2 that we wish were not present. We can make the "+1" go away by subtracting off a function whose difference is $1$, and we can then make the factor of 2 go away by scaling our function by $1/2$. We have discovered that if $$ \tag{$\spadesuit$} f(x) = \frac{x^2 - x}{2} $$ then $Df(x) = x$.

Now we are ready to evaluate an interesting finite sum using the fact that $\sum_{k=0}^N Df(k) = f(N+1) - f(0)$. With the particular choice of $f$ given in equation ($\spadesuit$), this fact tells us that $$ \sum_{k=0}^N k = \frac{(k+1)k}{2}. $$

That is a simple example of how to evaluate finite sums using the difference calculus. In calculus we evaluate integrals by finding antiderivatives. In the difference calculus we evaluate finite sums by finding "anti-differences". You can proceed like this to evaluate more complicated sums.

There is more to this subject, by the way. Here are some things to think about:

• What is the difference of the function $$ f(x) = x^{(n)} = x(x-1)(x-2) \cdots (x - n + 1). $$ (The quantity $x^{(n)}$ is read "$x$ fall $n$", and plays a role in the difference calculus analogous to the role of $x^n$ in calculus.)
• What is the discrete analogue of the product rule?
• What is the discrete analogue of integration by parts? (It's called "summation by parts".)
• What is the discrete analogue of the function $e^x$? (In other words, can you find a function whose difference is itself?)
• Use summation by parts to evaluate $\sum_{k=1}^N k 2^k$. (Analogously, in calculus we would use integration by parts to evaluate $\int x e^x \, dx$.)
• In calculus we write polynomials as $$ a_0 + a_1 x + a_2x^2 + \cdots + a_n x^n. $$ What is the natural way to write polynomials in the difference calculus? What is a formula for the coefficients $a_i$? (This sheds light on Newton's divided difference method for polynomial interpolation.)
• What is analogous to a power series in the difference calculus? In the difference calculus, what is the series for $2^x$? For which values of $x$ is the series valid? (Try taking $x$ to be a positive integer to recover a standard combinatorial identity.)

Answer 5

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.

Answer 6

Bernoulli numbers are used to find the sum of $k$th powers of first $n$ natural numbers. A very accessible pdf is available on https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwjSvPWxwYD8AhXymeYKHXR4DDwQFnoECBMQAw&url=https%3A%2F%2Fwww.whitman.edu%2Fdocuments%2FAcademics%2FMathematics%2F2019%2FLarson-Balof.pdf&usg=AOvVaw34ND3UpRW2suN_XsEQQX0D