A special type of generating function for Fibonacci

Question

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}$$

Answer 1

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 ?

Answer 2

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).

Answer 3

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.

Answer 4

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...

Answer 5

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.

Answer 6

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!}.$$

Answer 7

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.