2
$\begingroup$

This is a question on the test review packet I have for discrete mathematics.

Given: $f = \{(a, b), (b, a), (c, b)\}$ a function from $X = \{a, b, c\}$ to $X.$

(a) Write $f \circ f$ and $f \circ f \circ f$ as sets of ordered pairs.

(b) Define $f^n = f \circ f \circ \ldots \circ f$ to be the $n$-fold composition of $f$ with itself. Write $f^9$ and $f^{623}$ as sets of ordered pairs.

For part (a), I believe: $$ f(a) = b\\ f(b) = a\\ f(c) = b\\ f(f) = \{(a, a), (b, b), (c, a)\} \\ f(f(f)) = \{(a, b), (b, a), (c, b)\}$$

I think there is a pattern here with even exponents being equal to $$ f(f) = \{(a, a), (b, b), (c, a)\}$$ and odd being equal to $$f(f(f)) = \{(a, b), (b, a), (c, b)\}.$$

So how do we define $f^n = f \circ f \circ \ldots \circ f$ to be the $n$-fold composition of $f$ with itself?

Also I believe, $f^9$ and $f^{623}$ would both be $\{(a, b), (b, a), (c, b)\}.$

  • 0
    You made a mistake. $f = \{(\color{red}{a}, \color{blue}{b}), (\color{red}{b}, \color{blue}{a}), (\color{red}{c}, \color{blue}{b})\}$ means that $f(\color{red}{a}) = \color{blue}{b}, f(\color{red}{b}) = \color{blue}{a}, f(\color{red}{c}) = \color{blue}{b}.$2012-04-01
  • 0
    But, your expressions for $f(f)$ and $f(f(f))$ are correct.2012-04-01
  • 0
    Yes, I mistyped it on accident, corrected thanks. How does part b look?2012-04-01

1 Answers 1

2

Hints:

  1. From your solution, note that: $f^3 = f.$

  2. Property of composition: $f^{n} = f \circ f^{n-1} = f^{n-1} \circ f$

  3. $f^9 = f^3 \circ f^3 \circ f^3$

  4. Think about modular arithmetic. $3 \equiv 1 \pmod{\color{red}{??}}$ and $9 \equiv 1 \pmod{\color{red}{??}}.$ Figure out $\color{red}{??}$ and think about $623 \equiv\ \color{blue}{??} \pmod{\color{red}{??}}$

  5. The general form should be apparent: $f^n = f^{n\pmod{\color{red}{??}}}$

  • 0
    3≡1 (mod 2) 9≡1 (mod 2) 623≡1 (mod 2)? I don't really understand modular arithmetic very well to be honest.2012-04-01
  • 0
    @wazy That's corrent. Alternatively, in your original post your said there are two patterns: odd and even. Do you know programming? In programming, we often use $\pmod{2}$ to test for odd/even.2012-04-01
  • 0
    So part b would be f^n=f^n(mod 2). I wrote f^623 and f^9 as sets of ordered pairs already and I know some MIPS programming with the HI storing the remainder or I guess the mod.2012-04-01
  • 0
    No. Because an even number `mod 2` = 0. You want to say even $n \to 2$, odd $n \to 1.$2012-04-01
  • 0
    If you're not comfortable with modular arithmetic. You can just write it as two cases.2012-04-01
  • 0
    Yea that is easier for me. Thanks for the help. Do you mind editing your answer? (I'm going to note this and continue on with the packet before coming back and correcting it.)2012-04-01