Facebook Page
Twitter
RSS
+ Reply to Thread
Results 1 to 6 of 6
  1. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,815
    Thanks
    3,029 times
    Thanked
    995 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #1
    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?

  2. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

  3. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    Klaas van Aarsen's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Leiden
    Posts
    8,403
    Thanks
    5,435 times
    Thanked
    14,615 times
    Thank/Post
    1.739
    Awards
    MHB Pre-University Math Award (2018)  

MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)
    #2
    Quote Originally Posted by mathmari View Post
    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}$?

    Quote Originally Posted by mathmari View Post
    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.

  4. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,815
    Thanks
    3,029 times
    Thanked
    995 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #3 Thread Author
    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}$.


  5. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    Klaas van Aarsen's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Leiden
    Posts
    8,403
    Thanks
    5,435 times
    Thanked
    14,615 times
    Thank/Post
    1.739
    Awards
    MHB Pre-University Math Award (2018)  

MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)
    #4
    Quote Originally Posted by mathmari View Post
    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?

    Quote Originally Posted by mathmari View Post
    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?

    Quote Originally Posted by mathmari View Post
    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}$.

  6. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,815
    Thanks
    3,029 times
    Thanked
    995 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #5 Thread Author
    Quote Originally Posted by Klaas van Aarsen View Post
    What do you mean by maximum length?
    I forgot the index. It should be: The cycle $\pi_i$ has maximum length $n$.


    Quote Originally Posted by Klaas van Aarsen View Post
    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?

  7. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    Klaas van Aarsen's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Leiden
    Posts
    8,403
    Thanks
    5,435 times
    Thanked
    14,615 times
    Thank/Post
    1.739
    Awards
    MHB Pre-University Math Award (2018)  

MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)
    #6
    Quote Originally Posted by mathmari View Post
    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$.

Similar Threads

  1. induction
    By markosheehan in forum Pre-Algebra and Algebra
    Replies: 3
    Last Post: September 19th, 2016, 16:08
  2. induction
    By sarrah in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 1
    Last Post: April 23rd, 2016, 14:04
  3. Induction
    By evinda in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 3
    Last Post: February 26th, 2015, 07:58
  4. Induction
    By evinda in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 5
    Last Post: October 9th, 2014, 15:30
  5. Induction Help
    By crypt50 in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 2
    Last Post: June 30th, 2013, 11:16

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards