# Asymptotic growth of recurrence relation $x_n=\min\limits_{n_1+n_2=n}(a(x_{n_1}+x_{n_2})+2n_1n_2)$

Suppose $a>0$ . Define $$x_n=\min_{n_1+n_2=n}(a(x_{n_1}+x_{n_2})+2n_1n_2) \text{ with } x_1=0.$$ Can we find $r>0$ such that there exists two positive constant $c_1,c_2$ such that $$c_1<\frac{x_n}{n^r}<c_2$$ for sufficiently large $n$? If such $r$ exists, what is the value of $r$? Thanks for your help.

• Can you tell us something about the context? – Johan Wästlund Oct 3 '13 at 12:32
• Did you tried to check it numerically? It will be much easier to prove such statement by induction than to come up with one. – Rami Oct 3 '13 at 16:17
• I think that you can prove by induction that for any positive $\epsilon$ there exist $C_1,C_2$ s.t. $C_1 n^{log_2 a-\epsilon}<x_n<C_2 n^{max(log_2 a,2)+\epsilon}$, for sufficiently large $n$. – Rami Oct 3 '13 at 16:37
• This is begging for some numerical experimentation (for several $a$) and educated hypothesis-making. Finding the exponent of best fit to a polynomial-ish growing sequence is an easy computational task. – Greg Martin Oct 3 '13 at 21:54
• I assume that both $n_1$ and $n_2$ are supposed to be strictly less than $n$. Then $x_1$ is not defined. – Eckhard Oct 3 '13 at 23:13

Some back-of-the-frontal-lobe calculations:

One gets $x_2=2$ and $x_3=2a+4$, given the limited number of sums. For $x_4$, we have a choice of $4a+8$ or $2a^2 +4a +6$, and for $x_5$ either $2a^2 +6a +12$ or $2a^3 +4a^2 +6a + 8$ or $4a^2 +8a +8$.

If $a \lt 1/2n$ then $x_i \lt 2i$ for $i$ up to $n$ and perhaps further. If $a=0$, then $x_n =2(n-1)$, so if there is an $r$, it must be $r \geq 1$. If $a \leq 1$, it should not be hard to show $x_n=O(n^2)$. I imagine, but have not proved, that for $a>1$ $x_n$ is $O(a^{n/2})$.

• actually for $a=1$ $x_n=n(n-1)$, so it is true what you say for $a\le 1$. – Pietro Majer Oct 4 '13 at 9:26
Based on numerical experiments I found that for $0<a<1$ the minimum is always at $n_{1}=1$ and $n_{2}=n-1$. This conjecture can be proven by induction in $n$ for an $a=1-\epsilon$ where $\epsilon>0$ and small. (I guess, if it is proven for $a$ near 1, i.e. to $O(\epsilon)$, it is true for all smaller $a$, because all coefficients of the resulting polynomial in $a$ are positive.) The solution then can be given in closed form: $$x_{n}=2\frac{n - 1 - n a + a^n}{(1-a)^{2}}.$$ (It is a polynomial since the numerator has a double zero at $a=1$.) Thus $r=1$ for $0<a<1$ is correct.
Same as Pietro in his comment I found for $a>1$ (again by experiments using Mathematica) that $$x_{2^{m}}=2^{m} \frac{2^{m}-a^{m}}{2-a}$$ which means (for $n=2^m$) $$x_{n}=\frac{n}{a-2}\left(a^{\ln n/\ln 2}-n\right)$$ The latter is $O(n^{2})$ for $1<a<2$. For $a>2$ it has the more complicated asymptotics, $O(n a^{\ln n/\ln 2})$ (Edit: or, what is the same, $O(n^{1+\ln a/ \ln 2})$).
I could not prove formally the implicit assumption, that for $a>1$ the minimum in the recursion formula is at $n_{1}=n_{2}=n/2$ for $n$ even; and, for $n$ odd, $n_{1}=(n-1)/2$ and $n_{2}=(n+2)/2$. But I am pretty sure that I am right based on the results Mathematica gave me.
• Do you mean $O(n^2)$ for $1<a<2$ and $O(n^{1+\ln a/\ln 2})$ for $a>2$? – Eckhard Jun 24 '14 at 18:38