Conjecture on the error term in an asymptotic expression for $\sum 2^{T_x}$.

75 Views Asked by At

This is based off an insight for some possible asymptotes I gave at this post asking for the closed form for the partial sums. Let $T_x=x(x+1)/2$, $x^{th}$ triangular number; And, $$V(x)=\sum_{n=0}^{x}2^{T_n}$$

Then with simple manipulation, I was able to turn this into an asymptotic product expression (By using, $V(x)\sim2^{T_x}$);

$$V(x)\sim\left(2^{T_{x}}+2^{T_{x-1}}\right)\prod_{n=0}^{x-2}\left(\frac{1}{1-2^{\left(T_{n}-T_{x}\right)}}\right) \tag{1}$$

I've provided the sequence, this approximates in the given post. I also became much more interested in the error value. Subsequently, I noticed that the error term initially occurs off as something in relation to $2$ to the power of a particular quadratic expression. See the table below; $$\left( \begin{array}{ccc} x & V(x) & Eq. 1 & Error & 2^{(x^2-5x+2)/2} \\ \hline 0 & 1 \hspace{3.5cm}& 2 \hspace{4.6cm}& 1 \hspace{2.4cm}& 2 \hspace{1.6cm}\\ 1 & 3\hspace{3.5cm} & 3\hspace{4.6cm} & 0 \hspace{2.4cm} & .5\hspace{1.6cm} \\ 2 & 11 \hspace{3.3cm}& 11.428\hspace{3.65cm} & .428\hspace{1.9cm} & .25 \hspace{1.4cm}\\ 3 & 75\hspace{3.3cm} & 75.502 \hspace{3.55cm}& .502 \hspace{1.9cm}& .25\hspace{1.4cm} \\ 4 & 1099 \hspace{2.8cm}& 1099.786 \hspace{3.1cm}& .786\hspace{1.85cm} & .5\hspace{1.6cm} \\ 5 & 33867\hspace{2.6cm}& 33869.498 \hspace{2.8cm}& 2.498\hspace{1.6cm} & 2\hspace{1.64cm} \\ 6 & 2131019\hspace{2.2cm} & 2131036.719 \hspace{2.3cm} & 17.719\hspace{1.4cm} & 16 \hspace{1.4cm}\\ 7 & 270566475\hspace{1.7cm} & 270566743.757 \hspace{1.8cm}& 268.757\hspace{1.15cm} & 256\hspace{1.15cm} \\ 8 & 68990043211\hspace{1.25cm} & 68990051600.598 \hspace{1.3cm}& 8389.598\hspace{.9cm} & 8192 \hspace{.9cm} \\ 9 & 35253362132043\hspace{.6cm}& 35253362662561.579\hspace{0.65cm} & 530518.578\hspace{.45cm} & 524288\hspace{.44cm} \\ 10 &36064050381096011& 36064050448600818.911 & 67504807.911 & 67108864 \\ \end{array} \right) $$

You can see that the error section & $2^{(x(x-5)+2)/2}$ are similar. And alongside this, I've checked the ratio of the error term with the new error term possibility and I strongly think that $$\frac{1}{2}(Error)\sim2^{x(x-5)/2}$$ Is there a way to show that it is indeed true? I could appreciate elementary approaches, but other ways are also fine.

1

There are 1 best solutions below

0
On BEST ANSWER

Consider first the following approximation (I'll deal with the error in the approximation later): $$ \prod_{n=0}^{x-2} \frac{1}{1 - 2^{T_n - T_x}} \approx \prod_{n=0}^{x-2} (1 + 2^{T_n - T_x}) \approx 1 + \sum_{n=0}^{x-2} 2^{T_n - T_x}. $$ This turns your estimate $(1)$ into $$ (T_x + T_{x-1})\left(1 + \sum_{n=0}^{x-2} 2^{T_n - T_x}\right) = T_x + T_{x-1} + \sum_{n=0}^{x-2} 2^{T_n - T_x + T_x} + \sum_{n=0}^{x-2} 2^{T_n - T_x + T_{x-1}}. $$ The first three terms on the right simplify to just $V(x)$. But there's also a sum whose leading term is $2^{T_{x-2} - T_x + T_{x-1}} = 2^{(x^2-5x+2)/2}.$ This is the primary contributing term to your error.

The rest of the terms in that sum are together at most $2 \cdot 2^{T_{x-3} - T_x + T_{x-1}}$ and therefore asymptotically irrelevant.


As for the approximation of the product by a sum that I started with: on the one hand, it's a lower bound, because we are first replacing $1 + 2^{T_n - T_x} + 4^{T_n - T_x} + \dots$ by its first two terms, and then taking only the most significant terms of the second product. So to show that it's a good approximation, we also need a similar upper bound.

To obtain an upper bound, note that $(1 - a)(1-b) = 1 - a - b + ab \ge 1 - a - b$ for $a,b \ge 0$, so $\frac{1}{1-a} \cdot \frac1{1-b} \le \frac1{1-a-b}$, and apply this iteratively to conclude that $$ \prod_{n=0}^{x-2} \frac1{1 - 2^{T_n - T_x}} \le \frac1{1 - \sum_{n=0}^{x-2} 2^{T_n - T_x}} = 1 + \sum_{n=0}^{x-2} 2^{T_n-T_x} + \sum_{k=2}^\infty \left( \sum_{n=0}^{x-2} 2^{T_n-T_x}\right)^k. $$ The sum over $k$ is a bound on the error in our approximation. Inside this sum, note that $$ \sum_{n=0}^{x-2} 2^{T_n - T_x} \le 2^{T_{x-2} - T_x + 1} = 2^{2-2x}, $$ and $$ \sum_{k \ge 2} (2^{2-2x})^k \le \sum_{j \ge 4x-4} 2^{-j} = 2^{5-4x}. $$ Since this is later being multiplied by $T_x + T_{x-1} \le 2T_x$, the error introduced by replacing the product by its approximation is at most $2T_x \cdot 2^{5-4x} = 2^{(x^2-7x+12)/2}$, which is less significant than the error $2^{(x^2-5x+2)/2}$ we got earlier.