Let $p$ be a prime and suppose that $g(t)$ is the generating function $g(t) = 1/p\,g(t)^p + t$ with low order terms $g(t) = t + O(t^p)$. An easy induction shows that the coefficient of $t^n$ in $g(t)$ is zero unless $n\equiv 1\pmod{p-1}$. I need to show that the $p$-adic valuation of $[t^n] g(t)$ is equal to $-v(n!)$ when $n\equiv 1\pmod{p-1}$.

Expanded out, the recurrence says that

$\displaystyle f(n) = 1/p \sum_{a_1+\cdots + a_p = n} \prod_{i} f(i)$

When $p=3$, this sequence starts

$\displaystyle t+\frac{t^3}{3}+\frac{t^5}{3}+\frac{4 \, t^7}{9}+\frac{55 \,t^9}{81}+\frac{91 \,t^{11}}{81}+\frac{476 \,t^{13}}{243}+\frac{2584 \,t^{15}}{729}+\frac{4807 \,t^{17}}{729}+O(t^{19})$.

Does anyone have any suggestions for how to check this?

  • 6
    $\begingroup$ By Lagrange inversion, $$g(t) = \sum_{j=0}^\infty \frac{1}{p^j(pj+1)}\binom{pj+1}{j} t^{(p-1)j+1}.$$ $\endgroup$ – Ira Gessel May 13 at 4:47
  • $\begingroup$ @IraGessel Thanks, if you post that as an answer I will accept it. $\endgroup$ – Hood May 13 at 22:35

Let $g(t) = th(t^{p-1}/p)$. Then the functional equation for $g(t)$ gives $h(z) =1+zh(z)^p$. It is well known that the coefficients of $h(z)$ are given by $$h(z) = \sum_{j=0}^\infty \frac{1}{pj+1}\binom{pj+1}{j}z^j.$$ This can be proved by Lagrange inversion or in other ways. These number are sometimes called Fuss-Catalan numbers and they can be found in the OEIS as A062993 or A070914.

It follows that $$g(t) = \sum_{j=0}^\infty \frac{1}{p^j(pj+1)}\binom{pj+1}{j}t^{(p-1)j+1}.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.