Editing Generating function (section)

====Congruences for the partition function====

In this example, we pull in some of the machinery of infinite products whose power series expansions generate the expansions of many special functions and enumerate partition functions. In particular, we recall that ''the'' [[partition function (number theory)|partition function]] {{math|''p''(''n'')}} is generated by the reciprocal infinite [[q-Pochhammer symbol|{{mvar|q}}-Pochhammer symbol]] product (or {{mvar|z}}-Pochhammer product as the case may be) given by
<math display="block">\begin{align}
\sum_{n = 0}^\infty p(n) z^n & = \frac{1}{\left(1-z\right)\left(1-z^2\right)\left(1-z^3\right) \cdots} \\[4pt]
& = 1 + z + 2z^2 + 3 z^3 + 5z^4 + 7z^5 + 11z^6 + \cdots.
\end{align}</math>

This partition function satisfies many known [[Ramanujan's congruences|congruence properties]], which notably include the following results though there are still many open questions about the forms of related integer congruences for the function:<ref>{{harvnb|Hardy|Wright|Heath-Brown|Silverman|2008|loc=§19.12}}</ref>
<math display="block">\begin{align}
p(5m+4) & \equiv 0 \pmod{5} \\
p(7m+5) & \equiv 0 \pmod{7} \\
p(11m+6) & \equiv 0 \pmod{11} \\
p(25m+24) & \equiv 0 \pmod{5^2}\,.
\end{align}</math>

We show how to use generating functions and manipulations of congruences for formal power series to give a highly elementary proof of the first of these congruences listed above.

First, we observe that in the binomial coefficient generating function
<math display="block">\frac{1}{(1-z)^5} = \sum_{i=0}^\infty \binom{4+i}{4}z^i\,,</math>
all of the coefficients are divisible by 5 except for those which correspond to the powers {{math|1, ''z''<sup>5</sup>, ''z''<sup>10</sup>, ...}} and moreover in those cases the remainder of the coefficient is 1 modulo 5.  Thus, 
<math display="block">\frac{1}{(1-z)^5} \equiv \frac{1}{1-z^5} \pmod{5}\,,</math> 
or equivalently
<math display="block"> \frac{1-z^5}{(1-z)^5} \equiv 1 \pmod{5}\,.</math>
It follows that
<math display="block">\frac{\left(1-z^5\right)\left(1-z^{10}\right)\left(1-z^{15}\right) \cdots }{\left((1-z)\left(1-z^2\right)\left(1-z^3\right) \cdots \right)^5} \equiv 1 \pmod{5}\,. </math>

Using the infinite product expansions of 
<math display="block">z \cdot \frac{\left(1-z^5\right)\left(1-z^{10}\right) \cdots }{\left(1-z\right)\left(1-z^2\right) \cdots } =
z \cdot \left((1-z)\left(1-z^2\right) \cdots \right)^4 \times \frac{\left(1-z^5\right)\left(1-z^{10}\right) \cdots }{\left(\left(1-z\right)\left(1-z^2\right) \cdots \right)^5}\,,</math>
it can be shown that the coefficient of {{math|''z''<sup>5''m'' + 5</sup>}} in {{math|''z'' · ((1 − ''z'')(1 − ''z''<sup>2</sup>)⋯)<sup>4</sup>}} is divisible by 5 for all {{mvar|m}}.<ref>{{cite book |last1=Hardy |first1=G.H. |last2=Wright |first2=E.M.|title=An Introduction to the Theory of Numbers}} p.288, Th.361</ref> Finally, since
<math display="block">\begin{align}
\sum_{n = 1}^\infty p(n-1) z^n & = \frac{z}{(1-z)\left(1-z^2\right) \cdots} \\[6px]
& = z \cdot \frac{\left(1-z^5\right)\left(1-z^{10}\right) \cdots }{(1-z)\left(1-z^2\right) \cdots } \times \left(1+z^5+z^{10}+\cdots\right)\left(1+z^{10}+z^{20}+\cdots\right) \cdots
\end{align}</math>
we may equate the coefficients of {{math|''z''<sup>5''m'' + 5</sup>}} in the previous equations to prove our desired congruence result, namely that {{math|''p''(5''m'' + 4) ≡ 0 (mod 5)}} for all {{math|''m'' ≥ 0}}.