Sequences and Generating Functions 01
This is just the English version of my previous post : [수열과 생성함수 01]
Recently, someone introduced me an interesting problem, so I'm just writing about that. The problem says, "Prove that the infinite sum of the reciprocals of the function values of the partition function for the positive integers converges," and I solved it using a quite complicated way at that time. However, luckily, I got to know an easier and more beautiful solution for that problem by some chance.
![](https://steemitimages.com/640x0/https://cdn.pixabay.com/photo/2015/09/13/10/06/pay-937884_640.jpg)
First, what does the term 'partition function' means? The function value of the partition function for a positive integer n is just the number of ways of expressing n as a sum of positive integers. Take 6 for example. How many ways are there to express 6 as a sum of positive integers?
6 (We also count this as one way.)
5+1 (Caution : We think 1+5 and 5+1 are the same.)
4+2
4+1+1
3+3
3+2+1
3+1+1+1
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1
Total 11 ways. Therefore, the function value p(6) of the partition function for 6 is equal to 11.
In fact, it is known that p(n) is asymptotically equal to
![](https://steemitimages.com/640x0/http://i.imgur.com/fyYwBdD.jpg)
as n grows, however, the problem doesn't seem to be the asking us to use that fact.
To show the given infinite sum converges, let
![](https://steemitimages.com/640x0/http://i.imgur.com/q29nX59.jpg.jpg)
denote the number of ways of expressing n as a sum of three positive integers. It is clear that the output of this function is a positive integer not greater than p(n) if n is not less than 3. Since
![](https://steemitimages.com/640x0/http://i.imgur.com/DhYYpk7.jpg)
holds, we only need to show that the series
![](https://steemitimages.com/640x0/http://i.imgur.com/LibSCRj.jpg)
converges.
Surprisingly, we can find the general formula for computing
![](https://steemitimages.com/640x0/http://i.imgur.com/q29nX59.jpg)
, and this formula looks quite different from the general formulas we know, the general formula
![](https://steemitimages.com/640x0/http://i.imgur.com/m989uUZ.jpg)
for an arithmetic progression or the general formula
![](https://steemitimages.com/640x0/http://i.imgur.com/RR7Z2Og.jpg)
for the Fibonacci sequence, for instance. The value
![](https://steemitimages.com/640x0/http://i.imgur.com/q29nX59.jpg)
is equal to the nearest integer to
![](https://steemitimages.com/640x0/http://i.imgur.com/AXaEB4S.jpg)
. So, we can prove the convergence of the series
![](https://steemitimages.com/640x0/http://i.imgur.com/LibSCRj.jpg)
by using the direct comparison test with the well-known series
![](https://steemitimages.com/640x0/http://i.imgur.com/m5jzBUS.jpg)
which appears in the Basel problem.
To avoid this post to be too long, I'll just stop here and I'll deal with the way to find the general formula for
![](https://steemitimages.com/640x0/http://i.imgur.com/q29nX59.jpg)
in my next post.
Any mathematical comments and English corrections are welcome :)
A clever way to prove it, impressive work!