Dejemos que $a_{n+3}=a_{n+2}+a_{n+1}+a_n$ Demostrar que $\forall N\in \mathbb Z^+ , \exists a_k$ s.t. $N\mid a_k$

Question

Definir la secuencia $(a_n)$ tal que $$a_0=0, a_1=a_2=1\quad a_{n+3}=a_{n+2}+a_{n+1}+a_n$$ Demostrar que $\forall N\in \mathbb Z^+ , \exists a_k$ s.t. $N|a_k$

Tenga en cuenta que si la secuencia $(a_n)$ es periódico $\mod N$ y se nos da $$a_0=0\equiv 0\pmod N, \quad \forall N \in \mathbb Z^+$$ entonces hemos terminado. Porque habría $a_k\equiv a_0\equiv 0\pmod N$ .

Pero no tengo ni idea de cómo probarlo $(a_n)$ es periódica.

Answer 1

Dejemos que $S=\{0,1,2,...,N-1\}$ y $$A=\{(a_n, a_{n+1}, a_{n+2})\pmod N\mid n\in \mathbb N\}$$ donde $(a_n, a_{n+1}, a_{n+2})\pmod N=(a_n\pmod N, a_{n+1}\pmod N, a_{n+2}\pmod N)$ (Sólo una anotación)

Tenga en cuenta que $ A\subseteq S^3$ así $| A| \le | S|^3=N^3< \infty= | \mathbb N| $ . Por lo tanto, por el principio de piegonhole $\exists n\ne k$ tal que $$(a_n, a_{n+1}, a_{n+2})\pmod N=(a_k, a_{k+1}, a_{k+2})\pmod N$$ Significado $$\cases{a_n\equiv a_k\pmod N \\ a_{n+1}\equiv a_{k+1}\pmod N\\ a_{n+2}\equiv a_{k+2}\pmod N} \implies a_{n+3}\equiv a_{k+3}\pmod N$$

Usando la inducción no es difícil demostrar $$a_{n+s}\equiv a_{k+s}, \quad \forall s\ge 0$$ pero también tenemos $$a_n=a_{n+3}-a_{n+2}-a_{n+1}$$ Por lo tanto, $$a_{n+s}\equiv a_{k+s}, \quad \forall s\in \mathbb Z$$ Mientras bajamos nos encontraremos con $a_0=0\equiv 0\pmod N$ .

El encasillamiento siempre me parece mágico.