11
$\begingroup$

There exists a sequence $a_n$ that begins $(1, 2, 1, 1, 1, 2, 1, 1, 2, 1, ...)$. It is fully defined on the OEIS at A293630, but I will give a simple explanation here. The sequence starts $1, 2$. The next part is generated by looking at the last term in the current sequence (currently $2$), and adding the rest of the sequence to the end that many times (resulting in $1, 2, 1, 1$). This continues $(1, 2, 1, 1, 1, 2, 1), (1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2)...$ $a_n$ represents the $n$th term of the final, infinite sequence. It appears that $$\lim_{n\to\infty} \frac{\sum_{k=1}^{n} a_k}{n} = 1.2752618420911721359284772047801515149347600371...$$ While empirical evidence holds this to be true up to an absurd amount of terms, I have not been successful in even proving that the limit exists. I have found no relation of this number to other constants. Is there a way I could either prove the existence of the limit, prove this is the value of the limit, or find the significance of the number?

Edit: Now that a proof has been provided by Sangchul Lee, I am looking for what this value may represent and what causes this value in particular to appear. An acquaintance with the same interest has put a bounty up for answers that may present an explanation for this.

$\endgroup$
3
  • 2
    $\begingroup$ IMHO the limit must exist, because there are never numbers lower than 1 and larger than 2. Also the arithmetic mean can't alternate, because expanding the mean by another number in the sequence will result in smaller and smaller change in the value, so it must converge. However, those are just thoughts, not mathematical proof. $\endgroup$
    – TStancek
    Commented Apr 13, 2018 at 7:26
  • 1
    $\begingroup$ Those are the thoughts I had. I'm extremely sure that the limit exists and it is the value above, but I want to prove it to be completely sure. $\endgroup$
    – Kirk Fox
    Commented Apr 13, 2018 at 7:29
  • 2
    $\begingroup$ Great, just next time don't forget to add your thoughts to the question. so others know what you already know. $\endgroup$
    – TStancek
    Commented Apr 13, 2018 at 7:37

1 Answer 1

11
+50
$\begingroup$

We establish the convergence of the limit.

Step 1. Designate $(1,2)$ as the $1$-st stage and let $L_n$ be the length of the sequence at the $n$-th stage. Also, let $S_n = \sum_{k=1}^{n} a_k$ and $T_n = S_{L_n}$. Then

$$ L_{n+1} = \begin{cases} 2L_n - 1, & \text{if } a_{L_n} = 1 \\ 3L_n - 2, & \text{if } a_{L_n} = 2 \end{cases}, \qquad T_{n+1} = \begin{cases} 2T_n - 1, & \text{if } a_{L_n} = 1 \\ 3T_n - 4, & \text{if } a_{L_n} = 2 \end{cases} $$

With this at our hands, we claim the following:

Claim. $T_n/L_n$ converges to some $\alpha \in [1, 2]$, and in fact, we have $\left|\frac{T_n}{L_n} - \alpha \right| \leq \frac{4}{L_n} $.

Notice that $L_{n+1} - 1 \geq 2(L_n - 1)$ for all $n \geq 1$. Inductively applying this inequality, it follows that

$$L_{n+k} \geq 1 + 2^k (L_n - 1) \qquad \forall n, k \geq 1.$$

Moreover, from the above recurrence relation we read out that

$$ \left| \frac{T_{n+1}}{L_{n+1}} - \frac{T_n}{L_n} \right| = \left\{ \begin{array}{ll} \dfrac{\left| T_n - L_n \right|}{L_n(2L_n - 1)}, & \text{if } a_{L_n} = 1 \\ \dfrac{2\left| 2L_n - T_n \right|}{L_n(3L_n - 2)}, & \text{if } a_{L_n} = 2 \end{array} \right\} \leq \frac{1}{L_n}$$

So by the comparison test applied to $\frac{T_n}{L_n} = \frac{T_1}{L_1} + \sum_{k=1}^{n-1} \left( \frac{T_{k+1}}{L_{k+1}} - \frac{T_k}{L_k} \right)$, it follows that $T_n/L_n$ converges. Let $\alpha$ denote the limit. Then $1 \leq a_k \leq 2$ tells that $1 \leq \alpha \leq 2$ as well. Finally, applying both of the previous inequalities, we get

\begin{align*} \left| \frac{T_n}{L_n} - \alpha \right| &\leq \sum_{k=n}^{\infty} \left| \frac{T_{k+1}}{L_{k+1}} - \frac{T_k}{L_k} \right| \leq \frac{1}{L_n} \sum_{k=0}^{\infty} \frac{L_n}{L_{n+k}} \\ &\leq \frac{1}{L_n} \sum_{k=0}^{\infty} \frac{L_n}{1 + 2^k (L_n - 1)} \leq \frac{1}{L_n} \sum_{k=0}^{\infty} \frac{1}{2^{k-1}} = \frac{4}{L_n} \end{align*}

Therefore the claim follows. ////


Step 2. Now we want to show that $S_m/m$ converges to $\alpha$ as $m\to\infty$. To this end, we define

$$ \epsilon_{A} := \sup\left\{ \left| \frac{S_m}{m} - \alpha \right| : m \in A \cap \mathbb{Z} \right\} $$

(with the convention $\sup \varnothing = 0$, though this is irrelevant to the argument.) Our goal is to estimate $\epsilon_{[L_n, \infty)}$ and conclude that this converges to $0$ as $n\to\infty$, which is equivalent to the showing that $S_m/m \to \alpha$ as $m\to\infty$. It turns out that the following almost-repeating structure plays the key role:

