Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/ii/paper-1/12g/c/solution

Let be the successor function. Define by primitive recursion
Induction gives . Then define
by composition. Initial functions, composition, and primitive recursion produce primitive recursive functions, so and are partial recursive functions and are visibly defined for every . Both functions are total.

New to topics? Read the docs here!