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