4
$\begingroup$

Find a ${{b_n}}$ $n\in\Bbb N$ and $0\le b_n\le 1$ such as the limit $$\lim_{n\to\infty} {\frac1n}\sum_{i=1}^{n-1}b_i$$ does not exist.

I don't know how to deal with this problem, it seems to me that this limit can not be undetermined because the terms of the sum are all positive, so how is it possbile to obtain an "oscillation" of the limit? Maybe it can be undetermined because of $1/n$ but I can't find any ${b_n}$, I tried whit absolute value of sine and cosine but I think that I should consider a ${b_n}$ defined for recurrence or defined by intervals

Thanks for your help

$\endgroup$
  • $\begingroup$ If the series diverges, would you say the limit exists (and is $\infty$)? $\endgroup$ – cdwe Jul 25 '17 at 9:11
  • $\begingroup$ I think yes! Or maybe I have an undetermined form and the result depends on the quotient $\endgroup$ – pter26 Jul 25 '17 at 9:16
  • $\begingroup$ @5xum: Thanks, yes. $\endgroup$ – user90369 Jul 25 '17 at 10:10
3
$\begingroup$

Given an integer $m\ge2$, let $$ b_k=\frac12\left(1+(-1)^{\left\lfloor\log_m(k)\right\rfloor}\right) $$ Then we have that $b_k$ is $m-1$ ones followed by $m^2-m$ zeroes followed by $m^3-m^2$ ones followed by $m^4-m^3$ zeroes, etc.

