# A special type of generating function for Fibonacci

Notation. Let $$[x^n]G(x)$$ be the coefficient of $$x^n$$ in the Taylor series of $$G(x)$$.

Consider the sequence of central binomial coefficients $$\binom{2n}n$$. Then there two ways to recover them: $$\binom{2n}n=[x^n]\left(\frac1{\sqrt{1-4x}}\right) \tag{1-1}$$ and $$\binom{2n}n=[x^n]\left((1+x)^2\right)^n. \tag{1-2}$$ This time, take the Fibonacci numbers $$F_n$$ then, similar to (1-1), we have $$F_n=[x^n]\left(\frac1{1-x-x^2}\right). \tag{2-1}$$ I would like to ask:

QUESTION. Does there exist a function $$F(x)$$, similar to (1-2), such that $$F_n=[x^n]\left(F(x)\right)^n? \tag{2-2}$$

• Of course I agree with the stated equalities (1-1)–(2-1), but does "In view of this" really mean (as it sounds like to me) "as a consequence", or does it just mean "Analogously"? (Maybe "In view of this" was meant to go before "I would like to ask"?) Also, in what sense is (1-1) similar to (2-1), other than that both are extracting coefficients of (fixed) ogf's? – LSpice Jan 21 at 17:20
• Does not Lagrange inversion give an equation for $F$? – Fedor Petrov Jan 21 at 18:37
• @FedorPetrov: does it give something "explicit"? – T. Amdeberhan Jan 21 at 20:26

Sure: choose any nonzero value for $$a_0$$, and write $$F(x)=a_0+a_1x+a_2x^2+...$$. Expanding $$F(x)^n$$ gives you a LINEAR equation in $$a_n$$ as a function of the preceding ones, the coefficient of $$a_n$$ being $$na_0^{n-1}$$. In the special case of Fibonacci numbers, I do not know if $$F(x)$$ is "explicit", but formally it exists.

Added: choosing $$a_0=1$$ gives you $$F(x)=1+x+x^2/2-x^3/3+x^4/8+x^5/15-25x^6/144+11x^7/70-209/5760x^8-319/2835 x^9 +...$$

and any other nonzero $$a_0$$ gives $$a_0F(x/a_0)$$.

Second addition: since some people seem interested in this expansion, two remarks. Call $$a_n$$ the coefficient of $$x^n$$. First, it must be easy to show that the denominator of $$a_n$$ divides $$n!$$ (and even $$(n-1)!$$). Second, and much more interesting, is that the numerator of $$a_n$$ seems to be always smooth, more precisely its largest prime factor never exceeds something like $$n^2$$. This is much more surprising and may indeed indicate some kind of explicit expression.

Third addition: thanks to the answers of Fedor, Richard, and Ira, it is immediate to see that $$F(x)$$ is a solution of the differential equation $$y'-1=x/y$$, giving the recurrence formula for the coefficients $$c_n$$ of $$F$$: $$\sum_{0\le n\le N}(n+1)c_{n+1}c_{N-n}-c_N=\delta_{N,1}$$ Does this help ?

• Thank you. I wish (although I did not state it) we could find something more "explicit". – T. Amdeberhan Jan 21 at 20:25
• Have you noticed that for $n=5k+1$, the prime factors of the numerators are overall even much smaller than for the other $n$'s (with the biggest one about 4 times smaller than "usual")? For $n=6,11,\dots,46,51$ the biggest prime factor is as small as $5,5,31,61,101,151,211,281,241,359$. Moreover for $n=5k+1$ those numerators seem to contain high powers of $5$, at least $5^{2k-1}$. In general, only certain primes occur, starting with $5,11,19,29,31,41,59,61,71,79,89,101,109,131,139,149,151,179,181,191,199$. Really intriguing - do those have some (class number or whatever) property in common? – Wolfgang Jan 23 at 16:50
• And here are some patterns, inspired by the sequence $31,61,101,151,211,281$ in the above comment: the numerator for $n=5k+1$ is divisible by $5k(k-1)+1$. It looks like there are many other quadratic sequences among the divisors: If $n \ne 0\pmod {11}$, it seems like the numerator is divisible by $n^2-7n+11=(n-3)(n-4)-1$, while for $n = 0\pmod {11}$, just a factor $11$ is missing. For even $n=2k$, it is divisible by $(n-4)(n-8)-1$ and most often (!) also by $k(k-1)-1$. And so on. Maybe, all prime factors can be captured by such quadratic sequences, which would explain why they are small! – Wolfgang Jan 23 at 17:59
• Wolfram alpha does give a solution to that ODE: wolframalpha.com/input/?i=D%5By%2Cx%5D+-+1+%3D+x+%2F+y – Michael Anderson Jan 24 at 3:17

