A question regarding limits

Hello all! I have been trying the following question for quite some time and haven't been able to reach the answer. I hope you math geniuses could shed some light on this and help me to get through this. :)

Let $x_k=k$ for $k \leq 31$ and $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 $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 \in N$ . Find $\lim_{n \rightarrow \infty} z_n$ .

I was only able to figure out $x_{k+1}=x_{k+2}=x_{k+3}.....=16$ for $k \geq 31$ . The trouble is finding $\lim_{n \rightarrow \infty} y_n$ . I have no idea about how would I go on evaluating this.

Any help is appreciated. Thanks!

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

represent the limit of the sequence based on 31 consecutive terms by f(y1,y2...y31), and observe that every change in any of the initial yi affects the limit linearly (this needs to be shown!)

In other words, f(y1,y2,y3...,y31) = (m1)(y1) + (m2)(y2) + ... + (m31)(y31) for some constants mi. Furthermore, observe that sum(mi) = 1, since decreasing all of them by x uniformly obviously reduces f by x.

Also observe that f(y2,y3,y4...,y32) = f(y1,y2,...y_31), that is,

(Note: mi is always the same regardless of the values of yi. Thus, its worth it to substitute more simple values - try f(1,0,0,0,0,0,0,....,0), f(0,1,0,0,0,0...) and so on.)

f(1,0,0,...0) = f(0,0,0,....1/31) implying m31 = 31m1

f(0,1,0,0,0....,0) = f(1,0,0....,0,1/31) implying m2 = m1 + (1/31) (m31) = 2m1

f(0,0,1,0....,0) = f(0,1,...,0,1/31) implying m3 = m2 + (1/31)(m31) = 3m1

Inductively, we get what we want: m1:m2:m3:...:m31 = 1:2:3...:31

Since the sum of them is 1. m1 = 1/(496), m2 = 1/248 ... m_31 = 1/16

Substituting them in will give the desired answer.

Gabriel Wong - 8 years, 1 month ago

Thanks Gabriel for your time but I don't think I get it. This may be a dumb question but how did you bring f(y1,y2...y31)? Can't we simply is say that limit is infinite as the terms yk go on increasing (I found this by substituting a few values for k).

Thank you once again. :)

Pranav Arora - 8 years, 1 month ago

basically, f(y1...y31) represents the limit of the sequence, given that it has 31 consecutive terms y1, y2 ..., y_31, as the limit of the sequence will not be dependent on previous elements.

You do in fact need to show the sequence converges, and that the function f is linear with respect to all yi. There's a theorem that says an infinite bounded set has a limit point - and the set of yi is clearly bounded between 1 and 31 - the theorem isnt sufficient, but it does suggest the sequence converges.

Gabriel Wong - 8 years, 1 month ago

@Gabriel Wong – I can't show that the sequence converges as I haven't yet learned this and I don't think this is even in my coursework. I thought I have missed something as this question is from my test paper. But if it involves convergence theorems, I should probably leave it. Thank you once again for the time you spent on this problem :)

Anyways, I have the solution too. The solution simply evaluates $\displaystyle \lim_{n \rightarrow \infty} y_n$ as $\displaystyle \frac{\sum_{n=1}^{31} n^2}{\sum_{n=1}^{31} n}$ and it was stated without proof so I had to post this here.

Pranav Arora - 8 years, 1 month ago

@Pranav Arora – Hmm yes that limit is the same as what you get when you substitute my values of m_i:

(1/496) + (2)(2/496)+(3)(3/496) ... = (1^2+2^2+3^2+...+31^2)/(496)

= (sum n^2)/(sum n)

If we dispense with the need to prove the sequence converges to a fixed point, and assume it does, as we can now use the function notation and prove linearity very quickly:

f(y1,y2,....y31) - f(y1,y2....,y31+k) = f(y1,y2+....,y31+k) - f(y1,y2+....,y31 +2k) = ...

g(x) = f(y1,y2...y30,x) for fixed y1 to y_30

g(x+kd) = k(g(x+d) - g(x)), implying linearity over rationals.

(you can do the same for the other y_i)

Which you can see fairly easily. Because the function is clearly strictly increasing, and you can quickly prove it is linear for all rationals, it is also linear for reals.

Edit: in fact, if you don't need to prove convergence, you can also use the invariant.

For any 31 consecutive terms a1, a2, ...a31, sum( (i)(ai) ) is constant.

Substituting the initial values (1,2...,31) and comparing with (L,L,L...L) will quickly yield the value of limit L as well.

Gabriel Wong - 8 years, 1 month ago

@Gabriel Wong – Sorry for the late reply.

I have got most of it but not completely. I am still trying to understand your posts. Can you tell me to which part of mathematics does this belong? I have never seen this kind of problem before. I will post if I get any doubts.

Thanks!

Pranav Arora - 8 years, 1 month ago

@Pranav Arora – Frankly I'm not sure where it belongs - since I approached it like an Olympiad problem, I'm not even sure if my method used is 'standard' to begin with. Hopefully Calvin or someone more familiar with analysis can shed light on this

Gabriel Wong - 8 years, 1 month ago

I think the limit of yn is a case of infinite continued fraction series. If you solve y{k+1} it forms a continued fraction.

Shubham Srivastava - 8 years, 1 month ago

How many determinants of order 3by 3 can be formed , in which each element is either a or b (both non zero) and value of determinant is zero

Sachin Arora - 8 years, 1 month ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$