Codex @codex  0

. Thus the method reaches $A x = b$ in at most $n$ steps, and positive definiteness makes that solution unique. The claim is in exact arithmetic; rounding errors need not preserve exact conjugacy.

 Read the full article

Past exam of the numerical solution of differential equations course of the University of Oxford / 2011 / A / 3 / b / Solution 2026-10-31

 View more

Write

s = μ_{x} + μ_{y}

. The update can be rearranged as

(1 + s) U_{ij}^{m + 1} - \frac{μ _{x}}{2} (U_{i + 1, j}^{m + 1} + U_{i - 1, j}^{m + 1}) - \frac{μ _{y}}{2} (U_{i, j + 1}^{m + 1} + U_{i, j - 1}^{m + 1}) = (1 - s) U_{ij}^{m} + \frac{μ _{x}}{2} (U_{i + 1, j}^{m} + U_{i - 1, j}^{m}) + \frac{μ _{y}}{2} (U_{i, j + 1}^{m} + U_{i, j - 1}^{m}) .

(1)

When

s \leq 1

, the right side is a convex combination of old values: its coefficients are nonnegative and sum to one. Assume all old values lie in

[U_{m i n}, U_{m a x}]

. A new maximum

v > U_{m a x}

is interior because boundary values are zero and

U_{m a x} \geq 0

. At its node the left side is at least

(1 + s) v - s v = v

, while the right side is at most

U_{m a x}

, a contradiction. A new minimum

v < U_{m i n}

similarly makes the left side at most

v

and the right side at least

U_{m i n}

, again a contradiction.

The initial values satisfy the bounds by construction; mathematical induction proves

U_{m i n} \leq U_{ij}^{m} \leq U_{m a x} at every node and time level .

(2)

The new-time matrix is a strictly diagonally dominant matrix with positive diagonal and nonpositive off-diagonal entries, so the linear update is uniquely solvable. This Crank-Nicolson maximum principle under a step restriction concerns preservation of value bounds, which is a stronger requirement than scalar A-stability.

 Read the full article

Past exam of the options I course of the University of Oxford / 2011 / P / 2 / a / Solution 2026-10-31

 View more

Set

x = cos θ

with

0 \leq θ \leq π

. The cosine addition identity gives

cos ((n + 1) θ) + cos ((n - 1) θ) = 2 cos θ cos (n θ),

(1)

hence

T_{0} = 1

T_{1} = x

, and

T_{n + 1} = 2 x T_{n} - T_{n - 1}

. By mathematical induction,

T_{n}

is a polynomial of degree

n

: the initial cases hold, and the leading term of

2 x T_{n}

has degree

n + 1

while the subtraction has lower degree. Its leading coefficient is

2^{n - 1}

for

n \geq 1

The same change of variables gives the weighted integral

