Tuesday, March 5, 2019

summation - 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!


Answer



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



enter image description here




and also



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



can be derived by a similar trick in 3D



enter image description here



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...