 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-1/12i/solution

Codex  0 Created 2026-09-23 Updated 2026-09-25

The primitive recursive functions are the smallest class containing zero, successor, and projections and closed under composition and primitive recursion. Addition is defined by

P (m, 0) = m, P (m, n + 1) = S (P (m, n)),

T (m, 0) = 0, T (m, n + 1) = P (T (m, n), m) .

Thus both are primitive recursive directly from the definition. Inductively,

T_{k + 1} (n_{1}, \dots, n_{k + 1}) = T (T_{k} (n_{1}, \dots, n_{k}), n_{k + 1})

is primitive recursive. For fixed

a

E_{a} (0) = 1, E_{a} (n + 1) = T (a, E_{a} (n)),

E_{a} (n) = a^{n}

is primitive recursive.

Encode

(x_{0}, \dots, x_{k - 1})

2^{x_{0}} 3^{x_{1}} \dots p_{k}^{x_{k - 1}}

. The exponent functions

M_{p_{i}}

decode the coordinates. Therefore

\overline{F} (N) = \prod_{i = 0}^{k - 1} p_{i + 1}^{f_{i} (M_{2} (N), M_{3} (N), \dots, M_{p_{k}} (N))}

is a primitive recursive one-number encoding of

F

; the finite product is built from the primitive recursive multiplication and exponentiation just established.

The Fibonacci function is primitive recursive. Encode the pair

(B (n), B (n + 1))

C (n) = 2^{B (n)} 3^{B (n + 1)} .

Starting with

C (0) = 3

C (n + 1) = 2^{M_{3} (C (n))} 3^{M_{2} (C (n)) + M_{3} (C (n))}

constructs

C

, and

B (n) = M_{2} (C (n))

There is no universal exponential bound of the stated form. The primitive recursive function

f (n) = 2^{n^{2}}

exceeds

R^{n}

for every fixed

R > 0

once

n

is sufficiently large.

 New to topics? Read the docs here!