Results 1 to 5 of 5

Math Help - Proof Inverse Function

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    3

    Proof Inverse Function

    Hi there,

    I doing a proof problem and I am not sure if my proof is valid. Your help is greatly appreciated.

    Problem:

    Let A be a nonempty set and let f: A --->A. For each n that is in the natural numbers, define a function f^n: A ----> A recursively as follows: f^1= f,
    f^(n+1) = f o f^n and f^2 = f o f^1

    Let f(x) = x+1. Determine a formula for f^n(x) and use induction t prove that your formula is correct.

    Proof:
    Let n be a natural number.
    x+n = f^n(x+1)

    Prove P(1)
    x+1 = f^1(x+1)
    = x+1

    P(k)
    x+k = f^k (x+1)

    Assume P(k) is true so then P(k+1) is true.
    That is,
    (x+k) + (x+(k+1)) = f^(k+1)(x+1).

    So,

    (x+k) + (x+(k+1)) = f^k(x+1) + (x+(k+1))
    = (x+k) + (x+(k+1))
    = f^(k+1)(x+1) substitution since
    f^(k+1)(x+1) is ( (x+k) + (x+ (k+1)))

    QED





    Thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by applebee View Post
    Hi there,

    I doing a proof problem and I am not sure if my proof is valid. Your help is greatly appreciated.

    Problem:

    Let A be a nonempty set and let f: A --->A. For each n that is in the natural numbers, define a function f^n: A ----> A recursively as follows: f^1= f,
    f^(n+1) = f o f^n and f^2 = f o f^1

    Let f(x) = x+1. Determine a formula for f^n(x) and use induction t prove that your formula is correct.

    Proof:
    Let n be a natural number.
    x+n = f^n(x+1)

    Prove P(1)
    x+1 = f^1(x+1)
    = x+1

    P(k)
    x+k = f^k (x+1)

    Assume P(k) is true so then P(k+1) is true.
    That is,
    (x+k) + (x+(k+1)) = f^(k+1)(x+1).

    So,

    (x+k) + (x+(k+1)) = f^k(x+1) + (x+(k+1))
    = (x+k) + (x+(k+1))
    = f^(k+1)(x+1) substitution since
    f^(k+1)(x+1) is ( (x+k) + (x+ (k+1)))
    Your proof is incorrect:
    You assumed f^{(k)}(x) = x+k. So what you would want to prove is that f^{(k+1)}(x) = x+k+1, not f^{(k+1)}(x) = (x+k) + (x+k+1).

    Try proving it now, and please be more clear with what you do in each step (try to justify it as well), otherwise it is very difficult for us to understand and help you.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    3
    Thanks for replying and I will keep that in mind.

    This is what I want.


    So,
    .x+k+1 = f^k (x) + (x+k+1)

    Since f^k (x) = x+k, I use substitution, so

    = (x+k) + (x+k +1)

    = 2x + 2k + 1

    I'm not sure where I go from here. How can I get to f^(k+1)(x) ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by applebee View Post
    Thanks for replying and I will keep that in mind.

    This is what I want.


    So,
    .x+k+1 = f^k (x) + (x+k+1) How did you reach this? It is incorrect...

    Since f^k (x) = x+k, I use substitution, so

    = (x+k) + (x+k +1)

    = 2x + 2k + 1

    I'm not sure where I go from here. How can I get to f^(k+1)(x) ?
    You assume f^{(k)}(x) = x+k and you want to prove f^{(k+1)}(x) = x+k+1.

    Now, use the fact that f^{(k+1)} = f^{(k)}\circ f to get:

    f^{(k+1)}(x) = f^{(k)}(f(x)) = f^{(k)}(x+1)

    Now, according to our assumption, f^{(k)}(x) = x+k \Rightarrow f^{(k)}(x+1) = x+k+1

    Substitute that back into our equation to get f^{(k+1)}(x) = f^{(k)}(x+1) = x+k+1

    And we are done. It seems as if you need to do a little revision of the principles of induction...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    3
    Thanks.

    When it comes to mathematical proof, I am very slow at understanding them. I have never thought about writing f^(k+1)(x) as f^k(f(x)) . I have another problem just like this, and I will use your work as a guide. Thank you so much.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: April 19th 2013, 04:05 PM
  2. [SOLVED] Proof: Intersection, Inverse Function
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 21st 2011, 01:48 AM
  3. Replies: 2
    Last Post: September 8th 2010, 01:27 AM
  4. inverse proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 15th 2010, 07:57 AM
  5. Replies: 2
    Last Post: September 22nd 2009, 09:29 PM

Search Tags


/mathhelpforum @mathhelpforum