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.

 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 

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 

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

holds, we only need to show that the series

converges.

 Surprisingly, we can find the general formula for computing  

, and this formula looks quite different from the general formulas we know, the general formula

for an arithmetic progression or the general formula

for the Fibonacci sequence, for instance. The value

is equal to the nearest integer to 

. So, we can prove the convergence of the series

by using the direct comparison test with the well-known series

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

in my next post.