Question

F1 is a set of functions of one real variable defined recursively as follows.
● Base case
○ f(x) = 1, then f ∈ F1
○ f(x) = x, then f ∈ F1
● Constructor case
○ f, g ∈ F1, then f × g ∈ F1 and f + g ∈ F1
a. Prove by ordinary induction that () = nx + n , n ≥ 1 is in F1.
b. Prove by structural induction that if f(x) is in F1, then f(0) ≥ 0.

Answer 1

Answer:

F1 is a set of functions of one real variable defined recursively as follows.

● Base case

○ f(x) = 1, then f ∈ F1

○ f(x) = x, then f ∈ F1

● Constructor case

○ f, g ∈ F1, then f × g ∈ F1 and f + g ∈ F1

a. Prove by ordinary induction that () = nx + n , n ≥ 1 is in F1.

b. Prove by structural induction that if f(x) is in F1, then f(0) ≥ 0.

Answer 2

A Recursive Function is defined as: We say the function f is defined recursively if the value of f at 1 is specified and if a rule is provided for determining f(n+1) from f(n).

Explanation:

• The question implies a "general" proof

            $Let\ f:N\to R\\f':N\to R,\\g:R\to R,\\f(1)=f'(1)=x_1\in R,\\f(x+1)=g(f(x)),\\f'(x+1)=g(f'(x)).\\Whereasf(1)=x_1,f(2)=g(x_1),f(3)=g(g(x_1)),f(4)=g(g(g(x_1)))$

• Similarly for f′.

• Prove by induction that for all x∈N, we have f(x)=f′(x).

• Base case: f(1)=f′(1).

• Inductive Step:

• Suppose f(k)=f′(k), therefore f(k+1)=f′(k+1).