Lagrange–Bürmann formula claims that $$[w^{n-1}]H'(w)(\varphi(w))^n=n[z^n]H(g(z)),$$ where $$g(z)$$ and $$f(w)=w/\varphi(w)$$ are compositionally inverse power series without constant term (that is $$g(f(w))=w$$, $$f(g(z))=z$$), $$H$$ arbitrary power series. So if you choose $$H$$ equal to the antiderivative of $$1/\varphi$$, we get $$[w^{n-1}]\varphi^{n-1}=n[z^n]H(g(z))=[z^{n-1}](H(g(z))'=[z^{n-1}]\frac{g'(z)}{\varphi(g(z))}=\\ [z^{n-1}]\frac{g'(z)f(g(z))}{g(z)}=[z^{n-1}]\frac{zg'(z)}{g(z)}.$$ So, if you look for $$\varphi$$ such that $$\sum_{n=1}^ \infty ([w^{n-1}](\varphi(w))^{n-1})z^{n-1}=u(z)$$ is a fixed function (satisfying $$u(0)=1$$), you should at first solve $$zg'(z)/g(z)=u(z)$$ that reads as $$(\log g)'=u(z)/z,\quad\log g(z)=\log z+\int_0^z \frac{u(t)-1}tdt+{\rm const},\\ g(z)=C z\exp\left(\int_0^z \frac{u(t)-1}tdt\right),$$ after that solve $$g(z)/\varphi(g(z))=z,\quad\text{i.e.}\,\, \varphi(s)=s/g^{-1}(s).$$ The choice of $$C$$ is your freedom.

You may try Fibonacci numbers, that is, $$u(z)=1/(1-z-z^2)$$. We get $$g(z)=Cz(1-\alpha z)^{-\alpha/\sqrt{5}}(1-\beta z)^{\beta/\sqrt{5}},\quad \alpha=\frac{1+\sqrt{5}}2,\,\beta=\frac{1-\sqrt{5}}2.$$ The inverse map $$g^{-1}$$ is not explicit of course. You may probably look at it as a Christoffel–Schwarz type map (inverse of antiderivative of a product $$\prod (z-z_i)^{c_i}$$, where $$c_i$$ are all equal to $$-1$$ in our case).

• A little elementary algebra then gives a nice equation for F (your $\varphi$ ): $\left( F(x) - \alpha x \right)^{\alpha} = \left( F(x) - \beta x \right)^{\beta}$ – Eigentime Jan 22 at 14:44
• @Eigentime hm, where is $C$ in this equation? – Fedor Petrov Jan 22 at 16:32
• I forgot to mention that I put $C=1$ to get the equation. From Henri Cohen's answer we see that we get the other solutions as $a F(x / a)$ – Eigentime Jan 24 at 7:47

Another way to state Fedor's answer is Exercise 5.56(a) of Enumerative Combinatorics, vol. 2. Namely, if $$G(x)=a_1x+a_2x^2+\cdots$$ is a power series (say over $$\mathbb{C}$$) with $$a_1\neq 0$$ and $$n>0$$, then $$n[x^n]\log \frac{G^{\langle -1\rangle}(x)}{x} = [x^n] \left(\frac{x}{G(x)}\right)^n,$$ where $$^{\langle -1\rangle}$$ denotes compositional inverse. Letting both sides equal the Fibonacci number $$F_n$$ (using the indexing $$F_1=F_2=1$$) gives $$F(x) =\frac{x}{\left( x\exp \sum_{n\geq 1}F_n\frac{x^n}{n} \right)^{\langle -1\rangle}}.$$ One can find a closed expression for $$\sum F_n\frac{x^n}{n}$$ by integrating $$\sum_{n\geq 1} F_nx^{n-1}=1/(1-x-x^2)$$, but there is no simple formula for the resulting compositional inverse.

Perhaps interesting to note the following.

In the notation of Henri Cohen, $$F(x)=1 + x+\frac{x^2}{\color{red} 2}-\frac{x^3}{\color{red} 3}+\frac{x^4}{\color{red}8}+\frac{x^5}{15}-\frac{25 x^6}{\color{red}{144}}+\frac{11 x^7}{70}-\frac{209 x^8}{\color{red}{5760}}-\frac{319 x^9}{2835}+\frac{8569 x^{10}}{\color{red}{44800}}-\frac{625 x^{11}}{4536}-\frac{1212751 x^{12}}{\color{red}{43545600}}+\frac{2759 x^{13}}{13650}-\frac{155302219 x^{14}}{609638400}+\dots$$

Compare this to the sequence $$\sum_{k=0}^n \frac{(-1)^k}{k!}=1,0,\frac{1}{\color{red}2},\frac{1}{\color{red}3},\frac{3}{\color{red}8},\frac{11}{30},\frac{53}{\color{red}{144}},\frac{103}{280},\frac{2119}{\color{red}{5760}},\frac{16687}{45360},\frac{16481}{\color{red}{44800}},\frac{1468457}{3991680},\frac{16019531}{\color{red}{43545600}},\frac{63633137}{172972800},\frac{2467007773}{6706022400},\dots$$

Just a coincidence? Perhaps there is a closed-form after all...

• FWIW: the coefficient of $x^{20}$ also has matching denominator with the sequence. – AccidentalFourierTransform Jan 22 at 2:37
• and in any case the denominators in the latter sequence are multiples of the denominators of the coefficients – Pietro Majer Jan 22 at 21:15
• If fitted to the denominators in the latter sequence, the numerators of $F$ become $1,1,1,-1,1,2,-25,44,-209,-5104,8569,-550000,-1212751$... maybe "smooth" in terms of prime factors, maybe growing absolute values, but with an intriguing irregularity. – Wolfgang Jan 23 at 9:51
• @Wolfgang some of these are also in A258943. – AccidentalFourierTransform Jan 24 at 0:55
• @AccidentalFourierTransform Wow, and again those not in the "exponential reversion" (never heard that term before) seem to be divisors of the corresponding entries. Fascinating relationship... – Wolfgang Jan 25 at 11:59

The power series $$F(x)$$ is closely related to the series of the "exponential reversion of Fibonacci numbers" $$R(x)=\sum_{n\ge1}r_n\frac{x^n}{n!}$$ (the $$r_n$$ are A258943, quoted in a comment). In fact it appears that, again in the notation of Henri Cohen, $$a_{n+1}=nr_n,$$ equivalently $$F'(x)=xR'(x).$$

So if the Fibonacci numbers are encapsulated by $$x=\sum_{n\ge1}F_n\frac{y^n}{n!}=y+\frac{y^2}{2!}+2\frac{y^3}{3!}+3\frac{y^4}{4!}+5\frac{y^5}{5!}+\cdots,$$ the reverse series of this is $$y=R(x)=\sum_{n\ge1}r_n\frac{x^n}{n!}=x-\frac{x^2}{2!}+\frac{x^3}{3!}+\color{red}{2}\frac{x^4}{4!}-\color{red}{25}\frac{x^5}{5!}+-\cdots,$$ while \begin{align}F(x)=1+\sum_{n\ge1}a_n {x^n} &=1 + x+\frac{x^2}{ 2!}-2\frac{x^3}{ 3!}+3\frac{x^4}{4!}+8\frac{x^5}{5!}-125\frac{x^6}{6!}+-\cdots\\ &=1 + x+\frac{x^2}{ 2!}-2\frac{x^3}{ 3!}+3\frac{x^4}{4!}+4\cdot\color{red}{2}\frac{x^5}{5!}-5\cdot\color{red}{25}\frac{x^6}{6!}+-\cdots\end{align}.

Possibly this relationship is not even specific to the Fibonacci numbers.

EDIT: It looks like the sequence $$\{a_n\}$$ has finally yielded its secrets. Given the conjectured "smoothness" of these coefficients (i.e. all prime factors are relatively small) as mentioned in Henri Cohen's answer, I have looked again into the factors and those quadratic sequences mentioned in the comments, and fortunately there are enough primes in them, such that finally I was able to find the pattern! We have for the sequence $$\{r_n\}$$ $${ r_n=\begin{cases} {(-1)^k} \prod\limits_{j=1}^k(n^2-5nj+5j^2) \quad\text{for }\ n=2k-1, \\ \\ {(-1)^kk\cdot} \prod\limits_{j=1}^{k-1}(n^2-5nj+5j^2) \quad\text{for }\ n=2k. \end{cases}}$$ Once found, it should not be hard to prove that rigorously.
As pointed out by Agno in a comment, we can reduce to linear factors and write the product in terms of the Gamma function simply as $$r_n= {\sqrt5^{ \,n-1 }\frac { \Gamma \left( \frac{5-\sqrt {5}}{10}n \right)}{ \Gamma \left( 1-\frac{5+\sqrt {5}}{10}n \right) }}.$$More generally, if we start with a Lucas sequence $$f_0=0,\ f_1=1,\ f_n=pf_{n-2}+qf_{n-1}\quad(n\ge2),$$ the reversed series has $$\boxed{r_n= {\sqrt{4p+q^2}^{ \,n-1 }\frac { \Gamma \left[\dfrac n2 \Bigl(1-\dfrac{q}{\sqrt{4p+q^2}} \Bigr)\right]}{ \Gamma \left[1-\dfrac n2 \Bigl(1+\dfrac{q}{\sqrt{4p+q^2}} \Bigr)\right]}}}.$$ Note that whenever the argument in the denominator is a negative integer, the coefficient $$r_n$$ vanishes, e.g. this happens when $$p=3,q=2$$ for all $$n\equiv0\pmod4$$.

As far as the sequence of the signs, it is after all quite regular and is in fact self-similar (that is, unless $$\sqrt{4p+q^2}$$ is rational). This self-similar behaviour of the signs can be seen by virtue of the (negative) argument of the Gamma function in the denominator, knowing that $$\Gamma$$ changes signs at each negative integer and the multiples of $$\sqrt{4p+q^2}$$ occurring in the argument do the rest. (Think e.g. of the self similarity features of the Wythoff sequence.)
For the reversion of the original Fibonacci sequence, I have displayed here the signs of the first $$1500$$ even and then the first $$1500$$ odd coefficients and found that their quasi periodicity comes out nicely when putting exactly $$76$$ in each row (writing "o" instead of "$$-$$" for better visibility). The "longest pairings" are colored:
all patterns "$$++--++--++$$" in yellow and
all patterns "$$--++--++--$$" in blue. • Very well done, Wolfgang :-) I had also started to spot a few patterns, but had not come even close to this. You should most certainly add this as a formula for the sequence A258943 on Sloane's! – Agno Feb 17 at 19:21
• @Agno indeed, I was already thinking about that 😁 – Wolfgang Feb 17 at 21:12
• Just to share two observations: 1) You could rewrite $r_n$ for $n=odd$ as a "closed" form: $${\frac {i{5}^{n/2-1/2}\pi\, \left( -1 \right) ^{n/2}}{\sin \left( 1/10 \,\pi\, \left( \sqrt {5}n+15 \right) \right) \Gamma \left( 1-n/2+1/10 \,\sqrt {5}n \right) \Gamma \left( 1-n/2-1/10\,\sqrt {5}n \right) }}$$ 2) When $n=$ a prime $>5$, then a unique property of $r_n$ is that all its prime factors are always congruent to {1, 4} mod 5 (A045468). – Agno Feb 17 at 23:03
• Note that in my previous comment I used $r_n$ as the $n$-th element of A258943, i.e it excludes the $\frac{1}{n!}$ factor. – Agno Feb 17 at 23:25
• @Agno Little typo (must be "5" instead of "15"). We can indeed write it for odd $n$ as $$r_n=\frac 1{n!}{\frac {(-5)^{(n-1)/2}\pi}{\cos\left(\frac{n\sqrt {5}}{10}\pi\right) \Gamma \left( 1-\frac{5+\sqrt {5}}{10}n \right) \Gamma \left( 1-\frac{5-\sqrt {5}}{10}n \right) }}$$ and for even $n$ $$r_n=\frac 1{n!}{\frac {-i\cdot (-5)^{(n-1)/2}\pi}{\sin \left(\frac{n\sqrt {5}}{10}\pi\right) \Gamma \left( 1-\frac{5+\sqrt {5}}{10}n \right) \Gamma \left( 1-\frac{5-\sqrt {5}}{10}n \right) }}$$ – Wolfgang Feb 18 at 10:08

