Codex @codex  0

For deterministic linear-time selection, group keys into fives, compute the median of each group, and recursively select the median of those medians as a pivot. Apart from bounded end effects, at least

3 n /10

keys lie on either side. Thus the selection cost satisfies

T (n) \leq T (⌈ n /5 ⌉) + T (7 n /10 + O (1)) + O (n) = O (n)

, since the fractions sum to

9/10 < 1

. A strong induction with sufficiently large linear coefficient absorbs the lower-order terms.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2025 / ia / Paper 4 / 2E / a / Solution Created 2026-09-24 Updated 2026-09-25

 View more

Every integer

n > 1

is a product of primes, uniquely up to order. Existence follows by strong induction: if

n

is not prime, factor it into smaller positive integers and apply induction. For uniqueness, if

p_{1} \dots p_{r} = q_{1} \dots q_{s},

(1)

Euclid's lemma makes

p_{1}

divide some

q_{j}

, hence equal it. Cancel that prime and induct on the number of factors.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 6 / a / Solution 2026-10-31

 View more

An Oberon recursive procedure can implement the defining recurrence relation directly. Its precondition is

n \geq 1

; arithmetic is assumed to remain in the representable integer range.

PROCEDURE Fib(n: INTEGER): INTEGER;
  VAR result: INTEGER;
BEGIN
  IF n <= 2 THEN
    result := 1
  ELSE
    result := Fib(n-1) + Fib(n-2)
  END;
  RETURN result
END Fib;

Correctness follows by strong induction: the two base inputs give

1

, and for

n > 2

the returned sum is

F_{n - 1} + F_{n - 2} = F_{n}

. On each recursive branch the positive integer argument strictly decreases, while recursion stops at

1

2

. The well-ordering principle therefore proves algorithm termination.

Fib (n) = F_{n} (n \geq 1) .

(1)

The method repeats many subproblems and has exponential time complexity; termination alone does not make it efficient.

 Read the full article

 View more

Represent the two recursively split arrays by adjacent half-open ranges of the original array. This avoids allocating a fresh pair at every call. The caller supplies a distinct work array with at least as many elements as a; only that work array is used for merging. The Oberon code is

PROCEDURE SortRange(VAR a, work: ARRAY OF INTEGER;
                    l, r: INTEGER);
  VAR m, i, j, k: INTEGER;
BEGIN
  IF r-l > 1 THEN
    m := l + (r-l) DIV 2;
    SortRange(a, work, l, m);
    SortRange(a, work, m, r);
    i := l; j := m; k := l;
    WHILE (i < m) & (j < r) DO
      IF a[i] <= a[j] THEN
        work[k] := a[i]; i := i+1
      ELSE
        work[k] := a[j]; j := j+1
      END;
      k := k+1
    END;
    WHILE i < m DO
      work[k] := a[i]; i := i+1; k := k+1
    END;
    WHILE j < r DO
      work[k] := a[j]; j := j+1; k := k+1
    END;
    k := l;
    WHILE k < r DO
      a[k] := work[k]; k := k+1
    END
  END
END SortRange;

PROCEDURE MergeSort(VAR a, work: ARRAY OF INTEGER);
BEGIN
  SortRange(a, work, 0, LEN(a))
END MergeSort;

For a range of length

n > 1

, the left length is

p = ⌊ n /2 ⌋

and the right length is

q = ⌈ n /2 ⌉

, so

p \leq q \leq p + 1

as required. Both are positive and smaller than

n

, giving the recursive loop variant analogue

r - l

for algorithm termination. Empty ranges are also harmless, although the question supplies a nonempty array.

For the first merge loop, regard the two sorted ranges as fixed input sequences

B = a [l : m)

and

C = a [m : r)

. They are not overwritten during the merge. A loop invariant is that

l \leq i \leq m

m \leq j \leq r

k - l = (i - l) + (j - m)

, and work[l:k) is the stable sorted merge of the consumed prefixes a[l:i) and a[m:j). Every emitted element is at most every remaining element. Taking the smaller head preserves this property, and choosing the left head on equality preserves stable sorting. The loop variant is

(m - i) + (r - j) = r - k .

(1)

It is nonnegative and decreases by one per iteration. On exit at least one range is exhausted.

