Question

Use strong induction to prove that a function F defined by specifying F (0) and a rule for obtaining F (n + 1) from the values F (k) for k = 0,1,2,......n is well defined.

Short answer

p (n) is true for all integers n.

Step-by-step solution

Step 1:Introduction

A recursive function is a function that its value at any point can be calculated from the values of the function at some previous points.

Induction step

Let p (n) be the statement that F (n) is well-defined.

p (0) is true because F (0) is specified.

Assume that p (k) is true for all k < n .

Therefore, F (n) is well defined at n

Because F (n) is given in terms of F (0), F (1),......F (n - 1) .

Thus, p (n) is true for all integers n.