# Do we use induction?

#### mathmari

##### Well-known member
MHB Site Helper
Hey!!

1. Let $1\leq n\in \mathbb{N}$ and $\pi\in \text{Sym}(n)$. For $1\leq k\in \mathbb{N}$ we define $\pi^{-k}:=\left (\pi^n\right )^{-1}$.

Show for all $k,\ell\in \mathbb{Z}$ the equation $\pi^k\circ \pi^{\ell}=\pi^{k+\ell}$.

2. Let $1\leq n\in \mathbb{N}$. Show that $\pi^{n!}=\text{id}$ for all $\pi\in \text{Sym}(n)$.

Do we show both statements using induction?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hey!!

1. Let $1\leq n\in \mathbb{N}$ and $\pi\in \text{Sym}(n)$. For $1\leq k\in \mathbb{N}$ we define $\pi^{-k}:=\left (\pi^n\right )^{-1}$.
Hey mathmari !!

Is that a typo? Shouldn't it be $\pi^{-k}:=\left (\pi^k\right )^{-1}$?

Show for all $k,\ell\in \mathbb{Z}$ the equation $\pi^k\circ \pi^{\ell}=\pi^{k+\ell}$.

2. Let $1\leq n\in \mathbb{N}$. Show that $\pi^{n!}=\text{id}$ for all $\pi\in \text{Sym}(n)$.

Do we show both statements using induction?
I don't think we need induction for 1.
Instead I think we need to distinguish cases.
If k and l are positive, the relation follows from the definition of repeated application of a function.
However, if either is negative or zero, we still need to see what happens.

For question 2, I think we need group theory. Specifically that the order of an element divides the size of a finite group. Then we don't need induction.

#### mathmari

##### Well-known member
MHB Site Helper
I noticed now that the hint for induction is for question 1.

There is the following hint:

$\pi\in \text{Sym}(n)$

$\pi=\pi_1\circ \pi_2\circ \ldots \circ \pi_m$, $m\leq n$

$\pi$ has maximum length $n$

We are looking for $x\in \mathbb{N}$ such that $\pi^x=(\pi_1\circ \pi_2\circ \ldots \circ \pi_m)^x\ \overset{\text{Induction}}{ =} \ \pi_1^x\circ \pi_2^x\circ \ldots \circ \pi_m^x=\text{id}$

For $1\leq i\leq m$ the $\pi_i$ is a cycle of length $m_i$.

It holds that $(\pi_i)^{m_i}=\text{id}$ so $(\pi_i)^{n!}=\text{id}$ .

Then $\pi^{n!}=\pi_1^{n!}\circ \pi_2^{n!}\circ \ldots \circ \pi_m^{n!}=\text{id}\circ \text{id}\circ \ldots \circ \text{id}=\text{id}$.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
I noticed now that the hint for induction is for question 1.

There is the following hint:

$\pi\in \text{Sym}(n)$

$\pi=\pi_1\circ \pi_2\circ \ldots \circ \pi_m$, $m\leq n$

$\pi$ has maximum length $n$
What do you mean by maximum length?

We are looking for $x\in \mathbb{N}$ such that $\pi^x=(\pi_1\circ \pi_2\circ \ldots \circ \pi_m)^x\ \overset{\text{Induction}}{ =} \ \pi_1^x\circ \pi_2^x\circ \ldots \circ \pi_m^x=\text{id}$

For $1\leq i\leq m$ the $\pi_i$ is a cycle of length $m_i$.
I don't think this is true in general.
Consider for instance $(1) \circ (1\,2) \circ (1\,2\,3) = (2\,3)$ and $x=3$.
Then:
$$\big((1) \circ (1\,2) \circ (1\,2\,3)\big)^3 = (2\,3)^3=(2\,3) \ne (1\,2)= (1)^3 \circ (1\,2)^3 \circ (1\,2\,3)^3$$
isn't it?

Is it perhaps supposed to be a disjoint decomposition in cycles?

It holds that $(\pi_i)^{m_i}=\text{id}$ so $(\pi_i)^{n!}=\text{id}$ .

Then $\pi^{n!}=\pi_1^{n!}\circ \pi_2^{n!}\circ \ldots \circ \pi_m^{n!}=\text{id}\circ \text{id}\circ \ldots \circ \text{id}=\text{id}$.

#### mathmari

##### Well-known member
MHB Site Helper
What do you mean by maximum length?
I forgot the index. It should be: The cycle $\pi_i$ has maximum length $n$.

I don't think this is true in general.
Consider for instance $(1) \circ (1\,2) \circ (1\,2\,3) = (2\,3)$ and $x=3$.
Then:
$$\big((1) \circ (1\,2) \circ (1\,2\,3)\big)^3 = (2\,3)^3=(2\,3) \ne (1\,2)= (1)^3 \circ (1\,2)^3 \circ (1\,2\,3)^3$$
isn't it?

Is it perhaps supposed to be a disjoint decomposition in cycles?
Ahh ok! So if we suppose that $\pi_i\neq \pi_j$ for $i\neq j$, does the above hold?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
I forgot the index. It should be: The cycle $\pi_i$ has maximum length $n$.

Ahh ok! So if we suppose that $\pi_i\neq \pi_j$ for $i\neq j$, does the above hold?
That is not enough, is it?
If any pair $\pi_i$ and $\pi_j$ are cycles that overlap, the result won't hold.

However, if the cycles are disjoint, the result does hold.
So if for instance $\pi=(1\,2\,3)(5\,6)$ with $\pi_1=(1\,2\,3)$ and $\pi_2=(5\,6)$, we have for any $x\in\mathbb Z$:
$$\pi^x = \big((1\,2\,3)\circ (5\,6)\big)^x = (1\,2\,3)^x \circ (5\,6)^x$$
Then we have $m=2$ and $m_1=3,\,m_2=2$.