Thread: 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

Originally Posted by applebee

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 . So what you would want to prove is that , not .

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.

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) ?

Originally Posted by applebee

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 and you want to prove .

Now, use the fact that to get:



Now, according to our assumption,

Substitute that back into our equation to get

And we are done. It seems as if you need to do a little revision of the principles of induction...

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.