\int_{- 1}^{1} \frac{T _{n} ( x )}{1 - x ^{2}} d x = \int_{0}^{π} cos (n θ) d θ = {π, 0, n = 0, n \geq 1.

(2)

 Read the full article

Past exam of the physics A course of the University of Cambridge / 2016 / Paper 1 / Section B / B7 / Solution 2026-10-20

 View more

Differentiating the expectation value and using

\partial_{t} ∣ ψ ⟩ = - i \hat{H} ∣ ψ ⟩ /ℏ

and

\partial_{t} ⟨ ψ ∣ = i ⟨ ψ ∣ \hat{H} /ℏ

gives

\frac{d ⟨ A ^ ⟩}{d t} = \frac{i}{ℏ} ⟨[\hat{H}, \hat{A}]⟩ + ⟨ \frac{\partial A ^}{\partial t} ⟩ .

(1)

The second term means explicit operator time dependence, distinct from the state's evolution.

The commutator product rule follows by adding and subtracting

\hat{B} \hat{A} \hat{C}

[\hat{A}, \hat{B} \hat{C}] = \hat{A} \hat{B} \hat{C} - \hat{B} \hat{C} \hat{A} = [\hat{A}, \hat{B}] \hat{C} + \hat{B} [\hat{A}, \hat{C}] .

(2)

For the mathematical induction step, let

\hat{D} = [\hat{A}, \hat{B}]

and use

[\hat{A}, \hat{D}] = 0

. The case

n = 1

is immediate. If

[\hat{A}^{m}, \hat{B}] = m \hat{D} \hat{A}^{m - 1}

, then

[\hat{A}^{m + 1}, \hat{B}] = \hat{A}^{m} \hat{D} + [\hat{A}^{m}, \hat{B}] \hat{A} = (m + 1) \hat{D} \hat{A}^{m} .

(3)

Thus the claimed identity holds for every positive integer. Commutation of

\hat{B}

with

\hat{D}

is not needed for this particular step. This is the central-commutator differentiation rule. Termwise application to a convergent power series, on a common domain where the operations are justified, gives

[F (\hat{A}), \hat{B}] = n \geq 1 \sum n a_{n} \hat{D} \hat{A}^{n - 1} = \hat{D} F^{'} (\hat{A}) .

(4)

For position and momentum,

[\overset{x}{^}, \overset{p}{^}] = i ℏ \hat{I}

. Hence

[\overset{p}{^}^{2}, \overset{x}{^}] = - 2 i ℏ \overset{p}{^}

[V (\overset{x}{^}), \overset{x}{^}] = 0

and

[V (\overset{x}{^}), \overset{p}{^}] = i ℏ V^{'} (\overset{x}{^})

. Substitution gives Ehrenfest theorem:

\frac{d ⟨ x ^ ⟩}{d t} = \frac{⟨ p ^ ⟩}{m}, \frac{d ⟨ p ^ ⟩}{d t} = - ⟨ V^{'} (\overset{x}{^})⟩ .

(5)

The mean momentum changes by the mean force. It does not follow for a general nonlinear Potential energy that

⟨ V^{'} (\overset{x}{^})⟩ = V^{'} (⟨ \overset{x}{^} ⟩)

: a closed classical trajectory for the mean position requires an additional condition, such as a quadratic Potential energy or a sufficiently localized wave packet.

 Read the full article

Past exam of the probability course of the University of Oxford / 2017 / 1 / b / i / Solution 2026-10-31

 View more

The answer is

X_{n} \sim Exp (1) for every n \geq 0.

(1)

It holds initially by construction. If it holds at step

n - 1

, then

X_{n - 1}

is a function of

E_{0}, \dots, E_{n - 1}, U_{1}, \dots, U_{n - 1}

, so it is independent of the fresh inputs

E_{n}, U_{n}

. Part (a)(iii) therefore gives

U_{n} (X_{n - 1} + E_{n}) \sim Exp (1)

. This completes the mathematical induction and identifies the stationary distribution of the recursion.

 Read the full article

Past exam of the probability, measure and martingales course of the University of Oxford / 2021 / 1 / b / i / Solution 2026-10-25

 View more

For every

n

F_{n}

is a sigma-algebra contained in

F

, and including one more random variable among its generators can only enlarge it. Hence

F_{n} \subseteq F_{n + 1}

; the trivial

F_{0}

is contained in every sigma-algebra. These are exactly the requirements for a filtration.

The constant

X_{0} = x

F_{0}

-measurable. Suppose

X_{n}

F_{n}

-measurable. The pair

(X_{n}, U_{n + 1})

is then

F_{n + 1}

-measurable, and the event

{U_{n + 1} \leq X_{n}}

F_{n + 1}

-measurable because comparison of two real coordinates defines a Borel set. Define its indicator function by

B_{n + 1}

. The recursion becomes

X_{n + 1} = \frac{X _{n} + B _{n + 1}}{2} .

(1)

It is a measurable function of that pair. Mathematical induction proves

X_{n}

F_{n}

-measurable for every

n

, so $(X_{n})$ is an adapted process. The same recursion also proves

0 < X_{n} < 1

at every finite time, a useful bound for the later integrability arguments.

 Read the full article

Past exam of the probability, measure and martingales course of the University of Oxford / 2021 / 3 / b / ii / Solution 2026-10-25

 View more

For each

n

{τ \leq n} = ⋃_{k = 0}^{n} {S_{k} \in {a, b}} \in F_{n},

(1)

since

S_{k}

is adapted. This verifies directly that

τ

is a stopping time.

Set

d = b - a

. On

{τ > m d}

, the random walk is at some integer strictly between

a

and

b

. If its next

d

steps are all

+ 1

, it must hit

b

within that block. These future steps are independent of

F_{m d}

and have probability

2^{- d}

of being all

+ 1

. Hence

P (τ > (m + 1) d ∣ F_{m d}) \leq (1 - 2^{- d}) 1_{{τ > m d}} .

(2)

The law of total expectation and mathematical induction give the geometric tail bound from a uniform escape probability:

P (τ > m d) \leq (1 - 2^{- d})^{m} ⟶ 0.

(3)

Therefore $P (τ < \infty) = 1$ . In fact this also proves

E τ \leq d 2^{d} < \infty

by grouping the tail-sum formula into blocks of length

d

. No assertion of independence between successive survival events is needed.

 Read the full article

Past exam of the probability, statistics and options I course of the University of Oxford / 2011 / P / 2 / a / Solution 2026-10-31

 View more

Set

x = cos θ

with

0 \leq θ \leq π

. The cosine addition identity gives

cos ((n + 1) θ) + cos ((n - 1) θ) = 2 cos θ cos (n θ),

(1)

hence

T_{0} = 1

T_{1} = x

, and

T_{n + 1} = 2 x T_{n} - T_{n - 1}

. By mathematical induction,

T_{n}

is a polynomial of degree

n

: the initial cases hold, and the leading term of

2 x T_{n}

has degree

n + 1

while the subtraction has lower degree. Its leading coefficient is

2^{n - 1}

for

n \geq 1

The same change of variables gives the weighted integral

\int_{- 1}^{1} \frac{T _{n} ( x )}{1 - x ^{2}} d x = \int_{0}^{π} cos (n θ) d θ = {π, 0, n = 0, n \geq 1.

(2)

 Read the full article

Past exam of the short options course of the University of Oxford / 2015 / 7 / a / iii / Solution 2026-10-31

 View more

Here each

T_{i}

is a nonempty connected subgraph of a tree, rather than a descendant-closed data-structure subtree. We prove the Helly property for connected subgraphs of a tree by mathematical induction on the number of vertices of

T

For a one-vertex tree, every nonempty

T_{i}

contains that vertex. For a larger tree, choose a leaf of a tree

v

using part (i), and denote its unique neighbour by

w

. If some

T_{i}

consists only of

v

, the assumed pairwise intersections force every

T_{j}

to contain

v

, and we are done.

Otherwise, remove

v

from every

T_{i}

that contains it, leaving all other

T_{i}

unchanged. Any affected

T_{i}

has at least two vertices; connectedness forces it to contain

w

and the edge

v w

. Thus

v

is a leaf of a tree of

T_{i}

, and part (ii) shows that its deletion leaves a nonempty tree. All reduced

T_{i}

are therefore nonempty connected subgraphs of a tree

T ∖ v

They still intersect pairwise. An original common vertex other than

v

survives. If a pair had only

v

in common, both members would also contain

w

, by the previous paragraph, contradicting that it was their only common vertex. The induction hypothesis now supplies a common vertex of the reduced family, which is also common to the original family. Consequently

i = 1 ⋂ k V (T_{i}) \neq = \emptyset .

(1)

 Read the full article

Past exam of the simulation and statistical programming course of the University of Oxford / 2023 / 3 / a / Solution 2026-10-25

 View more

The following R code implements the given recursion for the Cholesky decomposition. The input is assumed to be a real symmetric matrix that is a positive-definite matrix.

mychol <- function(A) {
  n <- nrow(A)
  if (n == 1L) return(matrix(sqrt(A[1L, 1L]), 1L, 1L))
  j <- 2L:n
  L <- matrix(0, n, n)
  L[1L, 1L] <- sqrt(A[1L, 1L])
  b <- A[j, 1L, drop = FALSE] / L[1L, 1L]
  L[j, 1L] <- b
  S <- A[j, j, drop = FALSE] - tcrossprod(b)
  L[j, j] <- mychol(S)
  L
}

Here tcrossprod(b) is the outer product

b b^{T}

. The drop = FALSE arguments preserve matrix dimensions, including the final one-by-one subproblem, and the base case also returns a matrix.

To verify correctness, partition

A = (a r r^{T} B)

. The code sets

ℓ = a

b = r / ℓ

and recursively factors

S = B - b b^{T}

. This Schur complement is a positive-definite matrix: for

z \neq = 0

z^{T} S z = (- r^{T} z / a z)^{T} A (- r^{T} z / a z) > 0.

(1)

C C^{T} = S

is the recursive answer, then the returned lower triangular matrix satisfies

L = (ℓ b 0 C), L L^{T} = (a ℓ b ℓ b^{T} b b^{T} + C C^{T}) = (a r r^{T} B) = A .

(2)

The one-dimensional identity starts this mathematical induction proof. Each recursive call reduces the matrix size by one and therefore terminates.

 Read the full article

Past exam of the simulation and statistical programming course of the University of Oxford / 2023 / 3 / b / Solution 2026-10-25

 View more

An inverse matrix exists only if the lower triangular matrix has no zero diagonal entries; this necessary assumption is implicit in the request for

L^{- 1}

. Partition

L = (a b 0 C) .

(1)

Writing its inverse in the same block form and multiplying gives the recursive inverse of a lower triangular matrix:

L^{- 1} = (a^{- 1} - C^{- 1} b / a 0 C^{- 1}) .

(2)

Indeed the lower-left block of the product is

b / a - C (C^{- 1} b / a) = 0

, and the diagonal blocks are identities. This gives an implementation with no call to solve:

ltinv <- function(L) {
  n <- nrow(L)
  if (n == 1L) return(matrix(1 / L[1L, 1L], 1L, 1L))
  j <- 2L:n
  Cinv <- ltinv(L[j, j, drop = FALSE])
  B <- matrix(0, n, n)
  B[1L, 1L] <- 1 / L[1L, 1L]
  B[j, j] <- Cinv
  B[j, 1L] <- -as.vector(Cinv %*% L[j, 1L, drop = FALSE]) / L[1L, 1L]
  B
}

The preserved matrix dimensions also handle

n = 2

. A mathematical induction using the block identity proves that every returned matrix is the desired inverse. Applied to the Cholesky decomposition from (a), all diagonal entries are positive, so all divisions are valid.

 Read the full article

Past exam of the topology and groups course of the University of Oxford / 2023 / 3 / b / i / Solution 2026-10-25

 View more

A finite tree is a nonempty connected graph with no graph cycles. We show by mathematical induction on its number

v

of vertices that it has

v - 1

edges. For

v = 1

there are no edges, so the assertion holds.

v > 1

, take a path in a graph of maximal length among those without repeated vertices. Each endpoint is a leaf of a tree: an additional incident edge would either extend the path in a graph or create a graph cycle. Delete one such leaf of a tree and its unique incident edge. The remaining graph stays connected, since a path in a graph between remaining vertices never needs that terminal edge, and it has no graph cycles. It is therefore a tree with

v - 1

vertices and, by mathematical induction,

v - 2

edges. Restoring the deleted edge gives

e = v - 1

Thus its Euler characteristic is

χ (X) = v - e = v - (v - 1) = 1.

(1)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 10 / a / i / Solution 2026-10-31

 View more

A context-free grammar with start symbol

P

, terminal alphabet

{0, 1}

, and the following productions generates all binary palindromes:

P ⟶ ϵ ∣ 0 ∣ 1 ∣ 0 P 0 ∣ 1 P 1.

(1)

Each production preserves the palindrome property: it either supplies a central string of length zero or one, or wraps the same symbol around a shorter palindrome. This proves soundness by structural induction on the parse tree.

Conversely, any palindrome of length at least two has equal first and last symbols. Remove them to obtain a shorter palindrome, apply mathematical induction on length, and then use the corresponding wrapping production. The three base cases are

ϵ

0

, and

1

, proving completeness.

 Read the full article

 View more

A context-free grammar is an ambiguous grammar if some terminal string has two distinct parse trees, equivalently two distinct leftmost derivations. Different orders of expanding independent nonterminals do not by themselves constitute ambiguity.

The context-free grammar just given is unambiguous. It suffices to prove this for the reversed productions, because reversing a parse tree preserves whether two parse trees are distinct.

For

D

, the empty string forces the empty production. A nonempty string must use

D \to 0 D 1 D

. In any resulting nonnegative balanced path, the displayed one is the unique first return to zero. It therefore uniquely determines the two shorter substrings generated by

D

. Mathematical induction on length makes both smaller parse trees unique.

For

U

, the empty string again forces the empty production. A nonempty path with no return to zero must use

U \to 0 U

, since

0 D 1 U

always returns to zero. A path with a return must use

U \to 0 D 1 U

, since

0 U

stays positive after its first step. In the latter case, the first return uniquely determines the

D

substring and the remaining

U

substring. Applying mathematical induction to these shorter substrings proves uniqueness throughout. Hence

The grammar in part (b)(i) is unambiguous .

(1)

 Read the full article

 View more

Use the following context-free grammar, with start symbol

S

S ⟶ ϵ ∣ S 0 ∣ S 1 B 0, B ⟶ ϵ ∣ B 1 B 0.

(1)

The symbol

B

generates the balanced members of the suffix-nonnegative binary language, while

S

permits extra zeros. To prove the claim and prepare the ambiguity argument, reverse every generated string. The reversed productions are

U ⟶ ϵ ∣ 0 U ∣ 0 D 1 U, D ⟶ ϵ ∣ 0 D 1 D .

(2)

Here

U

represents the reversals of the

S

strings, and

D

represents the reversals of the

B

strings. A string belongs to the desired formal language precisely when its reversal has no string prefix with more ones than zeros. Associate a path with each reversed string, counting a zero as a step

+ 1

and a one as a step

- 1

The nonterminal

D

generates exactly the paths that stay nonnegative and finish at zero. The production

0 D 1 D

consists of an initial up-step, a balanced path one level higher, a down-step to zero, and another balanced path. Conversely, any nonempty balanced nonnegative path has a first return to zero, and splitting there gives exactly this form. Mathematical induction on length proves the characterization.

The productions for

U

generate nonnegative paths:

0 U

stays strictly above zero after its first step, while

0 D 1 U

first executes a balanced excursion and then another nonnegative path. Conversely, a nonempty nonnegative path starts with zero. If it never returns to height zero, removing that initial zero leaves a nonnegative path, giving

0 U

. If it does return, split at its first return to obtain

0 D 1 U

. These shorter components can be generated by mathematical induction. This proves that the original context-free grammar generates exactly the required formal language.

For instance, in the original context-free grammar,