For the second loop, the remaining left range is already sorted and any right remainder is absent whenever that loop runs. Appending the next left element preserves the same merge loop invariant; its loop variant is

m - i

. For the third loop, the left range is exhausted and the right remainder is appended in order; its loop variant is

r - j

. On completing both loops, work[l:r) is the complete sorted merge and

k = r

In the final copying loop, the loop invariant is that a[l:k) equals work[l:k), work[l:r) remains the correct sorted answer, and positions outside a[l:r) are unchanged. Its loop variant is

r - k

. At exit the whole answer has been copied back. By strong induction on range length, the recursive calls sort their halves, and the merge preserves the original multiset. Thus

MergeSort returns a sorted permutation of its input .

(2)

The work array must not alias a: overwriting the source while merging would invalidate the merge loop invariant.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Discrete mathematics, probability and continuous mathematics / 2 / d / Solution 2026-10-31

 View more

First consider powers of four, with a fixed finite base value. For a mathematical induction hypothesis

x_{n /4} \leq C (n /4)^{2}

, the recurrence relation gives

x_{n} \leq 4 C (n /4)^{2} + n^{2} = (C /4 + 1) n^{2} \leq C n^{2}

(1)

provided

C \geq 4/3

and

C

also covers the base value.

The allowed integer rounding needs a little more care. Suppose the recurrence relation is applied above fixed base cases, as usual; applying

x_{1} = 4 x_{1} + 1

with a ceiling would not define a positive sequence. For either rounding write

m = ⌈ n /4 ⌉

m = ⌊ n /4 ⌋

. For

n \geq 6

m \leq \frac{n + 3}{4}, \frac{4 m ^{2}}{n ^{2}} \leq \frac{1}{4} (1 + \frac{3}{n})^{2} \leq \frac{9}{16}, m < n .

(2)

Choose

C \geq 16/7

large enough to bound all finitely many positive-index base values below

6

. By strong induction,

x_{n} = 4 x_{m} + n^{2} \leq 4 C m^{2} + n^{2} \leq (9 C /16 + 1) n^{2} \leq C n^{2} .

(3)

This argument starts at

n = 6

, so the floor convention's index zero, if used in an earlier base calculation, is absorbed into those fixed initial values. Thus, for either convention with a well-defined finite base,

x_{n} = O (n^{2}) .

(4)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Discrete mathematics, continuous mathematics and probability / 3 / e / ii / Solution 2026-10-31

 View more

Use the same integer rounding in a divide-and-conquer recurrence, now with root cost

n^{2}

. Since

1/4 \leq m / n \leq 1/2

m^{2} + (n - m)^{2} \leq \frac{5}{8} n^{2} .

(1)

Choose

C \geq max {T (1), 8/3}

and use strong induction with inductive hypothesis

T (j) \leq C j^{2}

. Both child sizes are positive and less than

n

, so

T (n) \leq C {m^{2} + (n - m)^{2}} + n^{2} \leq (\frac{5}{8} C + 1) n^{2} \leq C n^{2} .

(2)

The same factor

5/8

occurs for the exact fractional split. Therefore

T (n) = O (n^{2})

in Big O notation.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Discrete mathematics, continuous mathematics and probability / 3 / e / i / Solution 2026-10-31

 View more

The printed fractional arguments require a size convention. To make the recurrence relation precise on positive integers, take a bounded base case

T (1) = t > 0

and use

m = ⌈ n /4 ⌉

n - m

for

n \geq 2

. This integer rounding in a divide-and-conquer recurrence gives

1/4 \leq m / n \leq 1/2

. The unrounded calculation is the special split fraction

1/4

Prove

T (n) \leq A n lo g_{2} n + B n

by strong induction. Put

h_{0} = H_{2} (1/4) > 0

, choose

A \geq 1/ h_{0}

, and choose

B \geq t

. The base case follows. The entropy potential for a divide-and-conquer recurrence gives

T (n) \leq A {m lo g_{2} m + (n - m) lo g_{2} (n - m)} + B n + n = A n lo g_{2} n + B n + n {1 - A H_{2} (m / n)} \leq A n lo g_{2} n + B n .

(1)

The last step uses

H_{2} (m / n) \geq h_{0}

