Solve Sequences & Limits Homework: Find Limit of z_n

[Saitama]

Homework Statement

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$.

Homework Equations

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!

 

[mfb]

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!

 

[Saitama]

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!

Can I have some hints for that?

 

[mfb]

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.

 

[Saitama]

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.

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?

 

[mfb]

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

Anyway:

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

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.

 

[Saitama]

Sorry for the late reply mfb.

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.

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. :(

 

[mfb]

Can you tell me what is the upper bound of the first summation you wrote

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:

The next terms go even more big.

No matter how complicated the terms get, they are always a linear function of the first 31 elements.

It is stated without proof. :(

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

 

[haruspex]

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

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.