## Monotonically increasing intervals

Problem  A real sequence $\{T_n\}_{n\ge1}$ satisfies $T_{n+1}+T_{n}=2n^\alpha$ for all $n\ge1$, where $1<\alpha<2$. Let $\Delta_{n}:=T_{n+1}-T_n$ be the length of the $n$th interval. Show that there exists a unique $T_1$ such that $\Delta_{n+1}>\Delta_n$ for all $n\ge1$.

Remark  This is a problem that arises from nonlinear quantization in AAC. There, MDCT coefficient $x$ is power-compressed to $y=x^{3/4}$ before linear quantization. Then we face the problem of choosing boundaries $T_n, T_{n+1}$ for the $n$th quantization interval where all $x\in [T_n, T_{n+1}]$ are quantized to $n$ and de-quantized to $\bar{x}=n^{4/3}$, such that the de-quantization noise $\bar{x}-x$ is minimized statistically. Of course, the solution to this problem depends on the underlying probability distribution of $x$. In case of uniform distribution, the de-quantized value $n^{4/3}$ should be at the center of the $n$th interval, or $T_n + T_{n+1} = 2n^{4/3}$. With this restriction, all the boundaries $\{T_n\}_{n>1}$ are uniquely determined by $T_1$. But the length of the interval $\Delta_n=T_{n+1}-T_n$, as revealed by numerical experiments, almost always undulates and at the same time, asymptotically increases to $\infty$ as $n\to\infty$ ($\sim \tfrac43n^{1/3}$ ), for a randomly chosen $T_1$. Then, is there a $T_1$ to make the length of the interval monotonically increase? The answer is yes, and this $T_1$ is uniquely determined by $\alpha$, as shown in the following.

Proof  Let us denote the difference of $n$th and $(n+1)$th intervals’ lengths by $\Gamma_n:=\Delta_{n+1}-\Delta_n$. We claim that $\Gamma_n>\Gamma_{n+2}$ for all $n\ge1$. If so, to ensure $\Gamma_n>0$ for all $n\ge1$, then we need to show that there exists a unique $T_1$ such that both $\lim_{n\to\infty}\Gamma_{2n}$ and $\lim_{n\to\infty}\Gamma_{2n+1}$ exist and are non-negative. First, by the relation $T_n+T_{n+1}=2n^\alpha$, we have $\Gamma_n=2(n+1)^\alpha+2n^\alpha-4T_{n+1}$. Furthermore, let $f(x):=(x+1)^\alpha-x^\alpha$, then

$latex \begin{array}{rcl} \Gamma_{n+2}-\Gamma_n & = & 2(n+3)^\alpha+2(n+2)^\alpha-2(n+1)^\alpha-2n^\alpha-4T_{n+3}+4T_{n+1} \\ & = & 2(n+3)^\alpha-6(n+2)^\alpha+6(n+1)^\alpha-2n^\alpha \\ & = & 2(f(n+2)-2f(n+1)+f(n)) \\ & = & 2f”(\eta_n), \end{array}$

where $\eta_n\in(n,n+2)$ and the last equation is due to recursive application of Rolle’s theorem (first about $f(x+1)-f(x)$, then about about $f(x)$).  Since $f''(x)=\alpha(\alpha-1)[(x+1)^{\alpha-2}-x^{\alpha-2}]<0$ for $x>0$ when $1<\alpha<2$, we have $f''(\eta_n)<0$ thus $\Gamma_{n+2}-\Gamma_n<0$. Next, consider the limit of $\Gamma_{2n}+\Gamma_{2n+1}$:

$latex \begin{array}{rcl} \Gamma_{2n}+\Gamma_{2n+1} & = & \Delta_{n+2}-\Delta_n \\ & = & T_{n+3}-T_{n+2}-T_{n+1}+T_n \\ & = & T_{n+3}+T_{n+2}-2T_{n+2}-2T_{n+1}+T_{n+1}+T_n \\ & = & 2[f(n+1)-f(n)] \\ & \xrightarrow{n\to\infty} & 0, \end{array}$

where the last equation is due to $\lim_{x\to\infty}f'(x)=0$ for $1<\alpha<2$. Thus, the desired $T_1$, if it ever exits, must ensure $\lim_{n\to\infty}\Gamma_{2n}=0$. Conversely, if with some $T_1$, $\lim_{n\to\infty}\Gamma_{2n}=0$, then $\Gamma_n>0$ for all $n\ge1$.

Now, if suffices to show there exists a unique $T_1$ such that $\lim_{n\to\infty}\Gamma_{2n}=0$. Let $S_n:=(n-1)^\alpha-(n-2)^\alpha+\cdots+(-1)^n$, then $T_n=2S_n-(-1)^nT_1$. We claim that $\xi_n:=(2n+\tfrac12)^\alpha-2S_{2n+1}$ converges as $n\to\infty$. In that case, we shall have

$latex \begin{array}{rcl} \Gamma_{2n} & = & 2(2n+1)^\alpha+2(2n)^\alpha-4T_{2n+1} \\ & = & 2(2n+1)^\alpha+2(2n)^\alpha-8S_{2n+1}-4T_1 \\ & = & 2(2n+1)^\alpha+2(2n)^\alpha-4(2n+\tfrac12)^\alpha+4\xi_n-4T_1 \\ & = & 2[g(2n+\tfrac12)-g(2n)]+4\xi_n-4T_1 \\ &\xrightarrow{n\to\infty} & 4\xi_n-4T_1, \end{array}$

where $g(x):=(x+\tfrac12)^\alpha-x^\alpha$ and the last equation above follows from $\lim_{x\to\infty}g'(x)=0$ when $1<\alpha<2$. Therefore, the unique $T_1$ will be $\lim_{n\to\infty}\xi_n$. It remains to show that $\{\xi_n\}_{n\ge1}$ does converge.

Let us investigate the difference between $\xi_n$ and $\xi_{n+1}$:

$latex \begin{array}{rcl} \xi_{n+1}-\xi_n & = & (2n+\tfrac52)^\alpha-(2n+1)^\alpha-2[(2n+2)^\alpha-(2n+1)^\alpha] \\ & = & f(2n+\tfrac32)+f(2n+\tfrac12)-2f(2n+1) \\ & = & \tfrac14\alpha(\alpha-1)(\alpha-2)\theta_n^{\alpha-3}, \end{array}$

where $\theta_n\in(2n+\tfrac12,2n+\tfrac52)$ and the last equation is also due to recursive application of Rolle’s theorem. (First about $f(x+\tfrac12)-f(x)$, then about $f(x)$, and finally about $x^\alpha$.) Therefore, we have $\xi_{n+1}-\xi_n=\mathcal{O}(n^{\alpha-3})$, which implies that $\xi_n$ converges.

This completes the proof.                                                                                                        $\square$