How many functions respect the equation 3 f ( f ( x ) ) − 7 f ( x ) + 2 x = 0

Question

How many functions respect the equation   3  f  (  f  (  x  )  )  −  7  f  (  x  )  +  2  x  =  0

motylowceyvy · Accepted Answer

Fix x and let       a    n    =      f    n    (  x  ) (n-th iteration of f). Then we have  3      a          n      +      1        −  7      a    n    +  2      a          n      −      1        =  0Solving this recurrence we get      a    n    =  a  ⋅      2    n    +  b  ⋅            1              3        n            for some a,b. Since       a    0    =  x and       a    1    =  f  (  x  ) we have   x  =  a  +  b and   f  (  x  )  =  2  a  +  b      /    3. Solving this on a,b we get  a  =                    3        f        (        x        )        −        x            5                    a    n    d            b  =                    6        x        −        3        f        (        x        )            5      Since x,f(x) are integers we have   a  =  c      /    5 and   b  =  d      /    5 for some integers c,d. So we have  5      a    n    −  c  ⋅      2    n    =  d  ⋅            1              3        n                ⟹        3    n    ∣  d          ∀  n  ∈      N  which is possible only iff d=0 and so b=0. Thus we have   f  (  x  )  =  2  x

MMDCCC50m · Accepted Answer

Consider   g  (  x  )  =  f  (  x  )  −  2  x. If   f  :      Z    →      Z   then   g  :      Z    →      Z    3  f  (  f  (  x  )  )  =  7  f  (  x  )  −  2  x  ⇒  3  g  (  f  (  x  )  )  =  3  f  (  f  (  x  )  )  −  6  f  (  x  )  =  f  (  x  )  −  2  x  =  g  (  x  )  ⇒  g  (  f  (  x  )  )  =            g      (      x      )        3  Suppose that   g  (      x    1    )  ≠  0 for some       x    1    ∈      Z  . Consider infinite sequence   (      a    n    ), such that       a    i    =      |    g  (      b    i    )      |  ,       b    1    =      x    1  ,       b          i      +      1        =  f  (      x    i    ). Then       a          i      +      1        =            a      i        3   and       a    i    ∈      Z  . Sequence   (      a    n    ) is decreasing, positive and integer. That is impossible. Contradiction.Then   g  (  x  )  =  0 for all   x  ∈      Z  . Then   f  (  x  )  =  2  x is the only function       Z    →      Z   to satisfy the given equation.

How many functions respect the equation 3f(f(x))−7f(x)+2x=0

Answered question

Answer & Explanation

New Questions in Algebra I