Observation. Let $m \in (L_n, L_{n+1}]\cap\mathbb{Z}$. Then

  1. If $m \in (L_n, 2L_n - 1]$, then $S_m = T_n + S_{m-L_n}$.
  2. If $a_{L_n} = 2$ and $m \in [2L_n, 3L_n-2]$, then $S_m = 2T_n - 2 + S_{m-2L_n + 1}$.

Both are direct consequences of the construction. Now we temporarily fix $p \geq 1$ and let $n > p$. Then for $m \in (L_n, L_{n+1}] \cap \mathbb{Z}$,

  • Case 1. Assume that $m \in [L_n, L_n+L_p) $. Using the fact that $\left| \frac{S_{m-L_n}}{m - L_n} - \alpha \right| \leq 1$, we obtain

    \begin{align*} \left| \frac{S_{m}}{m} - \alpha \right| &\leq \frac{L_n}{m} \cdot\left| \frac{T_n}{L_n} - \alpha \right| + \frac{m-L_n}{m} \left| \frac{S_{m - L_n}}{m - L_n} - \alpha \right| \\ &\leq \frac{L_n}{m} \cdot \frac{4}{L_n} + \frac{m-L_n}{m} \\ &\leq \frac{4}{L_n} + \frac{L_p}{L_p + L_n}. \end{align*}

  • Case 2. Assume that $m \in [L_n + L_p, 2L_n - 1]$. Using the fact that $m - L_n \geq L_p$, it follows that

    \begin{align*} \left| \frac{S_{m}}{m} - \alpha \right| &\leq \frac{L_n}{m} \cdot\left| \frac{T_n}{L_n} - \alpha \right| + \frac{m-L_n}{m} \left| \frac{S_{m - L_n}}{m - L_n} - \alpha \right| \\ &\leq \frac{L_n}{m} \cdot \frac{4}{L_n} + \frac{m-L_n}{m} \epsilon_{[L_p, \infty)} \\ &\leq \frac{4}{L_n} + \frac{1}{2} \epsilon_{[L_p, \infty)}. \end{align*}

  • Case 3. Let $m \in [2L_n, 2L_n+L_p) $. This case is possible only when $a_{L_n} = 2$ and hence we assume so. By mimicking the previous claim, we find that $\left| \frac{2T_n - 2}{2L_n - 1} - \alpha \right| \leq \frac{C}{2L_n - 1}$ holds for all $n \geq 1$ for some constant $C > 0$ which is independent of $n$. Using this and mimicking Claim 1,

    \begin{align*} \left| \frac{S_{m}}{m} - \alpha \right| &\leq \frac{2L_n - 1}{m} \left| \frac{2T_n - 2}{2L_n - 1} - \alpha \right| + \frac{m - 2L_n + 1}{m} \left| \frac{S_{m-2L_n+1}}{m - 2L_n + 1} - \alpha \right| \\ &\leq \frac{C}{L_n} + \frac{L_p}{L_p + L_n}. \end{align*}

  • Case 4. Let $m \in [2L_n+L_p, L_{n-1}) $. Adopting the techniques in Case 2 and Case 3, we obtain

    $$ \left| \frac{S_{m}}{m} - \alpha \right| \leq \frac{C}{L_n} + \frac{2}{3}\epsilon_{[L_p, \infty)}. $$

Combining altogether, with $C' = 4+C$ the following holds:

$$ \epsilon_{(L_n, L_{n+1}]} \leq \frac{C'}{L_n} + \max\left\{ \frac{L_p}{L_p + L_n}, \frac{2}{3}\epsilon_{[L_p, \infty)} \right\}. $$

Then it follows that $ \limsup_{n\to\infty} \epsilon_{(L_n, L_{n+1}]} \leq \frac{2}{3}\epsilon_{[L_p, \infty)} $. Then $\limsup_{n\to\infty} \epsilon_{[L_n, \infty)} \leq \frac{2}{3}\epsilon_{[L_p, \infty)}$ holds as well, and then it is easy to conclude that

$$\limsup_{n\to\infty} \epsilon_{[L_n, \infty)} = 0.$$

This implies the desired convergence.

$\endgroup$
3
  • 1
    $\begingroup$ Very nice proof. $(+1)$ :) $\endgroup$
    – Mr Pie
    Commented Apr 13, 2018 at 13:34
  • $\begingroup$ This is indeed a very nice proof, but as I am inexperienced with big O notation, I am unsure how the definitions of $T_{n+1}$ and $L_{n+1}$ imply $\frac{T_{n+1}}{L_{n+1}} = \frac{T_n}{L_n} + \mathcal{O}\left(\frac{1}{L_n}\right)$. $\endgroup$
    – Kirk Fox
    Commented Apr 13, 2018 at 16:03
  • 1
    $\begingroup$ @KirkFox, For instance, assume that $a_{L_n} = 1$. Then $$ \frac{T_{n+1}}{L_{n+1}}-\frac{T_n}{L_n}=\frac{(2T_n-1)L_n - T_n(2L_n-1)}{(2L_n-1)L_n}=\frac{T_n - L_n}{L_n(2L_n-1)}. $$ Now notice that $|T_n - L_n| \leq L_n$. Then the last quantity is bounded from above by $\frac{1}{2L_n-1} \leq \frac{1}{L_n}$. If you get experienced in $\mathcal{O}$-notation, you can easily derive $\mathcal{O}(L_n^{-1})$ bound by writing $$\frac{T_{n+1}}{L_{n+1}}=\frac{\frac{T_n}{L_n}-\frac{1}{2L_n}}{1-\frac{1}{2L_n}}.$$ Similar computation applies when $a_{L_n} = 2$. $\endgroup$ Commented Apr 13, 2018 at 16:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .