# Integer partition identity

Let be $p(n,4)$ number of partitions of $n$ in parts no greater than $4$ then

$$p(13n,4)-p(n,4)={61\over4}n^3 + {35\over2}n^2 + \frac{45+3(-1)^n}{8}n$$

I can prove this identity that seems to me very interesting (In my work, still unpublished, I need 3 or 4 pages to explain it at all). If someone has any reference where is mentioned above formula lets me know, or a short proof if it is possible. See [A191698] in OEIS

-

For fixed $k$, the sequence $p(n, k)$ has generating function

$$F_k(x) = \sum_{n \ge 0} p(n, k) x^n = \frac{1}{(1 - x)(1 - x^2)...(1 - x^k)}.$$

This generating function is rational, so partial fraction decomposition gives an explicit formula for its coefficients. If this isn't covered in Wilf's generatingfunctionology, it should be covered in Flajolet and Sedgewick's Analytic Combinatorics.

A very general approach to automatically proving certain types of combinatorial identities, which I am reasonably sure handles this special case correctly, is described in Petkovsek, Wilf, and Zeilberger's A=B.

-
I have checked all books as you suggested in none of them there was not any comment about my identity. you –  Adi Dani Jul 21 '11 at 18:31
I wouldn't expect there to be. My point is that those books should cover general methods for proving identities that include this one as a special case. –  Qiaochu Yuan Jul 21 '11 at 18:32
Can you explain how to go further from generating function and explicitly get this identity. I am trying but without any results. –  Adi Dani Jul 21 '11 at 18:43
@Adi: the details are messy, but completely algorithmic. Perhaps you should try $k = 2$ first: the partial fraction decomposition is much easier to deal with in that case. Are you familiar with how to do partial fraction decompositions when the denominator has repeated roots? –  Qiaochu Yuan Jul 21 '11 at 18:45
Qiaochu: If we go that way starting at k=2 we need to proceed with case k=3 then k=4 That is the way I get formula and for that purpose I needed 4 pages. I want to know if there exists any shorter path. According to your answer the only way to get this identity is the way I have already got. –  Adi Dani Jul 21 '11 at 19:15

With regard to Qiaochu's answer, the partial fraction decomposition is messy (compared, say, to anything you'd put on a calculus exam), having 8 terms, and coefficients like 59/288. It's worked out in detail in the lovely book by Andrews and Eriksson, Integer Partitions, in Section 6.3, A formula for $p(n,4)$, pages 58-60. They give several formulas for $p(n,4)$, perhaps the simplest is $$p(n,4)={\rm\ nearest\ integer\ to\ }{(n+5)(n^2+n+22+18\left[{n\over2}\right])\over144}$$

I suppose one could use this to have a go at $q(n)=p(13n,4)-p(n,4)$. But it might be better to work directly with a generating function for $q(n)$.

-

To add to Qiaochu's answer, there is a large body of work in existence on the Partition Function. Let $P(n,k)$ denote the number of ways to write $n$ as a sum of exactly $k$ positive integers. (Similar to your $p(n,k)$ above) Then we have the recurrence relation $$P(n,k)=P(n-1,k-1)+P(n-k,k).$$ This can be solved exactly, see equations $(61)$ to $(66)$ of the Wolfram link.

-