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

<p>First, let's notice that for <span class="math-container">$b_n=a_{2^n}$</span>, we have the recurrence</p>

<p><span class="math-container">$$b_n = 3b_{n-1}^2 - 2b_{n-2}^4.$$</span></p>

<p>Now, let's assume that <span class="math-container">$b_n = r s^{2^n}$</span>. The equation becomes</p>

<p><span class="math-container">$$r s^{2^n} = 3 r^2 s^{2^n} - 2 r^4 s^{2^n},$$</span></p>

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

<p>Suppose we could show that <span class="math-container">$\frac{b_{n-1}^2}{b_n} = r_0$</span>. Then we can show by induction that <span class="math-container">$b_n=r_0 s^{2^n}$</span> for some value of <span class="math-container">$s$</span>. Suppose this is true for some value <span class="math-container">$n$</span>. Then
<span class="math-container">\begin{align}
b_{n+1} &amp;= \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}</span></p>

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

<p>Why does <span class="math-container">$\frac{b_{n-1}^2}{b_n}$</span> go to <span class="math-container">$r_0$</span>? Take the recurrence, and divide <span class="math-container">$b_{n-1}^2$</span> by both sides. This gives</p>

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

<p><strong>Appendix:</strong></p>

<p>Here is a sketch of the argument that if <span class="math-container">$\lim_{n\rightarrow \infty} t_n = r_0$</span>, then <span class="math-container">$s$</span> exists. We'll consider an approximation to <span class="math-container">$s$</span> based on <span class="math-container">$b_n$</span>. Let
<span class="math-container">$$s_n = \left(\frac{b_n}{r_0}\right)^{\frac{1}{2^n}}.$$</span> 
Then
<span class="math-container">$$\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}}} .
$$</span>
If <span class="math-container">$\lim_{n \rightarrow \infty} t_n = r_0$</span>, this equation implies that <span class="math-container">$$ \prod_{m=n}^\infty \frac{s_{m+1}}{s_m} \rightarrow 1 \quad \mathrm{as} \quad n \rightarrow \infty,$$</span> and thus that <span class="math-container">$s =\lim_{n\rightarrow \infty} s_n $</span> exists. </p>

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

<p>But
<span class="math-container">$$
 \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},$$</span>
which goes to <span class="math-container">$1$</span> as <span class="math-container">$n \rightarrow \infty$</span>.</p>

CC BY-SA 4.0
2019-08-08T18:42:17.347Z
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? https://oeis.org/A005154
Clay Thomas
CC BY-SA 4.0
2019-08-08T19:00:38.620Z
@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 
CC BY-SA 4.0
2019-08-09T12:36:12.440Z
@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 
CC BY-SA 4.0
2019-08-09T15:13:34.653Z
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
CC BY-SA 4.0
2019-08-07T17:55:37.923Z
2019-08-08T16:09:25.197Z
2019-08-08T16:09:25.197Z
Peter Shor 
<p>I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows:</p>

<p><span class="math-container">$$a_1 = 1, a_2 = 2$$</span>
<span class="math-container">$$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$</span></p>

<p>Apparently, Knuth was able to prove that the sequence grows at least like <span class="math-container">$2.28^n$</span>. 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.</p>

<p>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  <span class="math-container">$n^{\Omega(1)} c^n$</span> verses <span class="math-container">$c^n / n^{\Omega(1)}$</span> 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 <span class="math-container">$a_1=2, a_2=7$</span>.</p>

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

<p>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 <span class="math-container">$2.28$</span>. [3] generalizes the family created in [1] somewhat but doesn't do better than <span class="math-container">$2.28^n$</span>.</p>

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

<p>[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.</p>

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

<h2>Solution</h2>

<p>I wrote up Professor Shor's solution <a href="https://oeis.org/A005154/a005154.pdf" rel="nofollow noreferrer">here</a>!</p>

CC BY-SA 4.0
2019-08-07T18:13:04.987Z
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 
<reference-request><co.combinatorics><matching>
The asymptotic behavior of a recurrence related to stable matchings
Clay Thomas
# The asymptotic behavior of a recurrence related to stable matchings

(Asked by: username_0 on 2019-08-07)

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](https://oeis.org/A005154/a005154.pdf)!

**Tags:** reference-request, co.combinatorics, matching
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2019-08-07. Score: 10 | Accepted answer

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

> **Comments:**
> **username_0**: 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? https://oeis.org/A005154  
> **username_1**: @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.  
> **username_1**: @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.  
> **username_0**: 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!  

---

