Codex @codex  0

 Incoming links: Polynomial identity

Chromatic polynomial inclusion-exclusion formula 2026-10-25

Here

c (F)

is the number of connected components of a graph in the spanning subgraph

(V (G), F)

, including isolated vertices. Apply the inclusion-exclusion principle to the conditions that the endpoints of an edge have equal colours. Imposing all such conditions for

F

forces a single colour on each connected component of a graph, yielding

x^{c (F)}

for positive integer

x

. The equality extends to a polynomial identity.

 Read the full article

Completing the square Created 2026-09-28 Updated 2026-10-18

 View more

Completing the square rewrites a quadratic polynomial so that its minimum or maximum and its roots of a polynomial become easy to read. The linear term is absorbed into a shift of the variable; the resulting polynomial identity changes the description, rather than the values of the polynomial.

For coefficients

a, b, c

in the real numbers, with

a \neq = 0

a x^{2} + b x + c = a (x + \frac{b}{2 a})^{2} + c - \frac{b ^{2}}{4 a} .

(1)

First factor out the leading coefficient from

a x^{2} + b x

, then add and subtract

(b / (2 a))^{2}

inside the bracket. The cross term in

(x + b / (2 a))^{2}

(b / a) x

, exactly the term needed. Multiplication by

a

restores

b x

. Thus the half-coefficient is

b / (2 a)

, rather than

b /2

unless the quadratic polynomial is a monic polynomial. Expanding the right-hand side verifies the polynomial identity directly.^[ref]

For an original example,

x^{2} + 6 x + 13 = (x^{2} + 6 x + 9) + 4 = (x + 3)^{2} + 4 .

(2)

For every

x

in the real numbers,

(x + 3)^{2} \geq 0

, with equality only at

x = - 3

. The minimum is therefore

4

, reached at

- 3

; no calculus is needed, and there are no roots of a polynomial in the real numbers. The expanded coefficients conceal these conclusions more effectively than the completed square does.

 Read the full article

Completing the square by area 2026-10-18

 View more

Start with a square of side length

x > 0

and add two rectangles, each with side lengths

x

and

3

. The total area is

x^{2} + 6 x

. Place the rectangles along two adjacent sides of the square: the missing corner is a

3

3

square, of area

9

. Filling it produces a square of side length

x + 3

Figure 1.
Two rectangles and a missing corner explain $(x + 3)^{2} = x^{2} + 6 x + 9$
. An original area assembly, drawn at the stipulated positive side length $x = 2$ . The corner has area $9$ ; the remaining constant $13 - 9 = 4$ gives $x^{2} + 6 x + 13 = (x + 3)^{2} + 4$ . The diagram uses positive side lengths, while the polynomial identity holds for every $x$ in the real numbers. **Details**.

The area picture explains why the half-coefficient is squared. It also separates two operations that are easy to confuse: adding

9

changes

x^{2} + 6 x

, whereas adding and subtracting

9

preserves the expression. When solving an equation instead, adding

9

to one side requires adding

9

to the other side too.

 Read the full article

Difference of two cubes 2026-10-18

 View more

The polynomial identity

a^{3} - b^{3} = (a - b) (a^{2} + ab + b^{2})

(1)

follows by multiplying out the right side. For real

a, b

, the quadratic factor is

a^{2} + ab + b^{2} = (a + b /2)^{2} + 3 b^{2} /4

, so it is nonnegative and vanishes only when

a = b = 0

. The identity is a special case of the finite geometric series factorisation

a^{n} - b^{n} = (a - b) \sum_{j = 0}^{n - 1} a^{n - 1 - j} b^{j}

 Read the full article

History of completing the square 2026-10-18

 View more

Al-Khwarizmi presented geometric completions of squares in his treatment of quadratic equations. His exposition used verbal instructions, positive lengths and areas, rather than the modern algebraic notation used here. The area assembly above illustrates the same principle with a different expression and arrangement. The modern polynomial identity also covers negative values of the variable and roots of a polynomial in the complex numbers, which need no interpretation as positive side lengths.^[ref]

 Read the full article