. This closes the inductive hypothesis and proves

T (n) = O (n lo g n)

in Big O notation.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability (resit) / 2 / c / Solution 2026-10-31

 View more

The initial values of the two sequences agree:

c_{0} = d_{0} = 1

and

c_{1} = - 1 + c_{0} = 0 = d_{1}

. For

n \geq 2

, use the first-order recurrence relation at

n

and

n - 1

c_{n} - (n - 1) (c_{n - 1} + c_{n - 2}) = (- 1)^{n} + c_{n - 1} - (n - 1) c_{n - 2} = (- 1)^{n} + (- 1)^{n - 1} = 0.

(1)

Therefore

c_{n}

satisfies exactly the same derangement recurrence as

d_{n}

. By strong induction, equality of the preceding two terms implies equality of the next term. Consequently

c_{n} = d_{n} for every n \geq 0.

(2)

The first-order recurrence relation therefore also counts derangements.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability (resit) / 3 / a / ii / Solution 2026-10-31

 View more

We prove the stronger bound

T (n) \leq 2 n^{2}

for every

n \geq 1

by strong induction. The initial case is

T (1) = 1 \leq 2

. For

n \geq 2

, put

m = ⌊ n /2 ⌋

. Then

1 \leq m < n

, so the induction hypothesis and the defining recurrence relation give

T (n) = 2 T (m) + n^{2} \leq 4 m^{2} + n^{2} \leq 4 (n /2)^{2} + n^{2} = 2 n^{2} .

(1)

Thus

T (n) \leq 2 n^{2} (n \geq 1), T (n) = O (n^{2}) .

(2)

The recurrence relation must be read as applying for

n \geq 2

; applying it at

n = 1

would invoke

T (0)

outside the printed domain. No value of

T (0)

is needed.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 2 / d / Solution 2026-10-31

 View more

Put

H_{n} = \sum_{k = 0}^{⌊ n /2 ⌋} (k n - k)

; the other summands in the printed sum vanish. The initial values are

H_{0} = 1 = F_{1}

and

H_{1} = 1 = F_{2}

. For

n \geq 2

, Pascal's identity gives

H_{n} = \sum_{k = 0}^{⌊ n /2 ⌋} (k n - 1 - k) + \sum_{k = 1}^{⌊ n /2 ⌋} (k - 1 n - 1 - k) = H_{n - 1} + H_{n - 2} .

(1)

For the first sum, when

n

is even its final term is zero; otherwise its range already agrees with

H_{n - 1}

. In the second sum put

j = k - 1

, obtaining

(j n - 2 - j)

for

0 \leq j \leq ⌊(n - 2) /2 ⌋

. Thus both range identifications hold without negative upper arguments in a binomial coefficient.

Now strong induction gives

H_{n} = F_{n} + F_{n - 1} = F_{n + 1}

from the two preceding cases and the Fibonacci recurrence. Hence

k = 0 \sum n (k n - k) = F_{n + 1} (n \geq 0) .

(2)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Discrete mathematics, continuous mathematics and probability / 3 / d / Solution 2026-10-31

 View more

A stronger exact formula makes the induction explicit:

S_{n} = 1 + m (1 + ⌊ lo g_{2} n ⌋), n \geq 1.

(1)

For

n = 1

, the recurrence gives

S_{1} = S_{0} + m = 1 + m

. For

n \geq 2

, set

j = ⌊ n /2 ⌋

, so

1 \leq j < n

. In the relevant binary interval,

⌊ lo g_{2} j ⌋ = ⌊ lo g_{2} n ⌋ - 1

. The strong induction hypothesis gives

S_{n} = S_{j} + m = 1 + m (1 + ⌊ lo g_{2} j ⌋) + m = 1 + m (1 + ⌊ lo g_{2} n ⌋) .

(2)

For

n \geq 2

S_{n} \leq 1 + m + m lo g_{2} n \leq (1 + 2 m) lo g_{2} n

. Hence

S_{n} = O (lo g_{2} n)

. This is an integer-halving recurrence with constant toll; the separately defined

n = 0

case does not require evaluating

lo g 0

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 5 / a / Solution 2026-10-25

 View more

For the first recurrence relation, the master theorem compares

n^{2}

with

