Monotonicity conjecture for the multifurcating-tree growth constants

We prove that $\gamma_{k+1}<\gamma_k$ for every integer $k\ge2$, as asserted in Doboli, Maranca and Rosenberg, Conjecture 4.8.

For fixed $k$, let $B_n$ be the maximal rank of an at-most-$k$-furcating rooted tree with $n$ leaves, in the encoding used in that paper. Its equation (10) and Theorem 4.7 give

$$\begin{aligned} B_1&=1,\\ B_n&=2-B_{n-1}\\ &\quad+\binom{B_{n-1}+k-1}{k}\quad(n\ge2), \end{aligned}$$

and

$$B_n\sim(k!)^{1/(k-1)}\gamma_k^{\,k^n}.$$

The idea is to bound $\log\gamma_k$ using just the fourth term of this recurrence. The remaining infinite tail is small enough that a coarse comparison of consecutive central binomial coefficients suffices.

1. A uniform bound for the logarithmic tail

Write $D_n=B_n-1$. Then

$$\begin{aligned} D_{n+1}&=F_k(D_n),\\ F_k(x)&=\binom{x+k}{k}-x,\\ D_2&=1,\qquad D_3=k,\\ D_4&=u_k:=\binom{2k}{k}-k. \end{aligned}$$

For $x>0$, expansion of the product gives

$$k!F_k(x)=\prod_{j=1}^k(x+j)-k!x=x^k+Q_k(x),$$

where $Q_k$ has positive coefficients. Indeed, subtraction changes only the linear coefficient, which becomes

$$k!\left(\sum_{j=1}^k\frac1j-1\right)>0.$$

Consequently, with all logarithms natural, we may write

$$\log F_k(x)=k\log x-\log(k!)+\varepsilon_k(x),$$

where

$$\begin{aligned} 0<\varepsilon_k(x) &=\log\frac{k!F_k(x)}{x^k}\\ &\le\sum_{j=1}^k\log\left(1+\frac jx\right)\\ &\le\frac{k(k+1)}{2x}. \end{aligned}$$

For every positive integer $x$ and every $k\ge2$,

$$F_k(x)\ge F_2(x)=\frac{x^2+x+2}{2}>x.$$

Here the first inequality follows because $\binom{x+k}{k}$ increases with $k$. Thus $D_n\ge u_k$ for $n\ge4$.

Put

$$\begin{aligned} c_k&=\frac{\log(k!)}{k-1},\\ a_k&=\log u_k-c_k,\\ e_k&=\frac{k(k+1)}{2(k-1)u_k}. \end{aligned}$$

Iterating the logarithmic recurrence from $D_4=u_k$ and dividing by $k^n$ yields

$$\log\gamma_k =\frac{a_k}{k^4} +\sum_{j=4}^{\infty}\frac{\varepsilon_k(D_j)}{k^{j+1}}.$$

The limit on the left is exactly the one in the source normalization: $\log D_n/k^n\to\log\gamma_k$. The series converges by the bound on $\varepsilon_k$ and $D_j\ge u_k$. Summing the geometric upper bound proves

$$\boxed{\frac{a_k}{k^4}<\log\gamma_k \le\frac{a_k+e_k}{k^4}.}$$

2. Comparing consecutive parameters for $k\ge4$

Let $C_k=\binom{2k}{k}$, so $u_k=C_k-k$. The exact ratio is

$$\frac{C_{k+1}}{C_k}=4-\frac2{k+1}.$$

For $k\ge2$ this ratio exceeds $3$, and hence

$$u_{k+1}>3C_k-(k+1)=3u_k+2k-1>3u_k.$$

Since $u_4=66\ge4\cdot2^4$, induction gives

$$u_k\ge k2^k\qquad(k\ge4).$$

Indeed, $3k\ge2(k+1)$ for $k\ge2$, so the induction step follows from $u_{k+1}>3u_k$.

Also $k!\le k^{k-1}$, so $c_k\le\log k$ and

$$a_k\ge k\log2\qquad(k\ge4).$$

The sequence $c_k$ is strictly increasing, because

$$c_{k+1}-c_k=\frac{\log(k+1)-c_k}{k}>0.$$

Using the upper bound $C_{k+1}<4C_k$, we obtain, for $k\ge4$,

$$\begin{aligned} u_{k+1}&<4(u_k+k)\\ &\le4u_k(1+2^{-k})<8u_k. \end{aligned}$$

It follows that

$$a_{k+1}-a_k<\log8=3\log2.$$

For every $j\ge4$, the lower bound on $u_j$ gives

$$e_j\le\frac{j+1}{2(j-1)2^j}\le2^{-j}.$$

In particular $e_{k+1}<\log2$; for example, $\log2=\int_1^2 dx/x>1/2$. Combining the preceding inequalities,

$$\begin{aligned} a_{k+1}+e_{k+1} &<a_k+4\log2\\ &\le a_k\left(1+\frac4k\right)\\ &<a_k\left(1+\frac1k\right)^4. \end{aligned}$$

The last inequality uses $a_k>0$ and the binomial expansion. Dividing by $(k+1)^4$ and applying the boxed tail bound proves

$$\log\gamma_{k+1}<\log\gamma_k\qquad(k\ge4).$$

3. The two remaining comparisons

The relevant exact values are

$$\begin{aligned} u_2&=4,&c_2&=\log2,\\ u_3&=17,&c_3&=\tfrac12\log6,&e_3&=\tfrac3{17},\\ u_4&=66,&c_4&=\tfrac13\log24,&e_4&=\tfrac5{99}. \end{aligned}$$

Since $\log2>1/2$, we have

$$e_3<\frac14<c_3,\qquad e_4<\frac16<c_4.$$

Thus the upper tail bounds simplify to $\log\gamma_3<\log17/81$ and $\log\gamma_4<\log66/256$.

For $k=2$, use $17<2^5$ and $80<81$:

$$\begin{aligned} \log\gamma_3 &<\frac{\log17}{81} <\frac{5\log2}{81}\\ &<\frac{\log2}{16} <\log\gamma_2. \end{aligned}$$

For $k=3$, the inequality $17/\sqrt6>5$ gives $a_3>\log5$. Since $66<5^3$ and $243<256$,

$$\begin{aligned} \log\gamma_4 &<\frac{\log66}{256} <\frac{3\log5}{256}\\ &<\frac{\log5}{81} <\log\gamma_3. \end{aligned}$$

All cases are now covered. Exponentiation yields $\gamma_{k+1}<\gamma_k$ for every integer $k\ge2$, proving Conjecture 4.8.