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, 2019 at 4:47
  • $\begingroup$ @IraGessel Thanks, if you post that as an answer I will accept it. $\endgroup$
    – Hood
    May 13, 2019 at 22:35

1 Answer 1


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 and acknowledge you have read our privacy policy.

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