n^{l o g_{2} 6}

. Since

2 < lo g_{2} 6

, the recursive leaves dominate and the answer is $Θ (n^{l o g_{2} 6})$ . More explicitly, the work at depth

j

n^{2} (6/4)^{j}

, a growing geometric series that stops at depth

lo g_{2} n - O (1)

, where its sum has that order.

For the second recurrence relation, each step subtracts two and adds one until reaching a base case. For integral

n > 4

there are

⌈(n - 4) /2 ⌉

steps, so

T (n) = 1 + ⌈(n - 4) /2 ⌉

and the answer is $Θ (n)$ .

The third set of printed requirements is inconsistent. The specified base values and its recurrence relation give

T (n) = 1

identically, as strong induction immediately verifies:

4 \cdot 1 - 4 \cdot 1 + 1 = 1

. In particular

T (8) = 1

, while the extra condition demands

T (8) > 2 T (4) = 2

. Thus no function satisfies all the printed conditions. Dropping that extra inequality gives $Θ (1)$ .

The likely intended growth calculation can nevertheless be made precise, without treating it as a solution of the contradictory data. On dyadic arguments put

U_{j} = T (2^{j})

. Its equation has the general form

U_{j} = 1 + (A + B j) 2^{j},

(1)

because

U_{j} - 1

has characteristic equation

(r - 2)^{2} = 0

. The printed values

U_{1} = U_{2} = 1

force

A = B = 0

. With suitably different initial values, the condition

U_{j} > 2 U_{j - 1}

for arbitrarily large

j

instead requires

B 2^{j} - 1 > 0

, hence

B > 0

and

U_{j} = Θ (j 2^{j})

, or

T (n) = Θ (n lo g n)

. That last order describes corrected initial data, not the paper as printed. All three bullets belong to this single marked part.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Discrete mathematics, probability and continuous mathematics / 2 / a / Solution 2026-10-25

 View more

Use strong induction with three consecutive base cases:

8 = 3 + 5, 9 = 3 \cdot 3, 10 = 5 \cdot 2.

(1)

For

n \geq 11

, assume all values from

8

through

n - 1

have the required representation. Since

8 \leq n - 3 < n

, write

n - 3 = 3 k + 5 m

with

k, m

nonnegative integers. Then

n = 3 (k + 1) + 5 m

is another such representation. Strong induction proves the claim for every

n \geq 8

. This is a consecutive-base induction for additive semigroups: the three base cases handle all residues before repeated addition of

3

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Discrete mathematics, probability and continuous mathematics / 3 / b / i / Solution 2026-10-25

 View more

Use strong induction on the positive integer

n

. The case

n = 1

is represented by the empty product. For

n > 1

, if

n

is prime it is already a product of one prime. Otherwise

n = ab

with

1 < a, b < n

; the induction hypothesis gives prime factorizations for both

a

and

b

, and concatenating them gives one for

n

. This proves existence in the fundamental theorem of arithmetic without presupposing uniqueness.

 Read the full article

Strong induction Created 2026-09-24 Updated 2026-10-18

 View more

Strong induction establishes a proposition

P (n)

for all integers

n \geq n_{0}

. Prove

P (n_{0})

; then, for each

n \geq n_{0}

, assume every

P (k)

with

n_{0} \leq k \leq n

and prove

P (n + 1)

. The induction hypothesis includes all earlier cases, so the inductive step can use whichever smaller indices it needs. It cannot use

P (n + 1)

itself.^[ref]

This is useful when a construction breaks into smaller pieces of varying sizes. A prime factorization splits a composite number into smaller integer divisors, which need not be one less than the original integer. A recursive procedure can likewise call itself on several smaller inputs. The available cases should match those dependencies. Strong induction lets the mathematical proof follow the construction rather than forcing every step through the immediately preceding size.

 Read the full article

Strong induction and accumulated hypotheses 2026-10-18

 View more

Strong induction does not prove more than ordinary mathematical induction. Put

Q (n) = ⋀_{k = n_{0}}^{n} P (k)

. Ordinary mathematical induction on

Q

retains the earlier cases and obtains the next one, establishing the same conclusion. Conversely, an ordinary inductive step can ignore the extra cases allowed in a strong induction hypothesis.^[ref]

