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.
7
-
3$\begingroup$ Can you tell us something about the context? $\endgroup$– Johan WästlundCommented Oct 3, 2013 at 12:32
-
1$\begingroup$ Did you tried to check it numerically? It will be much easier to prove such statement by induction than to come up with one. $\endgroup$– RamiCommented Oct 3, 2013 at 16:17
-
2$\begingroup$ 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$. $\endgroup$– RamiCommented Oct 3, 2013 at 16:37
-
$\begingroup$ 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. $\endgroup$– Greg MartinCommented Oct 3, 2013 at 21:54
-
$\begingroup$ I assume that both $n_1$ and $n_2$ are supposed to be strictly less than $n$. Then $x_1$ is not defined. $\endgroup$– EckhardCommented Oct 3, 2013 at 23:13
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
1
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})$.
Gerhard "Ask Me About System Design" Paseman, 2013.10.03
answered Oct 3, 2013 at 20:03
-
$\begingroup$ actually for $a=1$ $x_n=n(n-1)$, so it is true what you say for $a\le 1$. $\endgroup$ Commented Oct 4, 2013 at 9:26
$\begingroup$
$\endgroup$
0
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.
