If $f(x)$ is defined as :
$f(x)=i$ ,if $x\equiv i$ (mod n), $0\leq i< n$
How can I prove whether the following recursive sequences are periodic or not?
$$x_{i+1}=f(k_0+k_1x_{i}+k_2x_{i-1}+…+k_{m+1}x_{i-m})$$
and $$x_i=1,0\leq i< m$$
And for instance, how can I find period of an special case:($k_0=k_1=k_2=1$)
$$x_{i+1}=f(1+x_{i}+x_{i-1}) $$ $$x_0=x_1=1$$
Best Answer
1)All sequences are periodic after a certain point
The first sequences are periodic after a certain integer,and there period is less than $$(m+1)^n $$ In order to prove this you can consider the sequence $$y_k=(x_k,x_{k+1},\cdots,x_{k+m}) $$ and observe that if there exists two integers $i< N$ such that $y_i=y_N$ then $x_i$ is periodic and it's period is less than $N$, the second observation is the fact that $y_k$ can take it's values in the set $[0,n-1]^{m+1}$ which is finite ant it's cardinal is $(m+1)^{n}$ and this means that $N,i$ (in the first observation) must exist.
2)Is all sequences fully periodic from the first point,
This is equivalent to asking whither there exists an integer such $N$ such that: $$y_N=y_1 $$ This is not true in general take for example the sequence (there are simpler examples but this example shows why this could hold): $$n=4\quad f(n)= (n\mod 4)$$ and consider the sequence: $$x_{n+1}=f(4x_{n-4}) $$
3)advanced study of the problem
The sequence as stated is very known and their periodicity is well studied, as you defined the function $f$ to be the identity in $K=\mathbb{Z}_n$ the set of sequences could be defined in the ring $\mathbb{Z}_n$ by : $$x_{i+1}=k_0+k_1x_{i}+k_2x_{i-1}+...+k_{m+1}x_{i-m}$$ and from here, this type of sequences is called : linear recurrence sequences, when $K$ is a field they are related to the roots of their corresponding polynomial $P$ having $k_i$ as coefficients and we can even find a closed form for the sequence $a_k$. In particular, when $K=\mathbb{Z}_n$ with $n$ is a power of a prime, we know a theorem due to Peterson linking the period of the sequence to the smallest integer $r$ such that corresponding polynomial $P$ divides $x^r-1$. See for example the paper: LINEAR RECURRING SEQUENCES OVER FINITE FIELDS for a revue.
The periodicity is studied in "MODULAR PERIODICITY OF LINEAR RECURRENCE SEQUENCES" in general, but there are no more powerful results than what we proved in $(1)$
4) The second question
For the following sequence: $$x_{i+1}=1+x_i+x_{i-1} \quad \quad x_0=x_1=1$$ we consider $y_i=(x_i+1)/2$ we have: $$y_{i+1}=y_i+y_{i-1}\quad \quad y_0=y_1=1 $$ which is a shifted Fibonacci sequence and its period is called the $n$th Pisano period, written $\pi(n)$, and I don't know a closed form for this number but it's also well studied and you can prove a lot of relations between these numbers.