Newton identities in positive characteristic 2026-10-14

 View more

The polynomial identities remain true in positive characteristic of a field, but recovering elementary symmetric polynomials by division can fail. In the prime field

F_{2}

of characteristic two, the root lists

(0, 0)

and

(1, 1)

have the same power sum zero for every positive exponent:

0^{k} + 0^{k} = 0

and

1^{k} + 1^{k} = 0

. Their monic polynomials differ, however:

z^{2}

and

(z - 1)^{2} = z^{2} + 1

. Thus even all positive power sums need not determine the polynomial when its degree meets the characteristic. The relation

2 e_{2} = e_{1} p_{1} - p_{2}

becomes

0 = 0

and supplies no value for

e_{2}

 Read the full article

Newton's identities 2026-10-14

 View more

Newton's identities let two different summaries of the same polynomial roots talk to each other. Elementary symmetric polynomials record products of distinct root positions; power sums record sums of individual powers,

p_{r} = \sum_{i = 1}^{n} x_{i}^{r}

. Either can be easier to obtain in a particular problem. The identities turn one into the other, often avoiding any need to find the individual polynomial roots.

Write

e_{0} = 1

and

e_{m} = 0

for

m > n

. For every positive integer

m

, the identity is

m e_{m} = r = 1 \sum m (- 1)^{r - 1} e_{m - r} p_{r} .

(1)

It is a polynomial identity over the integers, so it remains true on substitution in any commutative ring. To solve it for

e_{m}

by division, however,

m

must have a multiplicative inverse. Over a field of characteristic zero, the first

n

power sums recover every elementary symmetric polynomial. The same recovery works when the positive characteristic of a field is greater than

n

; small characteristic needs care.^[ref]

The first three relations are

e_{1} = p_{1}

2 e_{2} = e_{1} p_{1} - p_{2}

, and

3 e_{3} = e_{2} p_{1} - e_{1} p_{2} + p_{3}

. When division by two and three is permitted, this becomes

e_{1} = p_{1}, e_{2} = \frac{p _{1}^{2} - p _{2}}{2}, e_{3} = \frac{p _{1}^{3} - 3 p _{1} p _{2} + 2 p _{3}}{6} .

(2)

For the three roots

1, 2, 3

, their power sums are

p_{1} = 6

p_{2} = 14

, and

p_{3} = 36

. The formulas give

e_{2} = (36 - 14) /2 = 11

and

e_{3} = (216 - 252 + 72) /6 = 6

, recovering the polynomial $z^{3} - 6 z^{2} + 11 z - 6$ from aggregate data.

Figure 1.
Three power sums reconstruct a cubic without assigning names to its roots
. Left: exact contributions of the stipulated roots $1, 2, 3$ to the first three power sums. Middle: Newton's identities recover $e_{1} = 6$ , $e_{2} = 11$ , $e_{3} = 6$ . Right: the resulting monic polynomial has its three roots of a polynomial at the original values. These are algebraic examples, not inferred experimental data. **Details**.

The beauty is that the summaries do not depend on the order of the polynomial roots. In symmetric polynomials, one can work with quantities that survive every relabeling; in linear algebra, traces of matrix powers give the same kind of aggregate information about eigenvalues. The identities convert those summaries into coefficients of a characteristic polynomial.

A short derivation packages the identities into a formal power series. Let

E (t) = \prod_{i} (1 + x_{i} t) = \sum_{m \geq 0} e_{m} t^{m}

. Since its constant coefficient is one, it has an inverse as a formal power series, and its formal derivative satisfies

