7
$\begingroup$

Define a sequence of decimals $x_n$ by alternating the digits $1,2,\ldots,n$ left and right, as follows: $$x_1 = .1$$ $$x_2 = .21$$ $$x_3 = .213$$ $$x_4 = .4213$$ $$x_5 = .42135$$ $$x_6 = .642135$$ $$\cdots$$ $$x_{14}=.1412108642135791113$$ $$\cdots$$ Define $a_n$ as the average of the sequence up to $x_n$: $$a_n = (x_1+x_2+ \cdots x_n)/n$$

Q. Does $a_n$ approach a limit as $n\to \infty$?


Addendum. Resolved by Thomas Andrews: the sequence has no limit! However, Paul Hurst conjectures that $\lim \sup_{n \to \infty} = 0.55$.

The same question can be asked in any base $b$. Especially interesting is $b=2$, e.g., $x_3=.10111$ (i.e.,$10{-}1{-}11$), $x_7=.11010010111101111$ (i.e.,$110{-}100{-}x_3{-}101{-}111$), etc.

$\endgroup$
  • $\begingroup$ As $n\to\infty$, $a_n$ increases. $\endgroup$ – user122283 May 27 '14 at 0:44
  • $\begingroup$ @SanathDevalapurkar: That doesn't seem true. Do you mean $a_n$? $\endgroup$ – MPW May 27 '14 at 0:49
  • $\begingroup$ Umm, that's not true, @SanathDevalapurkar. Note his $x_{14}$. $\endgroup$ – Thomas Andrews May 27 '14 at 0:49
  • $\begingroup$ @MPW I meant $a_n$, sorry. $\endgroup$ – user122283 May 27 '14 at 0:49
  • $\begingroup$ What does your instinct say? Do you have a gut feeling for the likely answer? $\endgroup$ – Thomas Andrews May 27 '14 at 0:50
10
$\begingroup$

There is no limit. Assume that the limit is $L\leq 0.55$. Then let $N=6\cdot 10^k$ and $M=7\cdot 10^k$, and note that $$a_M = \frac{6\cdot10^k a_N + \sum_{i=N+1}^M x_i}{7\cdot 10^k}$$

Now, $\sum_{i=N+1}^M x_i \geq 0.6\cdot 10^k\geq (L+0.05)\cdot 10^k$. So we have:

$$a_M \geq \frac{6a_N+L+0.05}{7}= \frac{6a_N+L}{7} + \frac{0.05}{7}$$

Letting $k$ got to infinity, this would mean $L \geq L + \frac{0.05}{7},$ which is a contradiction.

The case $L\geq 0.55$ also isn't possible. A similar argument, using $N=4\cdot 10^k$ and $M=5\cdot 10^k$ then works.

Basically, while the values $x_i$ might be relatively uniform in the interval $[0.1,1]$, they come in huge blocks that have the same leading digit, which causes the sequence $a_N$ to be not Cauchy.

It seems likely that $\lim_{k\to\infty} a_{10^k} = 0.55$, though.

Proof without cases that $a_n$ isn't Cauchy.

Lemma: $a_{10^k}\geq 0.45$ for $k>1$.

Proof: $$a_{10^k} = \frac{10^{k-1}a_{10^{k-1}} + \sum_{i=1}^9\sum_{j=1}^{10^{k-1}} x_{i 10^{k-1} + j}}{10^k}$$

Now, $x_{i10^{k-1}+j}\geq \frac{i}{10}$. So this means:

$$a_{10^k}\geq \frac{a_{10^{k-1}}}{10} + \frac{1}{100}\sum_{i=1}^9 i = \frac{a_{10^{k-1}}}{10} + 0.45\geq 0.45$$


You can use this lemma with my original argument to show that $a_{2\cdot 10^k} < a_{10^k}-\epsilon$ for an $\epsilon>0$ independent of $k$, and thus that $a_n$ is not Cauchy.

$$\begin{align}a_{2\cdot 10^k} &= \frac {10^ka_{10^k}+\sum_{i=1}^{10^k}x_{10^k+i}}{2\cdot 10^k}\\&<\frac{1}{2}\left(a_{10^k}+ \frac{2}{10}\right) \\&< a_{10^k} -\left(\frac{1}{2}a_{10^k}-\frac{1}{10}\right) \\&< a_{10^k}-0.1 \end{align}$$

The last step by the Lemma, the first step by $x_{10^k+i}<0.2$.

$\endgroup$
  • $\begingroup$ I now think it either diverges, or converges to 0.55. The reason 0.55 makes sense is that in the tenths slot you only get the digits 1 to 9, which would average out to 5 if they follow a uniform distribution in the limit. So the first term in my solution would be $\frac{5}{10}$ instead of $\frac{4.5}{10}$, and the series would converge to 0.55 $\endgroup$ – Paul Hurst May 27 '14 at 1:13
  • $\begingroup$ I've just shown it diverges. Easy to alter this proof to show it can't converge to any number in $[0,1]$. @PaulHurst $\endgroup$ – Thomas Andrews May 27 '14 at 1:15
  • $\begingroup$ Yeah, looks like your argument can be used to prove it diverges. $\endgroup$ – Paul Hurst May 27 '14 at 1:19
  • $\begingroup$ @ThomasAndrews Did you switch $N$ and $M$ in the argument? It seems like $N>M$... also, can you explain the $[\text{sum}]\ge 0.6\cdot 10^k$ step please? $\endgroup$ – user142299 May 27 '14 at 1:27
  • $\begingroup$ Whoops, yes, got them backward. Will fix, thanks @NotNotLogical $\endgroup$ – Thomas Andrews May 27 '14 at 1:27
2
$\begingroup$

I'm not 100% sure on this solution. But it looks like to me that in each digit spot you're going to end up with a uniform spread of the integers from 0 to 9. So you're going to have an average of 4.5 in each digit spot. $$\frac{4.5}{10} + \frac{4.5}{10^2} + \frac{4.5}{10^3} +\cdots = \frac{4.5}{10}(1+\frac{1}{10} + \frac{1}{10^2} + \cdots) = 0.5$$

Edited: But the digit in the tenths slot is always between 1 and 9, which average out to 0.5, so that would give $$\frac{5}{10} + \frac{4.5}{10^2} + \frac{4.5}{10^3} +\cdots = 0.55$$ But I'm not sure if this converges because you get lots of consecutive digits in the first slot.

I think Thomas Andrews just proved it diverges. However, I would conjecture that the $\limsup$ is 0.55.

$\endgroup$
  • $\begingroup$ Hmmm, in the Tenths slot you only get numbers from 1 to 9, which would be an average of 0.5. But as you hit each new $10^n$ you get a ton of consecutive 1's, then consecutive 2's, etc. $\endgroup$ – Paul Hurst May 27 '14 at 1:07
  • $\begingroup$ Nice conjecture, that $\lim \sup_{n \to \infty} = 0.55$! $\endgroup$ – Joseph O'Rourke May 27 '14 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.