I started writing this before Richard's answer appeared, with which it overlaps a lot, but I still have something to add.

Let us look at a more general problem: Suppose that $$G(x) = 1+g_1x+g_2x^2+\cdots$$ and that $$[x^m]G(x)^m = c_m$$ for $$m\ge1$$. It is clear that the $$g_i$$ can be expressed uniquely in terms of the $$c_i$$, and we would like to find an explicit formula.

Let $$R(x) = \exp\biggl(-\sum_{n=1}^\infty \frac{c_n}{n} x^n\biggr)$$ and let $$f=f(x)$$ satisfy $$f = xR(f)$$, so $$f(x) =\bigl(x/R(x)\bigr)^{\langle -1\rangle}$$.

By formula (2.2.7) of my survey paper on Lagrange inversion (a corollary of Lagrange inversion), $$[x^m](x/f)^m = c_m$$, so by the uniqueness of $$G(x)$$, we have $$G(x) = x/f(x)$$. By formula (2.2.4) of my paper (a form of Lagrange inversion) we have for $$\alpha\ne -m$$, $$[x^m] (f/x)^{\alpha}=\frac{\alpha}{m+\alpha} [x^m] R(x)^{m+\alpha}$$ so $$[x^m] G(x)^{-\alpha}=\frac{\alpha}{m+\alpha} [x^m] \exp\biggl(-(m+\alpha)\sum_{n=1}^\infty \frac{c_n}{n} x^n\biggr).$$ In particular, taking $$\alpha=-1$$ gives the formula for the coefficients of $$G(x)$$ in terms of the $$c_i$$: we have $$g_1=c_1$$ and for $$m>1$$, $$g_m=-\frac{1}{m-1} [x^m] \exp\biggl(-(m-1)\sum_{n=1}^\infty \frac{c_n}{n} x^n\biggr).$$ We can use these formulas to find some nice examples of $$[x^m]G(x)^m=c_m$$.

