Is $\frac 3 2$ an upper bound of $\frac{\sum_{k=1}^n 2^{\{log_2(3/2) \cdot k\}}}{n}$ for all $n \in \mathbb{N}$?

43 Views Asked by At

Let $f : \mathbb{N} \rightarrow (1, 2)$ be a function with $$f(n) = \frac{\sum_{k=1}^n 2^{\{log_2\left(\frac 3 2\right) \cdot k\}}}{n}$$ $\{x\} = x - \lfloor x \rfloor$ denotes the fractional part of x. I want to know if $\forall n \in \mathbb{N}: f(n) \leq \frac 3 2$.

Since $\{x\} \in [0, 1) \Rightarrow 2^{\{x\}} \in [1, 2)$ obvious lower and upper bounds for $f(n)$ are $1 \leq f(n) < 2$.
Furthermore, if $\frac 3 2$ is an upper bound for $f(n)$, than it is a sharp bound because $f(1) = \frac 3 2$.
Looking at the Graph it seems that $$ lim_{n\to\infty} f(n) \stackrel{?}{=} \int_0^1 2^{x} dx = \frac{1}{ln(2)} < \frac 3 2$$

While I was unable to show an upper bound of $\frac 3 2$, I had an idea that improved the upper bound to $\frac{46}{27} = 1.\overline{703}$ .
Let $I(k)$ be the interval for possible values of $\{log_2\left(\frac 3 2\right) \cdot k\}$,
$I^*(k) := I(k) \cap \left[1 - log_2\left(\frac 3 2\right), 1\right)$ and $I_*(k) := I(k) \cap \left[0, 1 - log_2\left(\frac 3 2\right)\right)$.
Let $I(a) \rightarrow I(b) \text{ or } I(b) \leftarrow I(a)$ denote that $I(a)$ influences the possible values of $I(b)$.

Case 1: $I^*, I^*, I^*$ $$ \begin{array}{ccccc} I^*(k) = \left[1 - log_2\left(\frac 3 2\right), 1\right) & \rightarrow & I^*(k+1) = \left[1 - log_2\left(\frac 3 2\right), log_2\left(\frac 3 2\right)\right) & \rightarrow & I^*(k+2) = \varnothing \\ \end{array} $$ $\Rightarrow$ There are never three consecutive $I^*$.

Case 2: $I^*, I^*, I_*$ $$ \begin{array}{ccccc} I^*(k) = \left[1 - log_2\left(\frac 3 2\right), 1\right) & \rightarrow & I^*(k+1) = \left[1 - log_2\left(\frac 3 2\right), log_2\left(\frac 3 2\right)\right) & \rightarrow & I_*(k+2) = \left[0, 2 \cdot log_2\left(\frac 3 2\right) - 1\right) \\ I^*(k) = \left[2 - 2 \cdot log_2\left(\frac 3 2\right), 1\right) & \leftarrow & I^*(k+1) = \left[1 - log_2\left(\frac 3 2\right), log_2\left(\frac 3 2\right)\right) & & I_*(k+2) = \left[0, 2 \cdot log_2\left(\frac 3 2\right) - 1\right) \\ I^*(k) = \left[2 - 2 \cdot log_2\left(\frac 3 2\right), 1\right) & & I^*(k+1) = \left[1 - log_2\left(\frac 3 2\right), log_2\left(\frac 3 2\right)\right) & & I_*(k+2) = \left[0, 2 \cdot log_2\left(\frac 3 2\right) - 1\right) \\ \end{array} $$
Upper bound of average for three consecutive terms in case 2: $$\frac{2^{1}+2^{log_2\left(\frac 3 2\right)}+2^{2 \cdot log_2\left(\frac 3 2\right) - 1}}{3} = \frac{37}{24} = 1.541\overline{6}$$

