# Sequences and Limits

1. Apr 10, 2013

### Saitama

1. The problem statement, all variables and given/known data
Let $x_k=k$ for $k \leq 31$ and $\displaystyle x_{k+1}=\frac{x_1+x_2+........x_k}{k}$ for $k \geq 31$. Also let $y_k=x_k$ for $k \leq 31$ and $\displaystyle y_{k+1}=\frac{y_k+y_{k-1}+........y_{k-30}}{31}$ for $k \geq 31$. Now if $z_k=y_k-x_k$ for all $k ε N$. Find $\lim_{n→∞} z_n$.

2. Relevant equations

3. The attempt at a solution
I figured out that $x_{k+1}=x_{k+2}=....=16$, so the question reduces to
$$\displaystyle \lim_{n→∞} z_n=y_n-16$$
I am having trouble finding $\lim_{n→∞}=y_n$.

I plugged in some numbers in the expression of $y_k$ starting k=31.
When k=31, $y_{32}=16$.
When k=32, $y_{33}=\frac{15+16*31}{31}$
The next terms go even more big. I am stuck here.

Any help is appreciated. Thanks!

2. Apr 10, 2013

### Staff: Mentor

That is an interesting sequence. Numerical calculations suggest a nice result, but I don't know how to prove it.
It is easy to show the existence of a limit.

Edit: It is possible to prove a way more general result for the limits (for all starting sequences) - your example follows as one special case of this.
That is a very nice problem!

Last edited: Apr 10, 2013
3. Apr 10, 2013

### Saitama

Can I have some hints for that?

4. Apr 11, 2013

### Staff: Mentor

You can look at some examples (in a spreadsheet, with a programming language or whatever), and try to find this general formula.

Hint: The whole system is linear.

5. Apr 11, 2013

### Saitama

I can't use any devices to solve this because this question is from my test paper and I suppose there should be a way of doing this without the help of computer.

And what do you mean by that the system is linear?

6. Apr 11, 2013

### Staff: Mentor

There is a way to prove it with pen and paper, but a computer certainly helps to get the right idea.

Anyway:
All y_k (apart from the first 31) can be written as sum of the first 31 y_i with some weights: $y_k = \sum_{i=1}{31} w_{ki}y_i$.
Those weights are bounded, if you take the limit of y_k you can split it in 31 individual limits and get 31 k-independent weights:
$$\lim_{k \to \infty}y_k = \sum_{i=1}^{31} w_{i}y_i$$

That is not limited to the first 31 elements - every other set of 31 adjacent elements in your sequence has to give the same limit. You can use this to determine the weights.

7. Apr 13, 2013

### Saitama

Sorry for the late reply mfb.

I am having some difficulty understanding as I have never seen this type of way for solving problems.

Can you tell me what is the upper bound of the first summation you wrote: $y_k = \sum_{i=1}{31} w_{ki}y_i$ ? And what does "Those weights are bounded" mean?

The solution simply evaluates the $\lim_{n→∞} y_n$ as $\displaystyle \frac{\sum_{n=1}^{31} n^2}{\sum_{n=1}^{31} n}$. It is stated without proof. :(

8. Apr 13, 2013

### Staff: Mentor

I don't see how this is relevant.

You can prove that, if the first n elements can be written as such a sum, element n+1 can be written with such a sum as well. The first 31 elements can be written like that. By induction, every element can be written in that way. In addition, you can get the conditions 0<w_i and sum(w_i)=1 in the induction - bounded weights.
That is a general way to express this:
No matter how complicated the terms get, they are always a linear function of the first 31 elements.

That is bad, but it is possible to prove it.

9. Apr 13, 2013

### haruspex

Maybe it's clearer if you look at it this way...
Suppose the first 31 terms were 1, 0, 0... That would generate some sequence for terms 32 onwards. 0, 1, 0, 0... would generate some other sequence. And if the first 31 were 1, 1, 0, 0, ... then the generated sequence would be the sum of the first two. So if you knew what each of the starting sequences with a single 1 and the rest zeroes generated then you could derive the result of any other starting sequence by adding multiples of these base ones. Likewise the limits.