# The asymptotic behavior of a recurrence related to stable matchings

I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows:

$$a_1 = 1, a_2 = 2$$ $$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$

Apparently, Knuth was able to prove that the sequence grows at least like $$2.28^n$$. Unfortunately, any hint of the proof seems to be lost or never published, as all reference cite "personal communication". I'd like to know the rationale.

While I don't need to know the sequence exactly, lower order terms have some importance. For example, the difference between a growth rate of $$n^{\Omega(1)} c^n$$ verses $$c^n / n^{\Omega(1)}$$ would be significant (although I think I have a proof sketch that the first case is impossible, it would be nice to check). I'm also interested in the initial conditions $$a_1=2, a_2=7$$.

So far, I've mostly just tried playing around the with generating function of the sequence, but I haven't gotten anywhere. A reference for applying generating function techniques to recurrence problems involving squares etc. of previous terms would be appreciated! I'm not sure what other techniques would be useful.

Background: [1] introduced a family of stable marriage instances which provide the best known lower bounds for the maximum number of stable matchings possible for some problem instance. [2] is the first source I could find to mention the number $$2.28$$. [3] generalizes the family created in [1] somewhat but doesn't do better than $$2.28^n$$.

[1] Irving, Robert W., and Paul Leather. "The complexity of counting stable marriages." SIAM Journal on Computing 15.3 (1986): 655-667.

[2] Pittel, Boris. “On Likely Solutions of a Stable Marriage Problem.” The Annals of Applied Probability, vol. 2, no. 2, 1992, pp. 358–401. JSTOR, www.jstor.org/stable/2959755.

[3] Edward G Thurber. Concerning the maximum number of stable matchings in the stable marriage problem.Discrete Mathematics, 248(1-3):195–219, 2002.

## Solution

I wrote up Professor Shor's solution here!

• The sequence $a_1=2$, $a_2 = 7$ grows like $s^n$ for a different value of $s$. Empirically, it seems to be around 4.19. – Peter Shor Aug 7 at 18:13

Here is a proof. Parts of the proof involve some real analysis; I've sketched the details in an appendix, and if you know real analysis, you should be able to fill in the details fairly easily.

First, let's notice that for $$b_n=a_{2^n}$$, we have the recurrence

$$b_n = 3b_{n-1}^2 - 2b_{n-2}^4.$$

Now, let's assume that $$b_n = r s^{2^n}$$. The equation becomes

$$r s^{2^n} = 3 r^2 s^{2^n} - 2 r^4 s^{2^n},$$

and $$s^{2^n}$$ factors out. Solving the equation $$r = 3r^2 - 2r^4$$, we find two positive roots, $$r = 0.366 = \frac{1}{2}(\sqrt{3}-1)$$ and $$r= 1$$. Let $$r_0$$ be the smaller of these roots.

Suppose we could show that $$\frac{b_{n-1}^2}{b_n} = r_0$$. Then we can show by induction that $$b_n=r_0 s^{2^n}$$ for some value of $$s$$. Suppose this is true for some value $$n$$. Then \begin{align} b_{n+1} &= \frac{b_{n}^2}{r_0} = \frac{\left(r_0 s^{2^n}\right)^2}{r_0} = r_0 s^{2^{n+1}}. \end{align}

In fact, we won't quite show this; what we will show is that $$\frac{b_{n-1}^2}{b_n}$$ goes to $$r_0$$ as $$n$$ goes to $$\infty$$. With some analysis (given in an appendix), we can complete the proof that $$b \approx r_0 s^{2^n}$$ for some value of $$s$$. The actual value of $$s$$ depends on the initial conditions, and the only way I know to get it is computationally. Maple seems to say that $$s$$ is around 2.280142. If you start with $$a_1=2$$, $$a_2=7$$, Maple gives $$s \approx$$ 4.189425.

Why does $$\frac{b_{n-1}^2}{b_n}$$ go to $$r_0$$? Take the recurrence, and divide $$b_{n-1}^2$$ by both sides. This gives

$$\frac{b_{n-1}^2}{b_n} = \frac{1}{3-2\left(\frac{b_{n-2}^2}{b_{n-1}}\right)^2},$$ or, letting $$t_n = b_{n-1}^2/b_n$$, $$t_n=\frac{1}{3-2 t_{n-1}^2}.$$ This has three fixed points, but the only attractive point is $$r_0$$, and $$t_n$$ approaches this point from any initial value except the two other fixed points.

Appendix:

Here is a sketch of the argument that if $$\lim_{n\rightarrow \infty} t_n = r_0$$, then $$s$$ exists. We'll consider an approximation to $$s$$ based on $$b_n$$. Let $$s_n = \left(\frac{b_n}{r_0}\right)^{\frac{1}{2^n}}.$$ Then $$\frac{s_n}{s_{n-1}} = \left(\frac{b_n}{r_0}\right)^{\frac{1}{2^n}}\left(\frac{r_0}{b_{n-1}}\right)^{\frac{2}{2^{n}}} = \left( \frac{b_nr_0}{b_{n-1}^2}\right)^{\frac{1}{2^n}} = \left( \frac{r_0}{t_n}\right)^{\frac{1}{2^{n}}} .$$ If $$\lim_{n \rightarrow \infty} t_n = r_0$$, this equation implies that $$\prod_{m=n}^\infty \frac{s_{m+1}}{s_m} \rightarrow 1 \quad \mathrm{as} \quad n \rightarrow \infty,$$ and thus that $$s =\lim_{n\rightarrow \infty} s_n$$ exists.

But in order to show that $$b_n$$ grows like $$r_0 s^{2^n}$$ as $$n \rightarrow \infty$$, you need not just that $$s_n$$ converges, but that it converges quickly. The exponent on $$\frac{r_0}{t_n}$$ above takes care of that. What we would like to show is that $$\lim_{n\rightarrow\infty} \frac{s^{2^n}}{s_n^{2^n}} = 1.$$

But $$\frac{s^{2^n}}{s_n^{2^n}} = \prod_{m=n}^{\infty} \left(\frac{s_{m+1}}{s_m}\right)^{2^{n}} = \prod_{m=n}^{\infty} \left(\frac{r_0}{t_{m+1}}\right)^{\frac{1}{2^{m+1}}2^{n}} \approx \left(\frac{r_0}{t_{n}}\right)^{2^n\left(\sum\limits_{m=n}^\infty \frac{1}{2^{m+1}}\right)}= \frac{r_0}{t_n},$$ which goes to $$1$$ as $$n \rightarrow \infty$$.

• Brilliant! Thanks a lot Professor Shor. Mind if I type this up in a bit more detail and add it to the OEIS page on the sequence? oeis.org/A005154 – Clay Thomas Aug 8 at 18:42
• @Clay: Please do. Also, I didn't write it up, but you can get rigorous bounds on how far off the estimate 2.280142 is using these techniques; this estimate was obtained from the formula $𝑏_𝑛 \approx 𝑟_0𝑠^{2^𝑛}$, and you can show that it converges to $s$ really fast. – Peter Shor Aug 8 at 19:00
• @Clay: Specifically, my last equation lets you find out how estimate how far the estimate for $s$ (2.280142) is off. You could easily get many more decimal places. – Peter Shor Aug 9 at 12:36
• Ah I see. We have both a recurrence for $t_n$ and $s_n = s_{n-1} (r_0 / t_n)^{1/2^n}$ allowing us to easily calculate $s$, and we know that $s_n \ge s \ge s_n (r_0 / t_n)^{1/2^n}$, giving very fast (at least $(1 + O(1/2^n)$) convergence! – Clay Thomas Aug 9 at 15:13