Case 3: $I_*, I^*, I^*$ $$ \begin{array}{ccccc} I_*(k) = \left[0, 1 - log_2\left(\frac 3 2\right)\right) & & I^*(k+1) = \left[1 - log_2\left(\frac 3 2\right), 1\right) & \rightarrow & I^*(k+2) = \left[1 - log_2\left(\frac 3 2\right), log_2\left(\frac 3 2\right)\right) \\ I_*(k) = \left[2 - 3 \cdot log_2\left(\frac 3 2\right), 1 - log_2\left(\frac 3 2\right)\right) & \leftarrow & I^*(k+1) = \left[2 - 2 \cdot log_2\left(\frac 3 2\right), 1\right) & \leftarrow & I^*(k+2) = \left[1 - log_2\left(\frac 3 2\right), log_2\left(\frac 3 2\right)\right) \\ I_*(k) = \left[2 - 3 \cdot log_2\left(\frac 3 2\right), 1 - log_2\left(\frac 3 2\right)\right) & & I^*(k+1) = \left[2 - 2 \cdot log_2\left(\frac 3 2\right), 1\right) & & I^*(k+2) = \left[1 - log_2\left(\frac 3 2\right), log_2\left(\frac 3 2\right)\right) \\ \end{array} $$ Upper bound of average for three consecutive terms in case 3: $$\frac{2^{1 - log_2\left(\frac 3 2\right)}+2^{1}+2^{log_2\left(\frac 3 2\right)}}{3} = \frac{29}{18} = 1.6\overline{1}$$

Case 4: $I^*, I_*, I^*$ $$ \begin{array}{ccccc} I^*(k) = \left[1 - log_2\left(\frac 3 2\right), 2 - 2 \cdot log_2\left(\frac 3 2\right)\right) & \leftarrow & I_*(k+1) = \left[0, 1 - log_2\left(\frac 3 2\right)\right) & \rightarrow & I^*(k+2) = \left[log_2\left(\frac 3 2\right), 1\right) \\ I^*(k) = \left[1 - log_2\left(\frac 3 2\right), 2 - 2 \cdot log_2\left(\frac 3 2\right)\right) & & I_*(k+1) = \left[0, 1 - log_2\left(\frac 3 2\right)\right) & & I^*(k+2) = \left[log_2\left(\frac 3 2\right), 1\right) \\ \end{array} $$ Upper bound of average for three consecutive terms in case 4: $$\frac{2^{2 - 2 \cdot log_2\left(\frac 3 2\right)}+2^{1 - log_2\left(\frac 3 2\right)}+2^{1}}{3} = \frac{46}{27} = 1.\overline{703}$$

Case 5, 6, & 7: $I_*, I_*, I^* / I^*, I_*, I_* / I_*, I^*, I_*$
Upper bound of average for three consecutive terms in case 5, 6 & 7: $$\frac{2^{1}+2^{1 - log_2\left(\frac 3 2\right)}+2^{1 - log_2\left(\frac 3 2\right)}}{3} = \frac{14}{9} = 1.\overline{5}$$

Case 8: $I_*, I_*, I_*$
Upper bound of average for three consecutive terms in case 8: $$\frac{2^{1 - log_2\left(\frac 3 2\right)}+2^{1 - log_2\left(\frac 3 2\right)}+2^{1 - log_2\left(\frac 3 2\right)}}{3} = \frac{4}{3} = 1.\overline{3}$$

$\Longrightarrow$ the average of every three consecutive terms is smaller than $\frac{46}{27}$, $f(1) = \frac 3 2 = 1.5 \text{ and } f(2) = \frac{21}{16} = 1.3125 \Rightarrow \forall n \in \mathbb{N}:f(n) < \frac{46}{27}. \quad \Box$

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, $\frac 3 2$ is an upper bound for $f(n)$, $\forall n \in \mathbb{N}$.
Let $c := log_2\left(\frac 3 2\right)$.
I expanded on the idea of possible intervals a little more starting from the intervals $\left[0, 1-c\right)$, $\left[1-c, c\right)$ and $\left[c, 1\right)$. $$ \begin{array}{ccc} I(k) \in \left[0, 1-c\right) & \rightarrow & I(k+1) \in \left[c, 1\right)\\ I(k) \in \left[1-c, c\right) & \rightarrow & I(k+1) \in \left[0, 1-c\right)\\ I(k) \in \left[c, 1\right) & \rightarrow & I(k+1) \in \left[0, 1-c\right) \cup \left[1-c, c\right)\\ \end{array} $$ I then repeatedly split the intervals that either have two target intervals or are targeted by two intervals, resulting in the following cycle of possible intervals with two paths.

