A specific kind of Moving average

Question

The problem is :

Consider the list consisting of the first n natural numbers without zero, ie from $1$ to $n$. We define the transformation "moving average" on the list of $n$ elements by adding the average of all the terms at the end of the list and eliminating the first term at the beginning of the list. For example, if $n = 4$, we have: $$(1,2,3,4) \rightarrow (2,3,4,2.5)$$ By iterating this process many times, one can observe a phenomenon of standardization and that all elements of the list tend to a common value when the number of iterations tends to $ +\infty $.

For what value of $n$ is this limit $254859658745$?

I did a little program some month ago, which didn't work and works now. But it seems so be this problem must be solved using maths. More, I haven't find anything on the net about this kind of problem, and I don't know what to do with it.

Any ideas or tips ?

---

EDIT

You want me to add details. Its not me who make this problem, I ask it there exactly like I found it!

As I understand the problem using the same example in the problem what we need to do is $(1,2,3,4) \rightarrow (2,3,4,2.5)\rightarrow (3,4,2.5,23/8) \rightarrow $ etc ...

Thank you in advance

Answer 1

My numeric investigations show that for a given $n$ the list values all tend toward $$r=\frac{2n+1}3$$

Therefore, if you are given the repeated value $r$, you can find $n$ from

$$n=\frac{3r-1}2$$

The complete proof escapes me so far, however. So far I see that the transformation is linear, and it appears that the only real eigenvalue is $1$ and the only real eigenvectors are scalar multiples of $(1,1,\ldots,1)$. This shows that the list does converge to repeated values but it does not show which value will be repeated.

My "numeric investigations" mostly used Microsoft Excel 2013. I just put the initial list in the top row and put formulas in the second row: cell A2 is =B1, B2 is =C1, up to the last column, which changes but for $n=7$ gives G2 is =AVERAGE(A1:G1). I copy that row down about $50$ rows, which clearly shows the limits. I did this for a variety of values of $n$ and the pattern $\frac{2n+1}3$ quickly appeared. This is a good heuristic but is no proof. The limits of each list item is simple, but the average and sum of the items in each list fluctuates up and down and is not so easy, though the limit of that is clear. I used my TI-Nspire CX graphing calculator to investigate eigenvalues and eigenvectors.

Answer 2

I kinda having the same problem, I solved it numerically but analytically it's not easy.

If you write the problem in term of a recursive sequence, we'll have:

$S_{n}=\frac{1}{k}({\sum} S_{n-i})$

with $n>k$, $i=1,2,...,k$ and $S_1=1, S_2=2, S_3=3, etc.$

From there you can solve it by normal ways using either: characteristic equation, generating function or matrix form, and then take the limit of the general term.

For the case $k=2$ it's straight forward, everything can be solved by hand. For your particular example $k=3$, it involves complexe numbers, but you can still rather solve it, and notice that the number k appears in the limit.

But find out the limit analytically for any value $k>3$ is pretty hard. The good thing is that the structure of the limit stay more or less the same, once you found it out. Otherwise, proving convergence is easy, using eigenvalues of the mapping matrix (stochastic matrix => spectral radius = 1) or nesting interval for each block of k (the value of the first block are increasing, then by the average operator, you create wave form fluctuations around the limit).