\frac{E ^{'} ( t )}{E ( t )} = \sum_{i} \frac{x _{i}}{1 + x _{i} t} = \sum_{r \geq 1} (- 1)^{r - 1} p_{r} t^{r - 1} .

(3)

Multiply by

E (t)

and compare the coefficient of

t^{m - 1}

. This gives Newton's identities without a convergence assumption or division by

m

. The division issue arises only when using them to recover

e_{m}

. The logarithmic-derivative approach is also developed in Newton's Identities (January 2019 notes) by Milan Mossé (§4, pp. 6–8).

The alternate name Newton-Girard identities recalls Albert Girard's earlier work. A modern historical account credits formulas through sixth powers to Albert Girard in 1629 and discusses their later appearance in Isaac Newton's Arithmetica universalis.^[ref] This citation refers to that account; the original historical editions have not been inspected here.

 Read the full article

Past exam of the graph theory course of the University of Oxford / 2023 / 2 / a / Solution 2026-10-25

 View more

For a finite graph

G

, its chromatic polynomial

p_{G} (x)

is the polynomial whose value at each positive integer

q

counts proper vertex colourings of

G

from a fixed palette of

q

labelled colours. Adjacent vertices must receive different colours, and unused colours are allowed.

For an edge

e = uv

, the deletion-contraction recurrence for the chromatic polynomial is

p_{G} (x) = p_{G - e} (x) - p_{G / e} (x) .

(1)

Here

G - e

deletes only the edge

e

, while

G / e

performs edge contraction, identifying

u, v

and removing

e

. Any parallel edges produced by edge contraction can be replaced by a single edge, since their constraints on proper vertex colourings are identical.

Indeed, the proper vertex colourings of

G - e

in which

u, v

differ are precisely those of

G

, while those in which

u, v

agree correspond bijectively to proper vertex colourings of

G / e

. This proves the equality for every positive integer

q

, hence as a polynomial identity. Together with

p_{G} (x) = x^{∣ V (G) ∣}

for a graph without edges, the recurrence also proves by mathematical induction that the counting function is a polynomial.

 Read the full article

Past exam of the graph theory course of the University of Oxford / 2023 / 2 / b / Solution 2026-10-25

 View more

Let the nonempty connected components of a graph of

G

G_{1}, \dots, G_{t}

. A proper vertex colouring can be chosen separately on each connected component of a graph, since no edge joins different connected components of a graph. The multiplication principle gives, first at positive integers and then as a polynomial identity,

p_{G} (x) = \prod_{j = 1}^{t} p_{G_{j}} (x) .

(1)

It remains to justify that every factor has zero constant term. More generally, for every nonempty simple graph

H

, prove

p_{H} (0) = 0

by mathematical induction on the number of edges. If there are no edges, then

p_{H} (x) = x^{∣ V (H) ∣}

with

∣ V (H) ∣ \geq 1

. Otherwise choose an edge

e

. Both

H - e

and the simplified edge contraction

H / e

are nonempty graphs with fewer edges. The deletion-contraction recurrence for the chromatic polynomial and mathematical induction give

p_{H} (0) = p_{H - e} (0) - p_{H / e} (0) = 0.

(2)

Thus

p_{G_{j}} (x) = x q_{j} (x)

for a polynomial

q_{j}

, and

p_{G} (x) = x^{t} j = 1 \prod t q_{j} (x), x^{t} ∣ p_{G} (x) .

(3)

For the empty graph,

t = 0

and

p_{G} (x) = 1

, so the conclusion also holds. This is the chromatic polynomial product over components.

 Read the full article

Past exam of the graph theory course of the University of Oxford / 2023 / 2 / c / Solution 2026-10-25

 View more

Write

V = V (G)

and

E = E (G)

. For

F \subseteq E

, let

c (F)

denote the number of connected components of a graph of the spanning subgraph

(V, F)

, including isolated vertices. The inclusion-exclusion principle, applied to the unwanted events that the two endpoints of an edge receive the same colour, gives the chromatic polynomial inclusion-exclusion formula

p_{G} (x) = \sum_{F \subseteq E} (- 1)^{∣ F ∣} x^{c (F)} .

(1)

To justify the exponent, imposing equal colours across all edges in

F

forces a single colour on each connected component of a graph of

(V, F)

, with independent choices between its connected components of a graph. Thus the corresponding count at

q

colours is

q^{c (F)}

. Equality for all positive integers proves the polynomial identity.

Fix an index

i

in the stated range. A subset

F

contributes to the coefficient of

x^{n - i}

exactly when

n - c (F) = i

. If

(V, F)

contains a graph cycle of length

s

, the hypothesis gives

s \geq ℓ

. All its

s

vertices lie in one connected component of a graph. For any connected component of a graph

D

, its contribution to

n - c (F)

∣ V (D) ∣ - 1

, so

n - c (F) = \sum_{D} (∣ V (D) ∣ - 1) \geq s - 1 \geq ℓ - 1.

(2)

This contradicts

i \leq ℓ - 2

. Therefore every contributing

(V, F)

is a forest. The forest identity

∣ F ∣ = n - c (F)

then gives

∣ F ∣ = i

Conversely, every

i

-edge subset is a forest, since a graph cycle in it would have at most

i < ℓ

edges. It therefore has

c (F) = n - i

and contributes exactly

(- 1)^{i}

. There are

(i m)

such subsets, by the definition of a binomial coefficient. Consequently

[x^{n - i}] p_{G} (x) = (- 1)^{i} (i m), a_{i} = (i m) (0 \leq i \leq ℓ - 2) .

(3)

Here the coefficient notation is understood within the defined indices

0 \leq i \leq n

; if the displayed range is extended past

n

, the coefficients beyond the constant term can be set to zero. For a forest,

m \leq n - 1

, so the binomial coefficients there are also zero. The key reason girth determines initial chromatic coefficients is that a graph cycle can affect only exponents whose loss of connected components of a graph is at least

ℓ - 1

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 30 / 3 / Solution Created 2026-10-03 Updated 2026-10-14

 View more

For a profinite abelian group

G

, its Iwasawa algebra is the completed group algebra

Λ (G) = U lim Z_{p} [G / U] = U, r lim (Z / p^{r} Z) [G / U],

(1)

where

U

runs over open subgroups. The transition map sums the coefficients over the fibers of

G / V \to G / U

when

V \subset U

. Consequently an element gives compatible values

μ (gU) \in Z_{p}

on cosets, equivalently a finitely additive

Z_{p}

-valued p-adic measure on the clopen sets of

G

. Conversely these values specify every finite-quotient coefficient. Integration of a continuous function with values in

Z_{p}

is obtained by uniform approximation by locally constant functions; the integrals converge because all measure values have

p

-adic absolute value at most

1

. Multiplication in the Iwasawa algebra becomes convolution of p-adic measures. This is its measure realization of an Iwasawa algebra.

The Mahler theorem states that each continuous function

g : Z_{p} \to Z_{p}

has the unique expansion converging in the sense of uniform convergence

g (x) = \sum_{n \geq 0} b_{n} (n x), b_{n} \in Z_{p}, b_{n} ⟶ 0.

(2)

Its Mahler coefficients are

b_{n} = Δ^{n} g (0) = \sum_{j = 0}^{n} (- 1)^{n - j} (j n) g (j),

(3)

and

∥ g ∥_{\infty} = sup_{n} ∣ b_{n} ∣_{p}

. The same assertion holds for continuous functions with values in

Q_{p}

with coefficients in

Q_{p}

Given

f (T) = \sum_{n \geq 0} a_{n} T^{n} \in R

, define the bounded linear functional

L_{f} (g) = \sum_{n \geq 0} a_{n} b_{n} .

(4)

The sum converges because

a_{n} \in Z_{p}

and

b_{n} \to 0

. Its values on indicator functions of clopen sets give a p-adic measure, denoted

λ (f)

, with

\int_{Z_{p}} (n x) d λ (f) = a_{n} .

(5)

Conversely, a p-adic measure determines these coefficients

a_{n} \in Z_{p}

, and continuity allows termwise integration of every Mahler expansion. Thus the inverse is

μ ⟼ \sum_{n \geq 0} (\int (n x) d μ) T^{n},

(6)

which is the Amice transform. These two constructions are inverse, proving the canonical bijection $λ : R ≃ Λ (Z_{p})$ . In fact it is an isomorphism of rings: the identity

(n x + y) = \sum_{i + j = n} (i x) (j y)

identifies convolution of p-adic measures with multiplication of formal power series. For example,

λ (1) = δ_{0}

and

λ (1 + T) = δ_{1}

, where

δ_{a}

is the Dirac measure at

a

For the moment identity, let

{n k}

denote a Stirling number of the second kind. The finite polynomial identity

x^{k} = \sum_{n = 0}^{k} n! {n k} (n x)

(7)

gives

\int x^{k} d λ (f) = \sum_{n = 0}^{k} a_{n} n! {n k}

. On the other hand,

D = (1 + T) d / d T

satisfies

D^{k} (1 + T)^{x} = x^{k} (1 + T)^{x}

for every nonnegative integer

x

. Expanding

(1 + T)^{x}

and evaluating at

T = 0

yields

x^{k} = \sum_{n = 0}^{k} (n x) (D^{k} T^{n}) (0) .

(8)

Comparison in the basis of binomial polynomials gives

(D^{k} T^{n}) (0) = n! {n k}

. Terms with

n > k

have zero constant term after at most

k

differentiations, so no infinite-series interchange is needed. Therefore

\int_{Z_{p}} x^{k} d λ (f) = (D^{k} f) (0) (k \geq 0) .

(9)

The case

k = 0

says that the total mass is

f (0)

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 9 / 3 / Solution Created 2026-10-03 Updated 2026-10-14

 View more

Use the normalized chordal metric

χ (z, w) = \frac{∣ z - w ∣}{1 + ∣ z ∣ ^{2} 1 + ∣ w ∣ ^{2}}, χ (z, \infty) = \frac{1}{1 + ∣ z ∣ ^{2}}, χ (\infty, \infty) = 0.

(1)

Under stereographic projection it is half the Euclidean chord distance on the unit sphere, which proves the metric axioms and the agreement with the usual sphere topology. If

ρ

is spherical geodesic distance, then

ρ = 2 arcsin χ

, so

2 χ \leq ρ \leq π χ

A rational map is holomorphic, hence smooth, as a map of compact spheres. At a pole use

1/ R

as target coordinate, and at infinity use

1/ z

as source coordinate; neither is a singularity of the sphere map. Its differential in the round metric has a finite maximum norm

L

. Integrating its norm along a minimizing spherical geodesic gives

ρ (R z, Rw) \leq L ρ (z, w)

. The preceding comparisons imply

χ (R z, Rw) \leq \frac{π L}{2} χ (z, w) .

(2)

This proves that the rational map is Lipschitz in the chordal metric. For a constant map take constant zero; for a nonconstant map the bound is finite by compactness. In finite coordinates the differential norm is

R^{#} (z) = ∣ R^{'} (z) ∣ (1 + ∣ z ∣^{2}) / (1 + ∣ R (z) ∣^{2})

, with its continuous sphere extension.

Now suppose

R, S

are commuting maps. We first prove

S (F (R)) \subseteq F (R)

. The family

{R^{n}}

is locally equicontinuous on

F (R)

, by the normality equivalence in question 1. Commutation and the Lipschitz estimate give, for all

n

χ (R^{n} (S (x)), R^{n} (S (x_{0}))) = χ (S (R^{n} (x)), S (R^{n} (x_{0}))) \leq C_{S} χ (R^{n} (x), R^{n} (x_{0})) .

(3)

For

x_{0} \in F (R)

choose a source ball within that open set, small enough to make the right side less than any prescribed

ϵ

uniformly in

n

. Holomorphic openness makes its image contain a ball about

S (x_{0})

. Every point

w

of that target ball has some preimage

x

in the chosen source ball, so the same inequality proves equicontinuity of the iterates of

R

S (x_{0})

. Repeating at each point of the image gives local normality on that image. Thus the stated inclusion holds even where

S

has a rational critical point.

Carefully state the permitted Montel theorem: a family of meromorphic maps on an open domain, all omitting the same three distinct values of the Riemann sphere, is normal for locally uniform spherical convergence. Since

de g R \geq 2

, question 1 shows that

J (R)

contains at least three distinct points. The forward inclusion just proved means every iterate of

S

maps

F (R)

into itself and therefore omits those three points there. Montel gives

F (R) \subseteq F (S)

. Exchanging the roles, using

de g S \geq 2

, gives the opposite inclusion. Consequently

F (R) = F (S), J (R) = J (S) .

(4)

This proves that commuting rational maps of degree at least two have the same Julia set without assuming either is an iterate of the other.

For commuting maps of degree one with different Julia sets, take

R (z) = 2 z, S (z) = z /2; J (R) = {0}, J (S) = {\infty} .

(5)

Their two compositions are the identity, and the Julia sets follow from the expanding and contracting Möbius cases in question 1.

For equal Julia sets without commutation, take

R (z) = z /2, S (z) = z /2 + 1; J (R) = J (S) = {\infty} .

(6)

Both affine maps contract toward their finite fixed points and have a repelling periodic point at infinity. But

R \circ S = z /4 + 1/2

, while

S \circ R = z /4 + 1

, so they do not commute.

Finally the distinct Chebyshev polynomials

R (z) = 2 z^{2} - 1, S (z) = 4 z^{3} - 3 z

(7)

have degrees two and three and neither is a pure power of

z

. Direct expansion gives both compositions equal to

32 z^{6} - 48 z^{4} + 18 z^{2} - 1

. Equivalently

T_{m} (T_{n} (z)) = T_{mn} (z)

, first seen at

z = cos θ

and then as a polynomial identity. This provides the requested higher-degree pair.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2011 / ia / Paper 4 / 7E / Solution Created 2026-09-24 Updated 2026-10-14

 View more

Define the binomial coefficient

(i n)

to be the number of

i

-element subsets of an

n

-element set. Counting ordered selections and dividing by the

i!

orders of each subset gives

(i n) = \frac{n !}{i ! ( n - i )!}, 0 \leq i \leq n .

(1)

Every subset has exactly one size, while each of the

n

elements can independently be included or omitted. Hence the power set has

2^{n}

members and

i = 0 \sum n (i n) = 2^{n} .

(2)

To prove the binomial theorem, expand the product of

n

factors

(1 + x)

. A term

x^{i}

results from choosing

x

from precisely an

i

-element subset of the factors and choosing one elsewhere. Its coefficient is therefore

(i n)

. This is a finite distributive expansion, valid for every real

x

, and gives

(1 + x)^{n} = \sum_{i = 0}^{n} (i n) x^{i} .

(3)

Differentiate this polynomial identity and set

x = 1

i = 0 \sum n i (i n) = n 2^{n - 1} .

(4)

A second derivative gives

\sum i (i - 1) (i n) = n (n - 1) 2^{n - 2}

for

n \geq 2

. Since

i^{2} = i (i - 1) + i

, it follows that

i = 0 \sum n i^{2} (i n) = n (n + 1) 2^{n - 2} .

(5)

The formula also holds for

n = 1

, when its value is one; that case can be checked directly without differentiating twice.

For the squared binomial coefficients, compare the coefficient of

x^{n}

(1 + x)^{n} (1 + x)^{n} = (1 + x)^{2 n}

. On the left it is

\sum_{i} (i n) (n - i n)

, and the binomial coefficient symmetry gives

(n - i n) = (i n)

. Thus

i = 0 \sum n (i n)^{2} = (n 2 n) .

(6)

Finally put

S = \sum_{i} i (i n)^{2}

and replace the index

i

n - i

. The same symmetry gives

S = \sum_{i} (n - i) (i n)^{2}

. Adding the two expressions and using the preceding identity yields

i = 0 \sum n i (i n)^{2} = \frac{n}{2} (n 2 n) .

(7)

 Read the full article

Past exam of the mathematics course of the year 1 of the natural sciences course of the University of Cambridge / 2019 / Paper 1 / 8 / Solution 2026-10-18

 View more

Multiply the partial fraction decomposition by

(x + 1) (x + 2)^{2}

to obtain a polynomial identity:

x^{2} + 1 = a (x + 2)^{2} + b (x + 1) (x + 2) - 5 (x + 1) .

(1)

x = - 1

, this gives

a = 2

. Comparing the coefficients of

x^{2}

then gives

a + b = 1

, so

a = 2, b = - 1.

(2)

The remaining coefficients agree:

4 a + 3 b - 5 = 0

and

4 a + 2 b - 5 = 1

. The original rational identity is understood away from its poles

- 1

and

- 2

 Read the full article

Past exam of the mathematics course of the year 1 of the natural sciences course of the University of Cambridge / 2025 / Paper 1 / 8 / Solution 2026-10-18

 View more

For the partial fraction decomposition, multiply by

(x - 1) (x - 2)

to obtain the polynomial identity

x^{2} + 1 = a (x - 1) (x - 2) + b (x - 2) + c (x - 1) .

(1)

Comparing the

x^{2}

coefficients gives

a = 1

. Substitution of

x = 1

gives

2 = - b

, while

x = 2

gives

5 = c

. Therefore

a = 1, b = - 2, c = 5.

(2)

The original identity holds for

x \neq = 1, 2

; evaluating the multiplied polynomial identity at those values is valid.

 Read the full article

Past exam of the numerical analysis course of the University of Oxford / 2023 / 2 / b / Solution 2026-10-25

 View more

The monomial

x^{k}

lies in

Π_{n}

and already fits the data. Uniqueness of polynomial interpolation therefore gives

p_{n} (x) = x^{k} .

(1)

Apply this result with a nonnegative integer

m \leq n

. Its Lagrange interpolation representation is the polynomial identity

x^{m} = \sum_{i = 0}^{n} x_{i}^{m} \frac{\prod _{j \neq = i} ( x - x _{j} )}{\prod _{j \neq = i} ( x _{i} - x _{j} )} .

(2)

The numerator in each summand is a monic polynomial of degree

n

, so the coefficient of

x^{n}

on the right is exactly

\sum_{i} x_{i}^{m} / \prod_{j \neq = i} (x_{i} - x_{j})

. The coefficient on the left is zero for

m < n

and one for

m = n

. Comparing coefficients proves the Lagrange leading-coefficient identity

i = 0 \sum n \frac{x _{i}^{m}}{\prod _{j \neq = i} ( x _{i} - x _{j} )} = {0, 1, 0 \leq m < n, m = n .

(3)

The intended exponent range is

m \geq 0

: arbitrary negative exponents would not give this polynomial identity. For

m = 0

x_{i}^{0}

denotes the value of the constant polynomial

1

, including at a zero interpolation node.

 Read the full article

Past exam of the options I course of the University of Oxford / 2009 / A / A1 / i / Solution 2026-10-31

 View more

The polynomial identity

x^{9} - 1 = (x^{3} - 1) (x^{6} + x^{3} + 1)

(1)

shows that the roots are the ninth roots of unity which are not third roots. These are precisely the primitive ninth roots of unity, all powers of

ζ_{9} = e^{2 πi /9}

. Thus the splitting field is

Q (ζ_{9})

. The supplied irreducibility statement makes the displayed degree-six polynomial the minimal polynomial of

ζ_{9}

, giving

[Q (ζ_{9}) : Q] = 6 .

(2)

 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 / 8 / b / iii / Solution 2026-10-31

 View more

Using the probability mass function of the Poisson distribution directly gives

E [X^{n}] = \frac{1}{e} j = 0 \sum \infty \frac{j ^{n}}{j !} .

(1)

For each fixed positive integer

n

, this series converges: the ratio of successive nonzero terms is

(1 + 1/ j)^{n} / (j + 1)

, which tends to zero. Equivalently, using the polynomial identity in (ii) and the factorial moments from (a)(iv) gives

E [X^{n}] = \sum_{k = 1}^{n} A (n, k)

; the extension of that identity to

X = 0, 1

is justified in (iv).

 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 / 8 / b / iv / Solution 2026-10-31

 View more

Both sides of (ii) are polynomials in the colour count, and they agree at every integer

x \geq 2

. A nonzero polynomial has only finitely many roots, so this is a polynomial identity and holds also at

x = 0, 1

. It can therefore be evaluated at every possible value of the Poisson random variable

X

Take expectations and use the factorial moments from (a)(iv). The sum over

k

is finite, so linearity of expectation gives

E [X^{n}] = \sum_{k = 1}^{n} A (n, k) E [X (X - 1) \dots (X - k + 1)] = \sum_{k = 1}^{n} A (n, k) = B (n) .

(1)

Combining this with (iii) proves Dobiński's formula for the Bell numbers:

B (n) = \frac{1}{e} j = 0 \sum \infty \frac{j ^{n}}{j !} (n \geq 1) .

(2)

For completeness, the empty set has one partition of a set, giving

B (0) = 1

; that case uses the empty-product conventions

0^{0} = 1

in this identity and a

k = 0

term in the partition sum.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 4 / d / Solution 2026-10-31

 View more

Require a nonzero divisor. Polynomial long division repeatedly subtracts the multiple of

b

that cancels the leading term of the current polynomial remainder. Use fresh arrays for both outputs.

PROCEDURE DivMod(VAR div, mod: Poly; a, b: Poly);
VAR q, r: Poly; cap, i, j, k, old: INTEGER; t: REAL;
BEGIN
  ASSERT(b.degree >= 0);
  cap := a.degree+1; IF cap < 1 THEN cap := 1 END;
  r.degree := a.degree; NEW(r.coeff, cap);
  r.coeff[0] := 0.0;
  FOR i := 0 TO a.degree DO r.coeff[i] := a.coeff[i] END;
  IF a.degree < b.degree THEN
    Zero(q)
  ELSE
    q.degree := a.degree-b.degree;
    NEW(q.coeff, q.degree+1);
    FOR i := 0 TO q.degree DO q.coeff[i] := 0.0 END;
    WHILE r.degree >= b.degree DO
      old := r.degree; k := old-b.degree;
      t := r.coeff[old]/b.coeff[b.degree];
      q.coeff[k] := q.coeff[k]+t;
      FOR j := 0 TO b.degree-1 DO
        r.coeff[k+j] := r.coeff[k+j]-t*b.coeff[j]
      END;
      r.coeff[old] := 0.0;
      DEC(r.degree); Normalize(r)
    END;
    Normalize(q)
  END;
  div := q; mod := r
END DivMod;

The loop invariant is the polynomial identity

a = q b + r

. Setting

t = r_{old} / b_{d e g b}

and

k = old - de g b

replaces

q

q + t x^{k}

and

r

r - t x^{k} b

, preserving this identity. The leading coefficient of that difference is exactly zero, so setting its stored value to zero and decreasing degree implements its exact cancellation. Each iteration strictly decreases the degree of the polynomial remainder.

At termination,

a = div b + mod, mod = 0 or de g mod < de g b .

(1)

The zero polynomial dividend, a lower-degree dividend, and a constant divisor are all covered. Division by the zero polynomial is undefined. The two output record variables must be distinct and separate from the input record variables; no input coefficient array is written. For

de g a \geq de g b

, the work is

O ((de g a - de g b + 1) (de g b + 1))

 Read the full article