Cycle of possible intervals

Upper bound of the arithmetic mean (longer path cycle):

$$ \begin{array}{c} \frac{2^{3-4c}+2^{2-3c}+2^{2-2c}+2^{1-c}+2^{1}+2^{c}+2^{2c-1}+2^{3c-1}+2^{4c-2}+2^{5c-2}+2^{6c-3}+2^{7c-4}+2^{6-9c}+2^{5-8c}+2^{5-7c}+2^{4-6c}+2^{3-5c}}{17} = \frac{1011366493}{685283328} \approx 1.476\\ \end{array} $$

Upper bound of the arithmetic mean (shorter path cycle):

$$ \begin{array}{c} \frac{2^{3-4c}+2^{2-3c}+2^{2-2c}+2^{8-13c}+2^{8-12c}+2^{7-11c}+2^{6-10c}+2^{6-9c}+2^{5-8c}+2^{5-7c}+2^{4-6c}+2^{3-5c}}{12} = \frac{7041236}{4782969} \approx 1.472\\ \end{array} $$

The first thirteen terms of $f(n)$: $$ \begin{array}{|c|ccccccccccccc|} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\ \hline 2^{\left\{log_2\left(\frac 3 2\right) \cdot n\right\}} & \frac{3}{2} & \frac{9}{8} & \frac{27}{16} & \frac{81}{64} & \frac{243}{128} & \frac{729}{512} & \frac{2187}{2048} & \frac{6561}{4096} & \frac{19683}{16384} & \frac{59049}{32768} & \frac{177147}{131072} & \frac{531441}{524288} & \frac{1594323}{1048576}\\ \hline \Sigma & \frac{3}{2} & \frac{21}{8} & \frac{69}{16} & \frac{357}{64} & \frac{957}{128} & \frac{4557}{512} & \frac{20415}{2048} & \frac{47391}{4096} & \frac{209247}{16384} & \frac{477543}{32768} & \frac{2087319}{131072} & \frac{8880717}{524288} & \frac{19355757}{1048576}\\ \hline f(n) & \frac {3}{2} & \frac{21}{16} & \frac{23}{16} & \frac{357}{256} & \frac{957}{640} & \frac{1519}{1024} & \frac{20415}{14336} & \frac{47391}{32768} & \frac{69749}{49152} & \frac{477543}{327680} & \frac{2087319}{1441792} & \frac{2960239}{2097152} & \frac{19355757}{13631488}\\ \hline \approx & 1.500 & 1.313 & 1.438 & 1.395 & 1.495 & 1.483 & 1.424 & 1.446 & 1.419 & 1.457 & 1.448 & 1.412 & 1.420\\ \hline \end{array} $$ So starting at the interval $\left[2 \cdot log_2\left(\frac 3 2\right) - 1, 2 - 3 \cdot log_2\left(\frac 3 2\right)\right)$ with a value of $max\left(\frac{1011366493}{685283328}, \frac{7041236}{4782969}, \frac{19355757}{13631488}\right) = \frac{1011366493}{685283328} \approx 1.476$ and assuming 13 previous terms we check both the short and long cycle for one round using the upper bound of each interval. If all resulting values are $\leq \frac 3 2$ then the upper bound of $f(n)$ is $\frac 3 2$ since further rounds always start at or below the arithmetic mean of the longer cycle and reduce the deviation from the mean.
Let $C^*(n)$ be the upper bound of an interval in the longer cycle and let $C_*(n)$ be the upper bound of an interval in the shorter cycle (both starting with $C^*(14) = C_*(14) = 2 - 3 \cdot log_2\left(\frac 3 2\right)$).
Longer cycle: $$ \begin{array}{|c|cccccccccccccccccc|} \hline n & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30\\ \hline 2^{C^*(n)} & \mathbf{-} & \frac{32}{27} & \frac{16}{9} & \frac{4}{3} & 2 & \frac{3}{2} & \frac{9}{8} & \frac{27}{16} & \frac{81}{64} & \frac{243}{128} & \frac{729}{512} & \frac{2187}{2048} & \frac{32768}{19683} & \frac{8192}{6561} & \frac{4096}{2187} & \frac{1024}{729} & \frac{256}{243} & \frac{128}{81}\\ \hline \Sigma & \frac{13147764409}{685283328} & \frac{13959952057}{685283328} & \frac{15178233529}{685283328} & \frac{16091944633}{685283328} & \frac{17462511289}{685283328} & \frac{18490436281}{685283328} & \frac{19261380025}{685283328} & \frac{20417795641}{685283328} & \frac{21285107353}{685283328} & \frac{22586074921}{685283328} & \frac{23561800597}{685283328} & \frac{12146797427}{342641664} & \frac{4239074257}{114213888} & \frac{4381680593}{114213888} & \frac{4595590097}{114213888} & \frac{4756022225}{114213888} & \frac{4876346321}{114213888} & \frac{5056832465}{114213888}\\ \hline f(n) & \frac{1011366493}{685283328} & \frac{13959952057}{9593966592} & \frac{15178233529}{10279249920} & \frac{16091944633}{10964533248} & \frac{17462511289}{11649816576} & \frac{18490436281}{12335099904} & \frac{19261380025}{13020383232} & \frac{20417795641}{13705666560} & \frac{21285107353}{14390949888} & \frac{22586074921}{15076233216} & \frac{23561800597}{15761516544} & \frac{12146797427}{8223399936} & \frac{4239074257}{2855347200} & \frac{4381680593}{2969561088} & \frac{4595590097}{3083774976} & \frac{4756022225}{3197988864} & \frac{4876346321}{3312202752} & \frac{1011366493}{685283328}\\ \hline \approx & 1.476 & 1.455 & 1.477 & 1.468 & 1.499 & 1.499 & 1.479 & 1.490 & 1.479 & 1.498 & 1.495 & 1.477 & 1.485 & 1.476 & 1.490 & 1.487 & 1.472 & 1.476\\ \hline \end{array} $$ Shorter cycle: $$ \begin{array}{|c|ccccccccccccc|} \hline n & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25\\ \hline 2^{C_*(n)} & \mathbf{-} & \frac{32}{27} & \frac{16}{9} & \frac{2097152}{1594323} & \frac{1048576}{531441} & \frac{262144}{177147} & \frac{65536}{59049} & \frac{32768}{19683} & \frac{8192}{6561} & \frac{4096}{2187} & \frac{1024}{729} & \frac{256}{243} & \frac{128}{81}\\ \hline \Sigma & \frac{13147764409}{685283328} & \frac{13959952057}{685283328} & \frac{15178233529}{685283328} & \frac{1302451359881}{55507949568} & \frac{1411973025929}{55507949568} & \frac{1494114275465}{55507949568} & \frac{1555720212617}{55507949568} & \frac{1648129118345}{55507949568} & \frac{1717435797641}{55507949568} & \frac{1821395816585}{55507949568} & \frac{1899365830793}{55507949568} & \frac{1957843341449}{55507949568} & \frac{2045559607433}{55507949568}\\ \hline f(n) & \frac{1011366493}{685283328} & \frac{13959952057}{9593966592} & \frac{15178233529}{10279249920} & \frac{1302451359881}{888127193088} & \frac{1411973025929}{943635142656} & \frac{1494114275465}{999143092224} & \frac{1555720212617}{1054651041792} & \frac{329625823669}{222031798272} & \frac{1717435797641}{1165666940928} & \frac{1821395816585}{1221174890496} & \frac{1899365830793}{1276682840064} & \frac{1957843341449}{1332190789632} & \frac{2045559607433}{1387698739200}\\ \hline \approx & 1.476 & 1.455 & 1.477 & 1.467 & 1.496 & 1.495 & 1.475 & 1.485 & 1.473 & 1.492 & 1.488 & 1.470 & 1.474\\ \hline \end{array} $$ $\Rightarrow \frac 3 2$ is an upper bound for $f(n)$, $\forall n \in \mathbb{N}\text{.} \quad \Box$