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