Sequences and Generating Functions 01
kr·@yey·
0.000 HBDSequences and Generating Functions 01
<html> <p>This is just the English version of my previous post : <a href="https://steemit.com/kr/@yey/01">[수열과 생성함수 01]</a></p> <p> 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.</p> <center><img src="https://cdn.pixabay.com/photo/2015/09/13/10/06/pay-937884_640.jpg" width="640" height="426"/></center> <p><br></p> <p> 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?</p> <p> 6 (We also count this as one way.)</p> <p> 5+1 (Caution : We think 1+5 and 5+1 are the same.)</p> <p> 4+2</p> <p> 4+1+1</p> <p> 3+3</p> <p> 3+2+1</p> <p> 3+1+1+1</p> <p> 2+2+2</p> <p> 2+2+1+1</p> <p> 2+1+1+1+1</p> <p> 1+1+1+1+1+1</p> <p>Total 11 ways. Therefore, the function value p(6) of the partition function for 6 is equal to 11.</p> <p><br></p> <p> In fact, it is known that p(n) is asymptotically equal to </p> <center><img src="http://i.imgur.com/fyYwBdD.jpg" width="168" height="55"/></center> <p>as n grows, however, the problem doesn't seem to be the asking us to use that fact.</p> <p> To show the given infinite sum converges, let </p> <center><img src="http://i.imgur.com/q29nX59.jpg.jpg"/></center> <p>denote the number of ways of expressing n as a sum of <strong>three</strong> 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</p> <center><img src="http://i.imgur.com/DhYYpk7.jpg"/></center> <p>holds, we only need to show that the series</p> <center><img src="http://i.imgur.com/LibSCRj.jpg" width="111" height="63"/></center> <p>converges.</p> <p><br></p> <p> Surprisingly, we can find the general formula for computing </p> <center><img src="http://i.imgur.com/q29nX59.jpg" width="75" height="44"/></center> <p>, and this formula looks quite different from the general formulas we know, the general formula</p> <center><img src="http://i.imgur.com/m989uUZ.jpg" width="142" height="43"/></center> <p>for an arithmetic progression or the general formula</p> <center><img src="http://i.imgur.com/RR7Z2Og.jpg" width="252" height="60"/></center> <p>for the Fibonacci sequence, for instance. The value</p> <center><img src="http://i.imgur.com/q29nX59.jpg" width="75" height="44"/></center> <p>is equal to <strong>the nearest integer</strong> to </p> <center><img src="http://i.imgur.com/AXaEB4S.jpg" width="74" height="51"/></center> <p>. So, we can prove the convergence of the series</p> <center><img src="http://i.imgur.com/LibSCRj.jpg" width="111" height="63"/></center> <p>by using the direct comparison test with the well-known series</p> <center><img src="http://i.imgur.com/m5jzBUS.jpg" width="109" height="66"/></center> <p>which appears in the Basel problem.</p> <p> 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</p> <center><img src="http://i.imgur.com/q29nX59.jpg" width="75" height="44"/></center> <p>in my next post.</p> </html>