The well-ordering principle gives another view. A least counterexample would have all smaller cases true, so the strong induction step would establish that allegedly false case. The starting case excludes the beginning.

 Read the full article

Strong induction for factorization existence 2026-10-18

 View more

Every integer

n \geq 2

has a prime factorization. The induction base case

2

is prime. For a larger integer, either it is prime or it is

ab

, with

2 \leq a, b < n

. The induction hypothesis supplies prime factorizations of both smaller integer divisors; multiplying them gives one for

n

. This proves existence, while uniqueness requires the additional argument under the fundamental theorem of arithmetic.^[ref]

For the chosen number

84

, one possible recursive decomposition is

84 = 6 \cdot 14 = (2 \cdot 3) (2 \cdot 7) = 2^{2} \cdot 3 \cdot 7.

(1)

The step at

84

needs results for

6

and

14

, rather than a result for

83

. Each composite number in this factorization tree splits into strictly smaller positive integers, so recursive descent terminates at prime numbers. The tree describes one construction; another choice of integer divisors can give a differently shaped factorization tree.

Figure 1.
The step for 84 can use 6 and 14: the induction hypothesis covers both
. Original factorization tree $84 \to 6 \cdot 14$ , followed by $6 \to 2 \cdot 3$ and $14 \to 2 \cdot 7$ . Arrows show recursive dependencies toward smaller integers, rather than the order of increasing induction. The strip at the bottom marks the earlier cases available at the step for $84$ , with the required $6$ and $14$ highlighted. No use of the unproved case $84$ is permitted in the hypothesis. **Details**.

The same pattern explains the usefulness of strong induction for algorithm correctness. When a recursive procedure returns answers for smaller inputs, the induction hypothesis can justify those answers; the remaining task is to justify how the current call combines them. Strictly decreasing a nonnegative integer size measure establishes termination. Correctness also requires each call's conditions and its combination rule; termination alone does not make an algorithm correct.

 Read the full article

Strong induction with four starting cases 2026-10-18

 View more

Consider a chosen packing problem: batches contain either four or seven identical items, with any nonnegative number of batches allowed. Which integer totals can be formed? The claim is that every total of at least eighteen is attainable:

\forall n \geq 18, \exists a, b \in N : n = 4 a + 7 b .

(1)

Here

a, b

count batches, so they must be nonnegative integers; the convention

N = {0, 1, 2, \dots}

permits omitting either size. Four direct starting cases are

18 = 4 + 7 + 7, 19 = 4 + 4 + 4 + 7, 20 = 4 + 4 + 4 + 4 + 4, 21 = 7 + 7 + 7.

(2)

n \geq 21

and every total from

18

through

n

is attainable, then

n - 3 \geq 18

is one of the cases available in the induction hypothesis. Add a batch of four to its representation to obtain

n + 1

. Thus the inductive step applies to every new total from

22

onward. Formally, one can start the strong induction at

18

and handle the next three totals directly before using the uniform step. The finite checks and the propagation together establish all totals, not merely those drawn below.

Figure 1.
Four starting cases seed every residue class when the step adds four
. Original chosen batch sizes $4$ and $7$ . Colored rows follow $18, 22, 26, \dots$ ; $19, 23, 27, \dots$ ; $20, 24, 28, \dots$ ; and $21, 25, 29, \dots$ . Each arrow adds a batch of four. The lower strip exhaustively checks totals through $29$ ; a cross means no representation by nonnegative batch counts. The infinite conclusion comes from the inductive step, not from this finite enumeration. **Details**.

Checking only

18

and repeatedly adding four would reach only totals congruent to

18

in modular arithmetic modulo four. The four induction base cases supply all four residue classes. The number of starting cases comes from this chosen construction, not from a universal requirement that strong induction needs several bases. A different construction can need different starting information.

The threshold is sharp for these batch sizes. If

17 = 4 a + 7 b

, reducing modulo four gives

3 b \equiv 1 (mod 4)

, so

b \equiv 3 (mod 4)

. A nonnegative

b

would therefore be at least three, giving

7 b \geq 21 > 17

, a contradiction. A finite failed search alone would need an explicit bound on

a, b

; this short modular arithmetic argument supplies a general obstruction.

 Read the full article