How do we continue at the inductive step?

28 Views Asked by At

Let $\pi\in \text{Sym}(n)$. Then it is of the form $\pi=\pi_1\circ \pi_2\circ \ldots \circ \pi_m$, with $m\leq n$.

We have that $\pi_i$ has maximum length $n$.

We suppose that the $\pi_i$'s are disjoint cycles.

We want to show that $(\pi_1\circ \pi_2\circ \ldots \circ \pi_m)^x= \pi_1^x\circ \pi_2^x\circ \ldots \circ \pi_m^x$ using induction. The induction is on $m$, right?

We have the following:

Base Case : For $m=1$ we have that $\pi=\pi_1$ and so $\pi^x=\pi_1^x$, which is true.

Inductive Hypothesis : We suppose that it holds for $m=k$, i.e. it holds that $(\pi_1\circ \pi_2\circ \ldots \circ \pi_k)^x= \pi_1^x\circ \pi_2^x\circ \ldots \circ \pi_k^x$.

Inductive Step : We want to show that it holds for $m=k+1$. How can we use the inductive hypothesis at $(\pi_1\circ \pi_2\circ \ldots \circ \pi_k\circ \pi_{k+1})^x$ ?