14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – LSpice Jan 21 at 17:20
  • 1
    $\begingroup$ Does not Lagrange inversion give an equation for $F$? $\endgroup$ – Fedor Petrov Jan 21 at 18:37
  • $\begingroup$ @FedorPetrov: does it give something "explicit"? $\endgroup$ – T. Amdeberhan Jan 21 at 20:26
15
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Thank you. I wish (although I did not state it) we could find something more "explicit". $\endgroup$ – T. Amdeberhan Jan 21 at 20:25
  • $\begingroup$ 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? $\endgroup$ – Wolfgang Jan 23 at 16:50
  • $\begingroup$ 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! $\endgroup$ – Wolfgang Jan 23 at 17:59
  • $\begingroup$ Wolfram alpha does give a solution to that ODE: wolframalpha.com/input/?i=D%5By%2Cx%5D+-+1+%3D+x+%2F+y $\endgroup$ – Michael Anderson Jan 24 at 3:17
11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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}$ $\endgroup$ – Eigentime Jan 22 at 14:44
  • $\begingroup$ @Eigentime hm, where is $C$ in this equation? $\endgroup$ – Fedor Petrov Jan 22 at 16:32
  • 1
    $\begingroup$ 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)$ $\endgroup$ – Eigentime Jan 24 at 7:47
11
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ FWIW: the coefficient of $x^{20}$ also has matching denominator with the sequence. $\endgroup$ – AccidentalFourierTransform Jan 22 at 2:37
  • 1
    $\begingroup$ and in any case the denominators in the latter sequence are multiples of the denominators of the coefficients $\endgroup$ – Pietro Majer Jan 22 at 21:15
  • $\begingroup$ 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. $\endgroup$ – Wolfgang Jan 23 at 9:51
  • 1
    $\begingroup$ @Wolfgang some of these are also in A258943. $\endgroup$ – AccidentalFourierTransform Jan 24 at 0:55
  • 1
    $\begingroup$ @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... $\endgroup$ – Wolfgang Jan 25 at 11:59
5
$\begingroup$

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. enter image description here

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Agno Feb 17 at 19:21
  • $\begingroup$ @Agno indeed, I was already thinking about that 😁 $\endgroup$ – Wolfgang Feb 17 at 21:12
  • $\begingroup$ 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). $\endgroup$ – Agno Feb 17 at 23:03
  • $\begingroup$ 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. $\endgroup$ – Agno Feb 17 at 23:25
  • $\begingroup$ @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) }}$$ $\endgroup$ – Wolfgang Feb 18 at 10:08
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.