I came on this sequence of generating functions on trying to count lambda terms (in lambda calculus)

$T^{\langle m+1\rangle} = \frac{T^{\langle m \rangle}(z)}{z} - (T^{\langle m\rangle}(z))^2$


$T^{\langle m\rangle}(0) = 0.$

What can be said about these functions?

I would be happy to have an expression for $T^{\langle 0\rangle}(z)$ and say something about the asymptotic behavior of the coefficients $T_{n,m}$ for

$T^{\langle m\rangle}(z) = \sum_{n=0}^{\infty}\ T_{n,m} z^n.$

  • 1
    $\begingroup$ This appears to say nothing at all about $T^{0}.$ $\endgroup$
    – Igor Rivin
    Oct 20, 2011 at 20:11
  • $\begingroup$ actually it seems to me that if you really want these $T^m(z)$ to be power series with vanishing zero degree coefficient, they have to be identically zero; I post the details as an answer (though I guess it is not the answer you want) in order to clarify what I mean. $\endgroup$ Oct 20, 2011 at 21:51
  • $\begingroup$ Something is wrong. If tdeg() denotes the tailing degree of a series (the smallest degree with nonzero coefficient), then the recurrent formula implies $$tdeg(T^{\angle m+1 \rangle}(z)) = tdeg(T^{\angle m \rangle}(z)) - 1$$ meaning that at certain point it will drop below 0. That is, for some $m$, $T^{\angle m \rangle}$ will have nonzero coefficients of negative degrees of $z$. $\endgroup$ Oct 20, 2011 at 22:37
  • $\begingroup$ unless $tdeg=\infty$, that is, all $T^m$ are identically zero, as said. $\endgroup$ Oct 21, 2011 at 7:49
  • $\begingroup$ Actually my problem was underdetermined. In my problem, I also want to say that $[z]T^{\langle m\rangle}(z) = T^{\langle m\rangle}'(0) = m.$ In other word, the coefficient of $z$ in the power serie of $T^{\langle m\rangle}(z)$ is $m$. $\endgroup$ Oct 28, 2011 at 20:49

1 Answer 1


We want all the (formal) power series $T^m(z)$ to be elements of the ideal $z\mathbb{R}[[z]]$ (which rephrases $T_{0,m}=0$). Also, the relation $T^m(z)=zT^{m+1}(z)+zT^m(z)^2$ implies that if for some $n$ we have $T^m(z)\in z^n\mathbb{R}[[z]]$ for all $m$, then also $T^m(z)\in z^{n+1}\mathbb{R}[[z]]$ for all $m$. By induction, we should conclude that the $T^m(z)$ are identically zero for all $m$..

  • 1
    $\begingroup$ Does this make some sort of philosophical statement about lambda calculus? $\endgroup$
    – Igor Rivin
    Oct 21, 2011 at 7:55

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.