First take $$c_m$$ to be the constant $$C$$. Then $$R(x)=\exp(-\sum_{n=1}^\infty C x^n/n) = (1-x)^C$$, $$f$$ satisfies $$f=x(1-f)^C$$, and \begin{aligned}G(x)^{-\alpha} &= \sum_{m=0}^\infty (-1)^m\frac{\alpha}{m+\alpha} \binom{C(m+\alpha)}{m} x^m\\ &=1+\sum_{m=1}^\infty (-1)^m \frac{\alpha C}{m}\binom{C(m+\alpha)-1}{m-1}x^m. \end{aligned} In particular, if $$C=1$$ then $$f=x/(1+x)$$ and $$G=1+x$$. If $$C=-1$$ then $$f$$ is $$xc(x)$$ where $$c(x)$$ is the Catalan number generating function, $$c(x) =(1-\sqrt{1-4x})/(2x)$$, and $$G(x) = 1/c(x)$$. If $$C=2$$ then $$f=xc(-x)^2$$, so $$G(x) = c(-x)^{-2}$$.

For another example take $$c_1=-1$$ and $$c_m=0$$ for $$m>1$$. Then $$R(x) = e^{x}$$ so $$f(x)$$ is the "tree function" satisfying $$f = xe^f$$, $$G = x/f = e^{-f}$$ and $$G(x)^{-\alpha} = \sum_{m=0}^\infty \alpha (m+\alpha)^{m-1}\frac{x^m}{m!}.$$

