Si $\alpha=(a_1a_2...a_k)$ es un $k$ -ciclo, entonces $\alpha^i(a_j)=a_{(j+i)\text{ mod }k}$ .

Question

Intento demostrar que si $\alpha=(a_1a_2...a_k)$ es un $k$ -entonces para todo $i\in\{1,2,...,k\}$ tenemos $\alpha^i(a_j)=a_{(j+i)\text{ mod }k}$ . Esperaba que la gente pudiera comprobar mi prueba y tal vez comentar si es más natural utilizar la inducción simple o la inducción fuerte.

Prueba (fuerte)

En $i=1$ si $j<k$ entonces por definición del ciclo $\alpha=(a_1a_2...a_k)$ tenemos $\alpha(a_j)=a_{(j+1)}=a_{(j+1)\text{ mod }k}$ desde $j+1\leq k$ si $j<k$ y $a_{0 \text{ mod } k}= a_{k\text{ mod } k}$ . Si $j=k$ entonces de nuevo por definición del ciclo $\alpha=(a_1a_2...a_k)$ tenemos $\alpha(a_j)=\alpha(a_k)=a_1=a_{(k+1)\text{ mod }k}$ .

Supongamos ahora por inducción que para todo $i$ menos de $k$ y mayor que $1$ que $\alpha^i(a_j)=a_{(j+i)\text{ mod }k}$ retenciones. Sea $i=k$ . Entonces $$\alpha^i(a_j)=\alpha^k(a_j)=\alpha(\alpha^{k-1}(a_j))$$ pero por la hipótesis de inducción $\alpha^{k-1}(a_j)=a_{(j+k-1)\text{ mod }k}$ así que $$\alpha^i(a_j)=\alpha^k(a_j)=\alpha(\alpha^{k-1}(a_j))=\alpha(a_{(j+k-1)\text{ mod }k}).$$

Ahora bien, puesto que $(j+k-1)\text{ mod }k +1 =(j+k-1)\text{ mod }k+(1)\text{ mod }k=(j+k)\text{ mod }k$ y $(j+k-1)\text{ mod }k\leq k $ tenemos

de nuevo por definición del ciclo $\alpha=(a_1a_2...a_k)$ eso:

$$\alpha(a_{(j+k-1)\text{ mod }k})=a_{(j+k)\text{ mod }k}=a_{(j+i)\text{ mod }k}$$ así que $\alpha^i(a_j)=a_{(j+i)\text{ mod }k}$ . Así pues, la afirmación es válida para $i=k$ y por inducción $\alpha^i(a_j)=a_{(j+i)\text{ mod }k}$ es válida para cualquier $k$ -ciclo donde $k\in\mathbb{Z^+}$ . $\blacksquare$

Prueba: (sencillo)

En $i=1$ si $j<k$ entonces por definición del ciclo $\alpha=(a_1a_2...a_k)$ tenemos $\alpha(a_j)=a_{(j+1)}=a_{(j+1)\text{ mod }k}$ desde $j+1\leq k$ si $j<k$ y $a_{0 \text{ mod } k}= a_{k\text{ mod } k}$ . Si $j=k$ entonces de nuevo por definición del ciclo $\alpha=(a_1a_2...a_k)$ tenemos $\alpha(a_j)=\alpha(a_k)=a_1=a_{(k+1)\text{ mod }k}$ .

Supongamos ahora por inducción que $\alpha^i(a_j)=a_{(j+i)\text{ mod }k}$ es válida para $i\in\{1,2,...,k\}$ . Entonces por la hipótesis de inducción: $$\alpha^{i+1}(a_j)=\alpha(\alpha^i(a_j)=\alpha(a_{(j+i)\text{ mod }k})$$

así que por definición del ciclo $\alpha=(a_1a_2...a_k)$ y que $(j+i)\text{ mod }k\leq k$ tenemos

$$\alpha(a_{(j+i)\text{ mod }k})=a_{(j+i+1)\text{ mod }k}.$$

Por lo tanto, la afirmación es válida para todos los $i$ en $\{1,2,...k\}$ y para todos los números enteros $k$ . $\blacksquare$

¿Hay alguna laguna, concretamente en la(s) etapa(s) de inducción señalada(s)? Me preocupa no estar teniendo en cuenta los casos en los que el elemento es el último del ciclo. $(=k)$ . Gracias de antemano.

Answer 1

En cuanto a su enfoque principal (expresado en un comentario), partamos de la definición de $k$ -ciclo:

$\alpha(a_i)=a_{i+1}$ para $i=1,\dots,k-1$

$\alpha(a_k)=a_1$

---

Paso para conocer la fórmula a demostrar por inducción:

$\alpha^2(a_i)=\alpha(a_{i+1})=a_{i+2}$ para $i=1,\dots,k-2$

$\alpha^2(a_{k-1})=\alpha(\alpha(a_{k-1}))=\alpha(a_k)=a_1$

$\alpha^2(a_{k})=\alpha(\alpha(a_{k}))=\alpha(a_1)=a_2$

Así pues, la definición correcta del $j$ -ésima potencia de $\alpha$ , $1\le j\le k$ se basa en la división del conjunto $\{1,\dots, k\}$ en $\{1,\dots, k-j\}$ y $\{k-j+1,\dots, k\}$ que debe formar parte del proceso de inducción.

---

Inducción :

Hipótesis inductiva ("i.h."):

1. $\alpha^j(a_i)=a_{i+j}$ para $i=1,\dots,k-j$
2. $\alpha^j(a_{k-j+l})=a_l$ para $l=1,\dots,j$

Para $j=1$ recuperamos la definición de $k$ -ciclo. Ahora para $j+1$ :

• para $i=1,\dots,k-(j+1)$ , obtenemos: $\alpha^{j+1}(a_i)=$ $\alpha(\alpha^j(a_i))\stackrel{(i.h.)}{=}$ $\alpha(a_{i+j})\stackrel{(j+1\le i+j\le k-1)}{=}a_{i+(j+1)}$ ;

• para $l=1,\dots,j+1$ , obtenemos: $\alpha^{j+1}(a_{k-(j+1)+l})=$ $\alpha(\alpha^j(a_{k-(j+1)+l}))=$ $\alpha(\alpha^j(a_{k-j+(l-1)}))$ ahora:

  • para $l=1$ , obtenemos: $\alpha(\alpha^j(a_{k-j+(l-1)}))=$ $\alpha(\alpha^j(a_{k-j}))\stackrel{(i.h.,\text{ part 1})}{=}$ $\alpha(a_k)=a_1$ ;
  • para $l=2,\dots,j+1$ , obtenemos: $\alpha(\alpha^j(a_{k-j+(l-1)}))\stackrel{(i.h.,\text{ part 2})}{=}$ $\alpha(a_{l-1})=$ $a_l$ ,

  y por lo tanto $\alpha^{j+1}(a_{k-(j+1)+l})=a_l$ para cada $l=1,\dots,j+1$ . $\space\Box$

---

Para $j<k$ de la parte 1 sigue $\alpha^j(a_1)=a_{j+1}\ne a_1$ y, por tanto $\alpha^j\ne Id$ .

Por otra parte, para $j=k$ la parte 2 cuenta toda la historia, que es: $\alpha^k(a_l)=a_l$ para $l=1,\dots,k$ a saber $\alpha^k=Id$ .

Por lo tanto, $\left|\alpha\right|=k$ .