Thus, we get $$ \sum_{k=1}^{m^n-1}b_k=\left\{\begin{array}{} \frac{m^{n+1}-1}{m+1}&\text{if $n$ is odd}\\ \frac{m^n-1}{m+1}&\text{if $n$ is even} \end{array}\right. $$ Therefore, $$ \frac1{m^n-1}\sum_{k=1}^{m^n-1}b_k=\left\{\begin{array}{} \frac{m^{n+1}-1}{(m+1)(m^n-1)}&\text{if $n$ is odd}\\ \frac1{m+1}&\text{if $n$ is even} \end{array}\right. $$ Thus, $$ \limsup_{n\to\infty}\frac1n\sum_{k=1}^nb_k\ge\frac{m}{m+1} $$ and $$ \liminf_{n\to\infty}\frac1n\sum_{k=1}^nb_k\le\frac1{m+1} $$ Therefore, the limit doesn't exist. Choosing $m$ appropriately, the liminf and limsup can be made as close to $0$ and $1$ as desired.


Notice: In the case of $m=2$, this sequence is the same sequence that appears in Andreas' earlier answer.

Notice: In the case of $m=2$, the upper and lower limits, although a bit different, are also given in Andreas' earlier answer.

$\endgroup$
  • $\begingroup$ Great because you give me a specific $b_k$, if is not too much asking that, how do you find it? $\endgroup$ – pter26 Jul 25 '17 at 13:13
  • $\begingroup$ I knew we wanted to double the number of zeroes and ones each run, and $\left\lfloor\log_2(k)\right\rfloor$ increases by $1$ each time $k$ passes a power of $2$. The fact that the number of zeroes and ones form a geometric sequence made the summation of terms easier. $\endgroup$ – robjohn Jul 25 '17 at 13:16
  • $\begingroup$ @robjohn Strange that you post exactly the same answer that I have posted 2 hours earlier (see below: same pattern, same oscillation limits, some more advanced notation maybe at your part). Also others have come up with the idea of doubling the length of the 0/1 intervals. Academic standards forbid cloning and require citing other's ideas and results. Arrogance is not a role model. $\endgroup$ – Andreas Jul 25 '17 at 14:33
  • $\begingroup$ @robjohn I agree with Andreas. Reference to relevant contributions of others is academic standard and should be obeyed. I provided the first solution of this type in a comment 4 hours ago, then in my solution 3 hours ago. I have quoted 5xum for the main idea. $\endgroup$ – Dr. Wolfgang Hintze Jul 25 '17 at 14:50
  • $\begingroup$ @Andreas: I had been interrupted in the process of writing the answer and the form of my answer did not look similar to any I saw after posting. I had to leave soon after posting to take someone to an appointment. I did NOT clone your idea since I hadn't read your answer before I posted. The OP liked something about my presentation, it seems, but if they unaccept my answer, I will be glad to delete it as I see that the sequence is indeed the same, though the presentation is quite different. $\endgroup$ – robjohn Jul 25 '17 at 15:48
5
$\begingroup$

You can do it by only setting $b_n$ to either $0$ or $1$.


First of all, let's call $$B_n = \frac1n\sum_{i=1}^{n-1} b_i$$

The important thing is, that let's say we already determined $b_1,\dots, b_k$. Then, $B_k$ is a fixed number.

Now let's say we add $N$ ones to the end of the sequence, so $b_{k+1}, b_{k+2}\dots b_{k+N} = 1$.

Then,

$$\frac1{k+N}\sum_{i=1}^{k+N-1} b_i =\frac{1}{k+N}\left(\sum_{i=1}^{k-1} b_i + \sum_{i=k}^{k+N-1} b_i\right) \\ =\frac{1}{k+N}\left(k\cdot B_k + \sum_{i=k}^{k+N-1} b_i\right) \\ =\frac{k}{k+N} B_k + \frac{N-1}{k+N}$$

which, when $N$ becomes large, approaches $1$.


So, no matter what the current value of $B_k$ is, if we add enough ones to the end of the sequence, we can get close to $1$. So, say, we can reach $\frac34$. Then, you can add enough zeroes to reach $\frac14$ and continue.

$\endgroup$
  • $\begingroup$ The $b_k$ already determined are between 0 and 1? So do you consider $b_n$ such a "fixed" value equal to 0 or 1? $\endgroup$ – pter26 Jul 25 '17 at 9:33
  • $\begingroup$ I don't think the line of argument is correct. What we are looking for is the limit as $n\to \infty$. If you start with $k$ values and then subsequently set $b_n = 1$, then for $n\to \infty$ the limit is clearly determined as 1. $\endgroup$ – Andreas Jul 25 '17 at 9:34
  • $\begingroup$ And also I don't understood your conclusion, until "when N becomes large, approaches 1" it seems totally right and clear, but when you say "we can reach 3/4" I'm totally lost $\endgroup$ – pter26 Jul 25 '17 at 9:39
  • $\begingroup$ @Andreas You only add enough $b_k$ such that $\frac1n\sum_{i=1}^{n-1} b_i$ is above $\frac34$. then you add zeroes to fall back down to below $\frac14$. $\endgroup$ – 5xum Jul 25 '17 at 9:43
  • 1
    $\begingroup$ @user411485 I won't solve everything for you. Think about it for a while. Especially about the last paragraphs. The idea is to add ones so we go above $\frac34$ (or $\frac23$, or any other number $\alpha$ from $(0,1)$), then add zeroes so we fall below $\frac14$ (or any other number from $(0,\beta)$. $\endgroup$ – 5xum Jul 25 '17 at 9:45
2
$\begingroup$

EDIT #2 related references

I noticed meanwhile that the sequence $b(n)$ I proposed here to illustrate the validity of the statement in the OP is contained in another context in OEIS (https://oeis.org/A086694, A run of 2^n 1's followed by a run of 2^n 0's, for n=0, 1, 2, ... ).

There also an explicit formula is given

$$b(n)=\left\lfloor \log _2(n+1)\right\rfloor -\left\lfloor \log _2\left(\frac{4 (n+1)}{3}\right)\right\rfloor +1$$

and an interesting recursion relation

$$b(1) = 1, b(2) = 0, b(2n+1) = b(n), b(2n) = b(n-1)$$

Many other sequences of this type, so called "divide-and-conquer" sequences, studied by R. Stephan can be found in this reference.

EDIT

Notice that, in the following example, it is the pattern that matters, not the value. Indeed, the b's could change between $0$ and any value $c$ with $0<c<1$. The limits mentioned below then have to be multiplied by $c$.

Original post

Let me illustrate the solution idea of 5xum of using a sequence of $0$s and $1$s with an explicit example in some more detail than is possible in a comment.

We use a pattern with powers of 2:

$$b(0) = 1, b(1) = 0, $$ $$b(2)=b(3) = 1, b(4)=b(5) = 0, $$ $$b(6)=b(7)=b(8)=b(9) = 1, b(10)=b(11)=b(12)=b(13) = 0 $$

and so on.

The generating function of this sequence is

$$g(z)=\frac{1}{1-z}\sum _{n=0}^{\infty } z^{2 \left(2^n-1\right)} \left(1-z^{2^n}\right)$$

The sequence of

$$B(n)=\frac{1}{n}\sum _{k=0}^n b(k)$$

has no limit because oscillates for large $n$ between 1/2 and 2/3.

A proof of the latter statement can be done as follows

Let us consider groups of elements and refer a group by an index $m$ stating at $m=0$.

group $m = 0$ starts at $k1 = 0$ with a $1$, followed at $k0=1$ by a $0$
group $m = 1$ starts at $k1 = 2$ with two $1$s, followed at $k0 = 4$ by two $0$s

In general,
group $m$ starts at $k1= 2(2^m-1)$ with $2^m$ $1$s, followed at $k0= 2(2^m- 1) + 2^m = 3(2^m-1) + 1$ by $2^m$ $0$s

The sum of all elements of a particular group $m$ is obviously $2^m$.

Hence the sum of all groups up to group $M$ inclusively, is $2^{M+1} - 1$.

This corresponds to the index start of next group $M+1$ minus $1$:

$$n = 2(2^{M+1}-1)-1$$

Hence $B(n)$, the sum divided by $n$, goes very quickly to 1/2. This is a minimum of $B(n)$ with respect to $n$ because the next goup comes in with $1$s.

The maximum value of $B(n)$ is reached at the end of the $1$s of group M. This is at

$$n = k1 + 2^M = 2(2^M-1)+2^M = 3*2^M - 2$$

Hence the maximum of $B(n)$ is

$$B(n) =(2^{M+1} - 1)/ (3*2^M - 2)$$

the limit of which is 2/3.
Q.E.D.

$\endgroup$
  • $\begingroup$ I guess proving the part that it falls to $\frac12$ should be trivial (since it's exactly $\frac12$ after every couple of steps) $\endgroup$ – 5xum Jul 25 '17 at 10:44
1
$\begingroup$

Here is a rigorous answer, building upon the idea of @Dr. Wolfgang Hintze.

Let us consider summing $b_i=1$'s only for indices $i$ with $2^{2k} \leq i < 2^{2k+1}$, $k \in \cal N_0$, otherwise we sum $b_i=0$. The length of the $k$th summation interval is $2^{2k+1} - 2^{2k}= 2^{2k} = 4^k$. Adding all intervals from $k=0$ to $k=L$ gives

$$ \sum_{k=0}^{L} 4^k = \frac{4^{L+1}-1}{4-1} = \frac{4}{3} \frac{4^{L}-1/4}{1} $$ This corresponds to having added all numbers $b_i$ from $i=1$ up to $i=2^{2L+1} -1 = 2 \cdot 4^L - 1$. Since we are continuing adding zeroes until $i=2^{2(L+1)} -1 = 4 \cdot 4^L - 1$, the value of the sum won't change. Since the OP's question asks for the mean, we have that the mean oscillates between $$ \frac{4}{3} \frac{4^{L}-1/4}{2 \cdot 4^L - 1} $$ and $$ \frac{4}{3} \frac{4^{L}-1/4}{4 \cdot 4^L - 1} $$

Large $n$ is the same as large $L$, so taking $L\to \infty$, the mean oscillates between $2/3$ and $1/3$, hence the limit does not exist.

$\endgroup$
  • $\begingroup$ (+1) I like this sequence and the computation of the means is good, too. $\endgroup$ – robjohn Jul 25 '17 at 18:07

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.