For any desired sequence $$a_0,a_1,a_2,\cdots$$ there is a unique function (a formal power series) $$F(x)$$ with $$[x^n]F(x)=a_n$$ namely $$F(x)=\sum a_ix^i.$$

Sometimes $$F(x)$$ is a polynomial. This happens exactly when the sequence is zero from some point on. Sometimes $$F(x)$$ is a rational function. This happens exactly when the sequence satisfies a linear homogeneous recurrence relation with constant coefficients. Then the denominator is determined by the recurrence and the numerator by the initial conditions. And $$F(x)$$ might or might not be expressible in a closed form of some other given type, such as $$\frac{P(x)}{\sqrt[k]{Q(x)}}$$ for $$P,Q$$ polynomials.

You desire that there is a function $$G(x)$$ with $$[x^n](G(x)^n)=a_n$$ for all $$n$$. Again there is a unique formal power series $$G[x]=1+s_1x+s_2x^2+\cdots$$ such that $$[x^n](G(x)^n)={\large \lbrace}\begin{array}{lr} 1 & \text{for } n=0\\ a_n & \text{for } n \geq 1\\ \end{array}$$ So you need to either have $$a_0=1$$ or restrict the requirement to $$n \geq 1.$$ The unique formal power series $$G(x)$$ is relatively easy to find term by term. It might or might not be a polynomial or expressible in a closed form of some other given type.

In the case of the central binomial coefficients, $$F(x)$$ is as you give in and $$G(x)=1+2x+x^2.$$

For the Fibonacci sequence the $$F(x)$$ is a rational function but the $$G(x)$$ doesn't appear at first glance to be anything nice.