Maths › Key ideas

Key ideas

Concise results, conditions and common distinctions from each topic, grouped by unit and linked to the full lesson. Open a unit to skim it, or search for a single idea.

463 ideas

ProofYears 12-132 topics

The structure of proof: deduction and exhaustion

A proof runs from stated assumptions through checkable steps to a conclusion, and establishes it for every case the claim covers.
P ⇒ Q claims one direction; P ⇔ Q claims both, so an equivalence takes two proofs.
Use deduction for a general argument, and exhaustion when a complete list of cases can be checked.

Disproof and proof by contradiction

One counter example is enough to disprove a universal claim.
Assume the opposite, reason correctly until you reach an impossibility, and the original statement is proved.

Algebra and functionsYears 12-138 topics

Indices and surds

Three index laws govern every power, and a fractional exponent denotes a root: a^m/n is the nth root of a^m.
Take out the largest square factor; rationalise with the conjugate when the denominator has two terms.

Quadratic functions

The completed square gives the vertex, and the constant outside the bracket is the maximum or minimum value.
The sign of the discriminant gives the number of real roots: two, one repeated, or none.

Simultaneous equations and inequalities

Substitute the linear equation into the quadratic: the roots are the x-coordinates of the intersections, and the discriminant gives how many there are.
Solve a quadratic inequality from a sketch: find the roots, note which way the parabola opens, then read the sign on each interval.

Polynomials and the factor theorem

Divide f(x) by (x − a) and the remainder is f(a). A remainder of zero names a factor.
One root found by the factor theorem, one division, and the remaining quadratic factorised or solved by the formula.

Graphs, proportion and transformations

The factors give the sketch: simple roots cross the axis, repeated roots touch it, and an asymptote is a line the curve approaches, which need not be a line it cannot meet.
Outside the bracket acts on y and does what it says. Inside acts on x and does the opposite.
Under y = 1/f(x) a zero becomes a vertical asymptote and a turning point swaps type at the reciprocal height, with the sign kept.
A rational curve is determined by its zeros, its vertical asymptotes and its end behaviour; divide out when the numerator has the higher degree, and set y = k with a non-negative discriminant to find the range.

Functions, inverses and the modulus

fg applies g first. An inverse reverses the function, is the reflection of its graph in y = x, and exchanges domain with range.
Only one-one functions invert.
Equal moduli mean equal squares, and |x − a| < b is the interval a − b < x < a + b.

Partial fractions

One fraction per distinct bracket, and a squared bracket takes a term over the bracket and a term over its square.
Substitute each bracket's root to find the corresponding constant, then compare coefficients for any constant that remains.

Functions in modelling

The modelling cycle is specify, collect, process and represent, interpret, then repeat with a sharper question.
The behaviour determines the family: a fixed period gives a trigonometric model, a rate proportional to the amount gives an exponential model, and a constant product gives a reciprocal model.
Fit the constants, interpret them with units, and state the conditions under which the model fails.

Coordinate geometryYears 12-133 topics

Straight lines

One point and one gradient determine a line, and y − y₁ = m(x − x₁) is its equation.
Parallel lines share m. Perpendicular gradients multiply to −1.

Circles

A circle is Pythagoras about a fixed centre, and completing the square recovers the centre and radius from any form.
Radius meets tangent at a right angle, the perpendicular from the centre bisects a chord, and a right angle on the circle names a diameter.
Two circles meet when the distance between their centres lies between |r₁ − r₂| and r₁ + r₂, touching at either end of that range.

Parametric equations

A parametric curve is the set of points (x(t), y(t)) for t in a stated range.
Eliminate t by substitution or by an identity, then state which part of the Cartesian curve the parameter range covers.

Sequences and seriesYears 12-135 topics

The binomial expansion

Row n of Pascal's triangle gives the coefficients nCr, and every term of (a + b)ⁿ has total degree n.
For small |x| the terms decrease in size, so a truncated expansion approximates the value, with an error of the order of the first term omitted.

The general binomial expansion

A negative or non-integer exponent makes the expansion infinite; a positive integer exponent makes it terminate. |bx/a| < 1 is where the infinite one converges, with the endpoints needing their own check.
Factorise out aⁿ, expand the remaining bracket, and state the interval of validity with the expansion.

Sequences and sigma notation

An nth-term formula gives any term directly; a recurrence gives each term from the previous one and needs a stated first term.
Classify a sequence as increasing, decreasing or periodic, giving the order in the periodic case; a sum in sigma notation states the counter, the expression for one term and the range.

Arithmetic series

The nth term is a plus (n − 1) common differences: count steps between terms rather than term positions.
Adding the sum forwards to the sum backwards gives n columns each totalling a + l, so the sum is n(a + l)/2.

Geometric series

Each term is r times the previous one, and subtracting rS_n from S_n cancels all but two terms, which proves the sum formula for r ≠ 1.
The series converges when |r| < 1, with sum to infinity a/(1 − r); take logarithms to find the number of terms needed to reach a stated total.

TrigonometryYears 12-136 topics

Triangles and the sine and cosine rules

Use the sine rule for opposite pairs, and the cosine rule for two sides with the included angle or for three sides.
An inverse sine gives two possible angles; test both against the angle sum and the stated side lengths rather than against the diagram.

Trigonometric graphs and equations

The unit circle defines sin and cos for every angle; the graphs repeat and the table of exact values covers the rest.
Widen the interval with the substituted angle, find every crossing in it, then translate back.

Radians, arcs and small angles

A radian is the angle subtended by an arc equal to the radius; π radians = 180°.
Arc length is rθ and sector area ½r²θ; for small θ in radians, sin θ ≈ θ, tan θ ≈ θ and cos θ ≈ 1 − θ²/2.

Reciprocal and inverse trigonometric functions

sec, cosec and cot are reciprocals of cos, sin and tan, undefined wherever those functions are zero.
Divide the Pythagorean identity by cos² or sin² for the two further identities; restrict the domain before inverting, and the range determines which angle the inverse returns.

Compound angles and the harmonic form

A sum of angles is expanded by the compound formulae; sine and cosine do not distribute over addition.
a sin θ + b cos θ is a single sinusoid of amplitude √(a² + b²); write the harmonic form first, then read off the extreme values and solve.

Trigonometric modelling

Centre line, amplitude and period are three separate constants, each in a fixed position in the formula.
Combine two-term models into harmonic form, and read the extreme values as the centre line plus or minus R.

Exponentials and logarithmsYear 123 topics

Exponential functions and e

The curve of a^x passes through (0, 1) and approaches the x-axis without meeting it.
e is the base for which the gradient of e^x equals its value; the gradient of e^kx is ke^kx.

Logarithms and their laws

A logarithm is an exponent: a to the n equals x and log base a of x equals n are one statement.
Logs turn multiplication into addition and bring exponents down as multipliers.

Log graphs and exponential models

A power law gives a straight line on log-log axes and an exponential gives one on log-linear axes; the plot that straightens the data identifies the model.
In Ae^kt, A is the value at t = 0, k is the proportional rate of change, and ln 2 divided by |k| is the doubling or halving time.

DifferentiationYears 12-137 topics

The derivative from first principles

The derivative is the limit of the chord gradient as h tends to zero, and it gives the gradient of the tangent.
Divide the factor of h out first, then take the limit; the remaining expression is the gradient function.

Differentiating powers of x

Multiply by the exponent and reduce the exponent by one: the derivative of xⁿ is nxⁿ⁻¹, wherever the real function xⁿ is differentiable.
The rule applies to powers only, so rewrite products, roots and fractions as powers of x before differentiating.

Tangents, turning points and curve behaviour

The tangent at (a, f(a)) has gradient f'(a); the normal has gradient −1/f'(a) when f'(a) ≠ 0, and is the line x = a when f'(a) = 0; stationary points solve f'(x) = 0.
The sign of f''(a) classifies a stationary point where it is non-zero; a point of inflection requires a change of concavity, which f''(a) = 0 alone does not establish.

Differentiating trig, exponentials and logs

With x in radians, sin x differentiates to cos x, cos x to −sin x, e^x to itself, and ln x to 1/x for x > 0.
Every k multiplies the term; every base other than e carries a factor ln a.

The product, quotient and chain rules

The chain rule multiplies the two rates; the product rule is u'v + uv'; the quotient rule is (u'v − uv')/v², for v ≠ 0.
Select the rule from the structure of the expression, name the inner function u, and factorise the answer.

Implicit and parametric differentiation

Differentiate equations as they stand; every y-term carries a factor dy/dx from the chain rule.
Parametric gradients divide dy/dt by dx/dt where dx/dt ≠ 0; for x given in terms of y, dy/dx is the reciprocal of dx/dy where dx/dy ≠ 0.

Rates of change and building differential equations

Linked quantities have rates linked by the chain rule: write the connecting formula, differentiate it, and multiply the rates.
Translate a rate statement term by term: the rate of change becomes a derivative, proportionality introduces a constant k, and a decrease gives a negative sign.

IntegrationYears 12-137 topics

Integration as antidifferentiation

Raise the exponent by one, divide by the new exponent, and include the + c.
A gradient function determines a family of curves; one known point determines which member.

Definite integrals and areas

Antidifferentiate, bracket, substitute both limits and subtract; the constant of integration cancels.
A definite integral is signed area; a geometric area is not signed. Sketch the curve, split at the axis crossings, and add the absolute values.

Integrating standard functions

Reverse each standard derivative and divide by k; the case excluded by the power rule is ∫(1/x) dx = ln|x| + c.
A squared trigonometric function is not a standard integral; use an identity to rewrite it as terms that are.

Integration by substitution and by parts

A function multiplied by its own derivative integrates by reversing a chain rule, by substitution or by inspection.
When no substitution is given, choose it from the structure: a linear bracket becomes u, a root of x becomes u = √x, and √(a² − x²) becomes x = a sin θ.
Parts replaces one integral by another: differentiate the factor that simplifies, and apply it again where the new integral is still a product.

Integrating rational functions

Decompose a rational integrand into partial fractions; each term with a linear denominator integrates to a logarithm.
A logarithm arises only from the f'/f form; other terms are powers written in fraction notation.

Areas, parametric curves and the limit of a sum

The area between two curves is one integral of top minus bottom between their intersections, wherever the region lies relative to the axis.
Parametric areas are found in t as ∫y (dx/dt) dt, and the definite integral is defined as the limit of a sum of strips as δx tends to zero.

Solving differential equations

Separate the variables, integrate both sides, and write a single constant at the integration step; check g(y) = 0 first for constant solutions.
A particular solution comes from substituting the condition into the general solution, and in context it is valid only on an interval that must be stated.

Numerical methodsYear 133 topics

Locating roots and iteration

A sign change of a continuous function across an interval shows that at least one root lies inside it; a sign change across the values that round to a stated figure proves an accuracy claim.
For x_n+1 = g(x_n), iterates started near a solution of x = g(x) converge when |g'(x)| is less than 1 there and move away when it is greater than 1.

The Newton-Raphson method

Newton-Raphson takes the tangent at x_n to the x-axis; near a simple root, with a suitable starting value and a sufficiently smooth f, convergence is usually quadratic.
Where f'(x_n) = 0 and f(x_n) is not zero, the next step is undefined; where f'(x_n) is small, the next iterate is far away and the sequence may converge to a different root or diverge.

The trapezium rule

The trapezium rule adds straight-topped strips, end ordinates once and interior ordinates twice, with n + 1 ordinates to n strips.
Where f'' keeps one sign, it fixes the direction of the error: convex overestimates, concave underestimates, and more strips reduce the error without changing its direction.
Where the function is monotonic on every strip, the two end-ordinate sums lie either side of the integral, h(y_n − y₀) apart, with the trapezium value at their mean.

VectorsYears 12-132 topics

Vectors in two dimensions

Vectors add component by component, a scalar multiple changes magnitude and possibly direction, and parallel vectors are scalar multiples of each other.
$\overrightarrow{AB}$ = b − a, destination minus start, and its magnitude |AB| is the distance.

Vectors in three dimensions

A third component follows the same rules: the magnitude is the square root of the sum of three squares, and AB = b − a.
Geometry in three dimensions is settled by distances and scalar multiples, computed component by component.

StatisticsYears 12-1310 topics

Sampling and the large data set

A sample represents its population only if chance, not convenience, chose it.
Stratify when you know the structure. The same fraction from every stratum keeps the sample's proportions matched to the population's.

Measures of location and spread

Location by position: order the data, find the position, then read the value.
σ² is the mean of the squares minus the square of the mean; scaling the data changes σ, translating it does not.

Representing and interpreting data

In a histogram, area is frequency and the vertical axis is frequency density.
By the common convention, fences lie one and a half IQRs beyond the quartiles and values beyond a fence are plotted separately; use the rule the question states.
Read any diagram in the same order: axes, key, what one mark represents, then a total that can be checked.

Correlation and regression

r measures the direction and strength of a linear association, not causation.
Regress y on x, predict only inside the data, and read a and b in the question's own units.

Probability and Venn diagrams

Draw the diagram, fill the overlap first, and check that the regions total 1.
Mutually exclusive means P(A ∩ B) = 0. Independent means P(A ∩ B) = P(A)P(B). Both hold together only if P(A) = 0 or P(B) = 0.

Conditional probability

To condition, divide P(A ∩ B) by the probability of the conditioning event, which must be non-zero.
On a tree, multiply along a path and add between paths; without replacement the second-stage denominators are reduced by one.

The binomial distribution

Fixed n, two outcomes, constant p, independent trials. Only then is it binomial.
Point probabilities by the formula, everything else through ≤ and the cumulative function.

The normal distribution

The normal curve is symmetric about μ, with points of inflection at μ ± σ and about 95% of the distribution within 2σ of the mean.
Use a normal model only for data that are approximately symmetric and bell-shaped, and standardise with Z = (X − μ)/σ whenever a parameter is unknown.

Hypothesis testing with the binomial

Assume H₀, calculate how extreme the data are under it, and compare with the stated significance level; then reject H₀ or do not reject it.
The critical region is decided before the data, and its probability under H₀ is the actual significance level.

Hypothesis testing: correlation and the normal

Correlation: hypotheses in ρ, and compare the sample r against the table value for the right number of tails.
The mean of n independent readings has distribution N(μ, σ²/n), so standardise with σ/√n.

MechanicsYears 12-139 topics

Modelling, quantities and units

Model first. Every standard word deletes one complication, and you should know which one.
SI units in, signed one-dimensional vectors throughout, magnitudes only at the end.
Dimensions come from the units: kilogram to M, metre to L, second to T, with ratios of like quantities dimensionless.
Matching dimensions across an equation tests it; matching powers predicts one, up to a dimensionless constant the method leaves open.

Kinematics with constant acceleration

List s, u, v, a, t, then pick the equation missing the letter you do not need.
With up positive, the acceleration is a constant −9.8 m s⁻² throughout the modelled flight, including at the highest point.

Kinematics with variable acceleration

Differentiate x to v to a, integrate back, and let the conditions fix the constants.
Solve v = 0 to find the turning points, and add distance leg by leg.

Forces and Newton's laws

Draw the diagram first: every force acting on the object, and no force it exerts on anything else.
Resolve, sum with signs, apply F = ma. Equilibrium is the a = 0 special case.

Connected particles and pulleys

System for the acceleration, single particle for the tension.
One equation per mass, own direction positive, then add to eliminate T.

Projectiles

Resolve once: u cos θ horizontally, constant during the modelled flight, and u sin θ vertically with acceleration −g.
Solve in whichever direction the given data allow, then use the same t in the other direction.

Friction and inclined planes

Friction matches the applied force up to μR, and only sliding or the limiting case makes that an equality.
On a slope, mg sin θ along and mg cos θ into it, and compare tan θ with μ to see whether the block slips.

Statics of a particle

Equilibrium means the components sum to zero in two chosen directions.
Choose axes that simplify the components; friction takes the value the other forces require, up to μR.

Moments

Moment = force × perpendicular distance, with a stated sense of rotation.
A beam in equilibrium satisfies two conditions: the forces sum to zero, and the moments about any point sum to zero.

Further proofFurther Maths2 topics

Proof by induction: sums and series

Verify P(1), then show P(k) forces P(k + 1). Both, every time.
For sums, the step is always the same. Add the next term to the assumed total, then tidy.
Write out the conclusion sentence in full: the proof is not complete without it.

Induction: divisibility and matrices

Divisibility steps rewrite the k + 1 case as (multiple of the k case) + (visible multiple).
Matrix steps are one multiplication, A to the k times A, worked entry by entry.
Inequality steps chain: assumption first, then a second inequality you state, and the base case sits where the range starts.

Complex numbersFurther Maths4 topics

Complex arithmetic and the Argand diagram

i squared is minus one. Everything else is ordinary algebra.
To divide, multiply top and bottom by the conjugate of the denominator.
Conjugation reflects in the real axis, and real quadratics have conjugate root pairs.
For square roots, square x + yi, compare real and imaginary parts, and quote the pair ±(x + yi).

Modulus, argument and loci

Modulus is distance from the origin; for z ≠ 0 the argument is the angle from the positive real axis, taken here in (−π, π] and read from a sketch.
Products multiply moduli and add arguments; quotients divide and subtract.
|z − a| = r is a circle, |z − a| = |z − b| a bisector, arg(z − a) = θ a half-line.

De Moivre's theorem and trigonometric identities

Powers in modulus-argument form: |zⁿ| = |z|ⁿ and arg(zⁿ) ≡ n arg z (mod 2π); in the form z = r e^iθ this is an index law.
For identities, expand (cos θ + i sin θ)ⁿ binomially and equate parts with cos nθ + i sin nθ.
With z = cos θ + i sin θ, zⁿ + 1/zⁿ = 2 cos nθ and zⁿ − 1/zⁿ = 2i sin nθ, which turn a power of cos θ or sin θ into multiple angles.
For a series of cosines or sines, sum C + iS as one geometric series, then take the part you were asked for.

Roots of unity and complex roots

nth roots of a non-zero number: take the real positive nth root of the modulus, divide the argument by n, then space the roots by 2π/n.
The n roots of unity form a regular n-gon on the unit circle and, for n ≥ 2, sum to zero.
Every root of zⁿ = w is one root times a root of unity, and zⁿ = 0 has only z = 0.

MatricesFurther Maths3 topics

Matrix algebra and transformations

A matrix's columns are the images of the unit vectors, so a stretch reads as rows (a, 0) and (0, b), a shear with the x-axis invariant as rows (1, k) and (0, 1), and the size of the determinant gives the area scale factor.
Doing B then A is the product AB, with the first-applied matrix nearest the vector, and A(BC) = (AB)C leaves the bracketing free; for invertible M a curve's image comes from substituting M⁻¹(X, Y), and for singular M from parameterising the curve.
In 3-D, reflections in coordinate planes reverse one sign; rotations place a 2 × 2 rotation in the other two coordinates, with a stated sense convention.
AB = 0 does not make A or B zero, so cancelling a matrix off both sides needs that matrix to be invertible.

Determinants and inverses

|det M| is the area scale factor in two dimensions and the volume scale factor in three; the sign records whether orientation is preserved or reversed.
A zero determinant means the image has lower dimension, so there is no inverse.
2 × 2 inverse: swap the diagonal, negate the off-diagonal, divide by the determinant. 3 × 3 inverse: minors, signs, transpose, divide.
Adding a multiple of one row or column to another leaves a determinant unchanged, scaling one scales it, swapping two flips the sign, and det(AB) = det A × det B.

Systems of equations and invariance

det ≠ 0 gives the unique solution v = M⁻¹b; when det = 0, compare ranks or test consistency to decide between no solution and infinitely many.
An invariant line maps to itself as a set; a line of invariant points fixes each of its points.

Further algebra and seriesFurther Maths3 topics

Roots of polynomials

Expand a(z − α)(z − β)…: root sums and products sit in the coefficients, signs alternating.
For transformed roots, substitute z in terms of w, or rebuild from the new sum and product.
Real coefficients force complex roots into conjugate pairs.

Summing series and the method of differences

Polynomial series split into Σr³, Σr² and Σr; check which of these your awarding organisation's formula booklet supplies.
The method of differences writes each term as f(r) − f(r + 1); write out both ends and state the terms that remain.

Maclaurin series

Maclaurin: the coefficient of x^r is the rth derivative at zero divided by r factorial.
Substitute into a standard series for a composite, and transform the interval of validity for ln and arctan with the same substitution.
A finite Maclaurin polynomial needs only the required derivatives; the infinite series represents f only where it converges to f.
Simplify each derivative before evaluating it at zero.

Further vectorsFurther Maths2 topics

Lines and planes in three dimensions

Line: r = a + λb, one anchor point plus multiples of a direction, in two dimensions or three; the symmetric cartesian form requires every component of b to be non-zero.
Plane: r·n = d, every point whose displacement from the anchor is perpendicular to n.
Plane again: r = a + λb + μc, one parameter for each direction lying in it.

Intersections, angles and distances

Line into plane: substitute the parametric coordinates and solve one equation in λ; no solution means parallel, an identity means the line lies in the plane.
Line-plane angles use sine with the normal; plane-plane angles use cosine.
Shortest distances come from making the joining vector perpendicular to each of the available directions.

Further calculusFurther Maths3 topics

Volumes of revolution

About the x-axis, V = π∫y² dx between x-limits, with the radius measured perpendicular to the axis; square first, then integrate.
About the y-axis, V = π∫x² dy between y-limits, with x² rewritten in terms of y.
For a washer, dV = π(R² − r²) dx with R ≥ r ≥ 0; split the integral where the region crosses the axis or the outer radius changes.
Parametric curves: substitute for y² and dx, and change the limits to t.

Mean values and improper integrals

The mean value is the signed integral divided by the interval width, the height of a rectangle with the same signed integral.
Improper integrals: integrate to a letter, take the appropriate one-sided limit, then state whether it converges or diverges.
A singularity inside the interval splits the integral in two, and it converges only if both halves do.
Exponential and logarithmic cases are settled by the standard limits: x^ke^−x → 0 at ∞, x^kln x → 0 at 0.

Calculus with inverse trigonometric functions

Differentiate the inverse functions implicitly: sin y = x gives dy/dx = 1/√(1 − x²) for |x| < 1, and d(arctan x)/dx = 1/(1 + x²) for all real x.
For a > 0, ∫1/√(a² − x²) dx = arcsin(x/a) + c on an interval inside |x| < a, and ∫1/(a² + x²) dx = (1/a) arctan(x/a) + c.
Complete the square, split numerators, divide an improper fraction down first, and give every irreducible quadratic factor a Bx + C numerator, including at each repeated power.
Beyond the standard forms, substitute: x = a sin θ simplifies a² − x², x = a tan θ simplifies a² + x².

Hyperbolic functionsFurther Maths2 topics

Hyperbolic functions and identities

cosh and sinh are the even and odd parts of e^x, and cosh²x − sinh²x = 1 follows from the definitions.
Ranges: cosh x ≥ 1, 0 < sech x ≤ 1, |tanh x| < 1 and |coth x| > 1; sinh takes every real value and cosech takes every real value except 0.
Osborn's rule replaces cos by cosh and sin by sinh, reversing the sign once for each pair of sine factors.
arsinh x = ln(x + √(x² + 1)); arcosh x = ln(x + √(x² − 1)) for x ≥ 1, returning y ≥ 0; artanh x = ½ln((1 + x)/(1 − x)) for −1 < x < 1.

Calculus with hyperbolic functions

sinh' = cosh and cosh' = sinh, with no minus sign; tanh' = sech²x.
arsinh' = 1/√(x² + 1) for all real x; arcosh' = 1/√(x² − 1) for x > 1; artanh' = 1/(1 − x²) for −1 < x < 1.
Integrals of 1/√(x² + a²) give arsinh(x/a); integrals of 1/√(x² − a²) give arcosh(x/a) on x > a, and the logarithmic form with absolute values covers x < −a.
Substitute x = a sinh u or x = a cosh u, with a > 0, when the integrand is not in a standard form.

Polar coordinatesFurther Maths2 topics

Polar curves

x = r cos θ and y = r sin θ; form r² and r cos θ to convert equations. In a curve equation, (−r, θ) denotes (r, θ + π).
Sketch a polar curve from a complete tracing interval, its symmetry, the zeros and extrema of r, and sufficient intermediate values.
Tangents parallel to the initial line come from dy/dθ = 0 and perpendicular ones from dx/dθ = 0, each with the other derivative non-zero; if both vanish, take the limiting gradient.

Areas with polar coordinates

Polar area is ½∫r² dθ, with the radius squared.
Expand the square, use cos²θ = (1 + cos 2θ)/2, and take limits between zeros of r or at intersections.
Between two curves traced with non-negative r over the same interval, the area is ½∫(R² − r²) dθ with R ≥ r; split the integral where the outer boundary changes.

Differential equationsFurther Maths3 topics

First order equations and integrating factors

Linear first order: multiply by e^{∫P dx} and the left side becomes d(IF × y)/dx; on an interval where P and Q are continuous the initial-value problem has a unique solution.
For constants p > 0 and q, y = q/p + Ce^−px: q/p is the equilibrium and the transient tends to zero. For variable Q(x) a particular solution need not be constant.
A general solution is a family of curves, one for each value of the constant; a boundary condition selects one particular member.

Second order equations

For a linear constant-coefficient homogeneous equation, substituting e^mx gives am² + bm + c = 0, and the roots determine the form of the solution.
A root with negative real part gives decay and one with positive real part growth; a repeated root needs (A + Bx); a non-real pair p ± qi gives oscillation of frequency q inside the envelope e^px.
With a forcing term, the general solution is the complementary function plus a particular integral of the same functional type.
If the trial duplicates a complementary-function term, multiply it by a sufficient power of x.

Modelling with differential equations

SHM is ẍ = −ω²x, with period 2π/ω and amplitude determined by the initial conditions.
For y″ + by′ + cy = 0 with b ≥ 0 and c > 0, the sign of b² − 4c classifies the damping: negative gives oscillation inside a decaying envelope, zero critical damping, positive heavy damping.
A suitable linear coupled pair reduces to one second order equation by differentiating one equation and substituting the other; nonlinear systems need not reduce this way.

Further Pure 1Further Maths10 topics

The t-formulae

With t = tan(θ/2): sin θ = 2t/(1 + t²), cos θ = (1 − t²)/(1 + t²), tan θ = 2t/(1 − t²).
a cos x + b sin x = c becomes a quadratic in t. Solve it, then take x = 2 arctan t.
The substitution reaches no odd multiple of π, so check each one lying in the stated interval by hand.

Taylor series

Taylor about a: the coefficient of (x − a)^r is the rth derivative at a over r factorial, and a = 0 gives the Maclaurin case.
Expand about a point where the derivatives are exact and which is close to the target value; the remainder carries (x − a) to the power n + 1.
An infinite Taylor series represents f only where it converges to f; smoothness alone is not sufficient.

Limits and L'Hôpital's rule

0/0 determines nothing by itself: expand in series and compare the lowest surviving powers.
L'Hôpital's rule replaces f/g by f'/g' for a 0/0 or ∞/∞ form, given differentiability near the point, g' non-zero there, and a limit for f'/g'.
Products, differences and power forms must be rearranged into a quotient before the rule applies.
For k > 0: x^ke^−x → 0 as x → ∞, and x^kln x → 0 as x → 0⁺.

Leibniz's theorem and the Weierstrass substitution

Leibniz: the nth derivative of fg is the binomial-weighted sum of derivatives of the two factors.
t = tan(x/2) with dx = 2dt/(1 + t²) turns a rational trigonometric integrand into a rational function of t; transform the limits as well.

Series solutions of differential equations

Solve for the highest derivative, then differentiate and substitute repeatedly; each round yields the next Taylor coefficient, valid locally about the expansion point.
A given substitution turns the equation into a standard type. Transform the derivatives, solve, translate back, and list any solution the substitution excluded.

Conic sections

Parabola (at², 2at); ellipse (a cos t, b sin t); hyperbola (a sec t, b tan t); rectangular hyperbola (ct, c/t) with t ≠ 0.
Distance to focus = e × distance to directrix, with e < 1 an ellipse, e = 1 a parabola, e > 1 a hyperbola.
Foci sit at (±ae, 0) and directrices at x = ±a/e when the major axis is horizontal.
The hyperbola x²/a² − y²/b² = 1 has asymptotes y = ±(b/a)x.

Tangents, normals and loci of conics

Tangent to y² = 4ax at (at², 2at) is ty = x + at²; to xy = c² at (ct, c/t) it is x + t²y = 2ct.
A repeated root in the substituted quadratic means tangency, and a zero discriminant is how the conditions are derived.
For a locus, parametrise the moving point and eliminate the parameter; state every restriction, since the equation alone usually describes more points than the locus contains.

The vector product and the scalar triple product

a × b is perpendicular to both factors, with |a × b| = |a||b| sin θ, the parallelogram's area; for non-zero vectors a × b = 0 exactly when they are parallel.
a, b and a × b form a right-handed triple, and the product distributes over addition.
|a·(b × c)| is the parallelepiped's volume, the tetrahedron has a sixth of it, and zero means coplanar.
The shortest distance between two lines with non-parallel directions is |(a₂ − a₁)·(b₁ × b₂)|/|b₁ × b₂|; parallel lines are handled as a point-to-line distance.

Numerical methods for differential equations

The forward difference uses the step ahead; the central difference uses a step each side and, for a sufficiently smooth function and small h, has truncation error of order h² against order h.
Second order equations use (y_n+1 − 2y_n + y_n-1)/h², which needs two consecutive grid values; y and y′ at one point give only one, so the second is found from a starting approximation.
Simpson: h/3 with weights 1, 4, 2, …, 4, 1, and an even number of strips.
Mid-ordinate: h times the n centre heights. Where the second derivative keeps one sign across the interval, its error is opposite in sign to the trapezium rule's and, as h tends to zero, about half the size.

Inequalities and inequations

Collect on one side, factorise, and read a sign diagram; multiplying by an unknown sign loses intervals.
Square a modulus inequality when both sides are non-negative, otherwise split into cases and sketch to check.

Further Statistics 1Further Maths9 topics

Discrete random variables and expectation

E(X) = Σ x P(X = x) is the balance point, and Var(X) = E(X²) − μ² measures the scatter round it.
E(aX + b) = aE(X) + b while Var(aX + b) = a²Var(X). Shifting moves the centre; scaling enters the spread squared.
The median is the first value whose running total reaches a half, and a discrete uniform on 1 to n has mean (n + 1)/2 and variance (n² − 1)/12.

The Poisson distribution

Poisson counts events occurring singly, independently and at a constant average rate, with E(X) = Var(X) = λ.
Independent Poissons add and windows scale λ, and B(n, p) becomes Po(np) for large n and small p.

Geometric and negative binomial distributions

Geometric: P(X = x) = p(1 − p)^x-1, mean 1/p, variance (1 − p)/p².
Negative binomial for the rth success: the combination arranges the earlier successes, and the mean is r/p.

Hypothesis tests for Poisson and geometric models

Poisson tests fix hypotheses on λ, and you compare the tail probability of the observed count under H₀ with the level.
Discreteness drops the actual significance level below the nominal one, and geometric upper tails are (1 − p) to the power x − 1.

The Central Limit Theorem

For large n, with independent identically distributed observations of finite variance, the sample mean is approximately N(μ, σ²/n) and the total approximately N(nμ, nσ²), whatever the shape of the population.
The population distribution itself is unchanged by sample size, and the standard error σ/√n needs four times the data for half the spread.

Goodness-of-fit tests

χ² sums (O − E)²/E, so each squared gap is weighted down by how large its class was expected to be.
Degrees of freedom are classes minus 1, minus one more for each parameter estimated from the data, counted after pooling.
A discrete model gives a class its probability at a point; a continuous one gives it F(upper) − F(lower), with the outer classes run to infinity.

Contingency tables

Expected = row total × column total ÷ grand total, which is independence written as arithmetic.
Degrees of freedom are (rows − 1)(columns − 1), because the margins have already used up the rest.
On a two by two table, where one degree of freedom makes the continuous approximation weakest, OCR H245 requires 0.5 to be subtracted from each |O − E| before squaring, and AQA 7367 expects you to know when to do so.

Probability generating functions

G(t) = E(t^X) stores every probability as a coefficient, G(1) = 1 always, and the mean is G'(1).
Variance is G''(1) + G'(1) − [G'(1)]², and independent sums multiply their generating functions.

Type I and Type II errors, test size and power

Type I rejects a true H₀, with probability equal to the test's size; Type II misses a real change.
Power = 1 − P(Type II error), rising as the alternative moves away from H₀, and with n fixed size and power trade off.

Further Pure 2Further Maths13 topics

Groups and their axioms

A group needs four axioms: closure, associativity, an identity, and an inverse for every element.
The order of an element is the least positive power reaching the identity, a quantity some specifications call its period; the order of a group is its size.
A group generated by one element is cyclic, and the integers modulo n under addition always are.
Associativity is inherited from familiar arithmetic; for an operation given by a formula, expand both bracketings.

Subgroups, Lagrange's theorem and isomorphism

A subgroup needs the identity, closure and inverses; associativity is inherited from the parent group.
Lagrange: every subgroup's order divides the group's order, and so does every element's order.
Proper rules out the whole group; non-trivial rules out the identity alone.
Orders 1 to 7 hold 1, 1, 1, 2, 1, 2, 1 groups: a cyclic one at each order, plus the Klein group at 4 and the triangle at 6.

Reduction formulae

Integrate by parts once, rearrange into a recurrence, then apply it down to a base case that integrates directly.
∫₀^∞ xⁿe^−x dx = n! for each non-negative integer n, the boundary term vanishing by the standard limit x^ke^−x → 0.

Arc length and surface area

Arc length integrates the hypotenuse: √(1 + (dy/dx)²) dx, or the parametric and polar equivalents.
About the x-axis, S = 2π∫|y| ds, which becomes 2π∫y ds when the curve satisfies y ≥ 0; ds is the same element as in the arc-length integral.
Check every answer against a circle, a cone or a sphere before moving on.

Functions of two variables

A partial derivative differentiates with respect to one variable and holds the other constant, giving f_x, f_y and then f_xx, f_yy and f_xy, where f_xy means x first and then y.
If the second partial derivatives are continuous near the point, f_xy = f_yx.
Stationary points solve f_x = 0 and f_y = 0 together. With H = f_xx f_yy − (f_xy)²: negative is a saddle; positive with f_xx > 0 a minimum and with f_xx < 0 a maximum; H = 0 leaves the test inconclusive.
At a point where f is differentiable the tangent plane is z = f(a, b) + (x − a)f_x(a, b) + (y − b)f_y(a, b), horizontal at a stationary point.

Eigenvalues and eigenvectors

Eigenvectors satisfy Mv = λv with v non-zero; solve det(M − λI) = 0 for the eigenvalues, then solve (M − λI)v = 0 for each eigenspace.
Over C every square matrix has an eigenvalue; a real matrix need not have a real eigenvector, and a rotation through an angle that is not a multiple of π is the standard example.
Trace is the sum of the eigenvalues and determinant their product; a real symmetric matrix has perpendicular eigenvectors whenever the eigenvalues differ.

Diagonalisation and the Cayley-Hamilton theorem

If an n × n matrix has n independent eigenvectors, P from the eigenvectors and D from the eigenvalues give P⁻¹MP = D and Mⁿ = PDⁿP⁻¹; without a full eigenvector basis the matrix is not diagonalisable.
For a real symmetric matrix, an orthonormal set of eigenvectors makes P orthogonal, so P⁻¹ is the transpose.
Cayley-Hamilton applies to every square matrix and reduces high powers; it yields an inverse only when the determinant is non-zero.

Further loci and regions in the Argand diagram

For distinct a and b and k > 0, |z − a| = k|z − b| is a circle when k ≠ 1 and the perpendicular bisector when k = 1; for k = 0 it reduces to the single point z = a.
A constant argument of a quotient traces an arc through a and b, with those two points excluded and the sign of the angle choosing the arc.
Sketch every boundary before shading, and record which ones the region includes.

Transformations of the complex plane

Under w = z², separate u = x² − y² and v = 2xy, then eliminate to find the image curve.
A Möbius map w = (az + b)/(cz + d) needs ad − bc ≠ 0, and on the extended plane it sends generalised circles to generalised circles.
Invert to z in terms of w before substituting; under w = 1/z a line missing the origin maps to a circle through the origin on the extended plane, with w = 0 omitted from a finite Argand diagram.

The Euclidean algorithm and Bézout's identity

Euclid: divide, keep the remainder, repeat, and the last non-zero remainder is the highest common factor; the same repeated division, carried on the quotient, writes a number in any base.
Bézout: back substitution writes that factor as ax + by, and when it is 1 the coefficient x inverts a modulo b. With d = gcd(a, b) and one solution (x₀, y₀) of ax + by = c, all integer solutions are x = x₀ + (b/d)t, y = y₀ − (a/d)t for t ∈ Z.
A common divisor of b and c divides bx + cy; Euclid's lemma: if a divides rs and a is coprime to r then a divides s.
Fundamental theorem: an integer above 1 is a product of primes in one way only, up to order.

Modular arithmetic and Fermat's little theorem

Congruences add, subtract, multiply and take powers; reduce at every step to keep the numbers small.
Cancelling is only safe when the common factor is coprime to the modulus; a quadratic congruence to an odd prime modulus is soluble when its discriminant is a square to that modulus.
Fermat: for prime p and a not divisible by p, a to the power p − 1 is 1 modulo p, so exponents reduce mod p − 1. The second form, a to the p is a, holds for every base, and composites can pass it.
For a system, solve one congruence, substitute its general form into the next; for a prime power of a sum, the middle of the binomial expansion vanishes.

Combinatorics

Multiply choices made in sequence, add alternatives, and subtract from the total when 'at least one' appears; more objects than boxes puts two of them in one box.
Permutations order the selection and combinations do not, so they differ by exactly r factorial.
Repeated objects divide the count, n! over the factorials of the repeats; partitions into k parts follow S(n, k) = S(n − 1, k − 1) + kS(n − 1, k).
Together means a block, apart means total minus together, and repeats taken some at a time or a graph of forbidden pairs mean cases; a derangement leaves nothing in its own place.

Recurrence relations

Recurrences solve like differential equations: complementary function plus particular solution, constants fitted to the initial terms.
Second order relations use an auxiliary equation in m, and a repeated root needs the extra factor of n; the Fibonacci relation gives m squared = m + 1, whose positive root is the golden ratio.
Modelled situations that grow by a factor and change by a fixed amount each step give u sub n+1 = au sub n + b.
A factor mⁿ tends to zero when |m| < 1, alternates in sign when m < 0, and grows in magnitude when |m| > 1; among terms with non-zero coefficients a unique largest modulus usually decides the long-term behaviour, while equal dominant moduli, cancellation and truncation need separate analysis, and bounded is not the same as convergent.

Further Statistics 2Further Maths12 topics

Least squares regression and residuals

Least squares minimises the sum of the squared vertical residuals, giving b = S(xy)/S(xx), with the line through the mean point.
Coding by p = (x − h)/c and q = (y − k)/d scales the gradient by d/c and leaves the shifts to the intercept, so substitute the coding rules back to recover the line.
For a least-squares fit with an intercept the residuals sum to zero, their pattern tests the model, and RSS = S(yy) − S(xy)²/S(xx) measures what is left unexplained.

Continuous random variables: density and distribution functions

For a continuous variable, probability is area under the density: P(a < X ≤ b) is the integral of f from a to b, and P(X = c) = 0.
F is the integral of f from the lower end, climbing from 0 to 1; differentiating F gives f back, F(m) = 0.5 gives the median, and the distribution of a function of X comes from rewriting its event in terms of X.
A part discrete, part continuous variable carries positive probability at individual values: those probabilities and the area under the density total 1, and F jumps at each such value by that probability.
Where the specification includes it, the wait between events at a constant random rate λ is exponential, with F(x) = 1 − e^−λx and tail e^−λx for x ≥ 0, and the memoryless property gives P(X > s + t | X > s) = P(X > t).

Mean, variance and skewness of continuous variables

Replace sums with integrals: E(X) is the integral of xf(x), E(g(X)) the integral of g(x)f(x), and Var(X) = E(X²) − [E(X)]².
The mode is where f peaks, endpoints included, any percentile solves F(x) = p/100, and for a single-peaked density the order of the three averages indicates the skew.
An exponential wait has mean 1/λ, variance 1/λ² and median (ln 2)/λ, proved by parts once you know the exponential outruns the power.

The continuous uniform distribution

U(a, b) has density 1/(b − a) on the interval, and a distribution function in three branches: 0 below a, (x − a)/(b − a) on it, 1 above b, so probability is proportion of length.
Its mean is the midpoint (a + b)/2 and its variance is (b − a)²/12, a standard deviation of about 29% of the range.

Correlation coefficients: product moment and Spearman

The product moment coefficient r = S(xy)/√(S(xx)S(yy)) measures linear association only, and linear coding leaves its size unchanged.
Spearman's rs = 1 − 6Σd²/[n(n² − 1)] measures agreement of orderings and is exact without ties; tied values take the mean rank, and with ties the product moment correlation of the ranks is the exact coefficient.

Testing a correlation coefficient

Hypotheses are about the population coefficient ρ or ρs, tested against a critical value that depends on n, the tail and the level.
Critical values fall as n grows; the product moment test assumes a bivariate normal population, while the rank test assumes nothing about shape but still needs independent paired observations and tests for monotonic association.
A non-parametric test names no family of distributions for the population and works from ranks, dropping a condition at the cost of power when that condition would have held.

Combinations of normal random variables

For independent normals, aX ± bY is normal with mean aμx ± bμy and variance a²σx² + b²σy²; without independence the covariance term is required.
Under independence, variances add for a difference as well as a sum, and n independent copies give variance nσ² while n times one gives n²σ².

Estimators, standard error and confidence intervals

An estimator is unbiased when its expected value is the parameter, and among unbiased ones the smaller variance is preferred.
The standard error of an estimator is the standard deviation of its sampling distribution, σ/√n for the sample mean: a 95% interval is the sample mean ± 1.96 standard errors, and 95% of such intervals capture μ.

Comparing two normal means

The difference of two independent sample means is normal, with the two variance-over-n terms added under the square root.
With large samples the sample variances may replace the population ones, and an interval missing zero matches a significant two-tailed test.

Testing variances: chi-squared and the F-distribution

(n − 1)S²/σ² is chi-squared on n − 1 degrees of freedom, and the distribution is skewed, so a two-tailed test needs two different critical values.
The ratio of two sample variances is F on the two degrees of freedom, numerator first; the alternative hypothesis picks the numerator, and larger-over-smaller is the two-tailed procedure at half the level.

Confidence intervals and tests with the t-distribution

With σ estimated from the sample, use t on n − 1 degrees of freedom: heavier tails than the normal, so wider intervals.
Paired data becomes one sample of differences; independent samples with a common variance use the pooled s² on n₁ + n₂ − 2 degrees of freedom.
Paired or unpaired is decided by how the data were collected, not by the test: equal-length lists with a partner for each reading are paired, and samples of different sizes are not.

Non-parametric tests

A non-parametric test names no family of distributions for the population: it works from signs and ranks, and asks about a median or about two populations being the same one.
Sign test: the count above the claimed median is B(n, ½). Signed-rank: rank the sizes, total them by sign to T₊ and T₋, and reject when the relevant total is at or below the critical value.
Rank two independent samples together and take W from the smaller one; for large samples T is about N(n(n + 1)/4, n(n + 1)(2n + 1)/24) and W about N(m(m + n + 1)/2, mn(m + n + 1)/12), each with a continuity correction.

Further Mechanics 1Further Maths8 topics

Momentum and impulse

Impulse is force times time and equals the change in momentum, so a rebound needs an impulse equal to the mass times the sum of the two speeds.
In a collision the internal forces are equal and opposite, so when the external impulse is negligible the total momentum before equals the total momentum after.
A force that varies delivers I = ∫F dt, with Ft as the constant-force case of it; divide any impulse by the contact time to get the average force.
When a slack inextensible string becomes taut, the impulsive tension is equal and opposite at its two ends, so momentum along the string is conserved and the two particles leave with equal components along it.

Impulse and momentum as vectors

In vector form I = mv − mu, so the i components and the j components each obey the principle on their own.
Take magnitudes only after the vector is known. A change of direction at constant speed still needs an impulse.
A string jerks along its own length: resolve along it, where momentum is conserved and the two components become equal, and across it, where each particle keeps what it had.

Work, energy and power

Work is Fd cos θ, and the work-energy principle says the total work done by all forces equals the change in kinetic energy.
With no resistance, kinetic plus gravitational potential energy stays constant.
Power is P = Fv, so the driving force falls as speed rises, and maximum speed is where it has dropped to equal the resistance.
In vectors, kinetic energy is ½m v·v and constant acceleration gives v·v = u·u + 2a·s, which is the work-energy principle once both sides are multiplied by ½m.

Hooke's law and elastic strings

Hooke's law is T = λx/l, where x is the extension, l the natural length and λ the modulus in newtons.
A string pulls only and has zero tension when slack. A spring also pushes, with the compression in place of the extension.

Elastic potential energy

The energy stored is λx²/(2l), the area of the triangle under the Hooke's law line, so it grows with the square of the extension.
Add it to kinetic and gravitational potential energy, and set the total change equal to any work done against friction.

Direct impact and Newton's law of restitution

Newton's law of restitution says the separation speed is e times the approach speed, with 0 ≤ e ≤ 1.
Use it with conservation of momentum to get two equations in the two unknown velocities.
Kinetic energy is lost in every impact except e = 1; at e = 0 the spheres coalesce.

Successive impacts and impacts with a wall

Against a fixed surface only restitution applies: the rebound speed is e times the approach speed, and momentum is not conserved for the ball alone.
In a chain of impacts, carry signed velocities forward; a further collision happens exactly when the bodies are still approaching.

Oblique impact and impact with a smooth surface

A smooth surface leaves the parallel component untouched and multiplies the perpendicular component by −e.
The outgoing path therefore hugs the surface more closely than the incoming one whenever e < 1.
All the energy lost comes from the perpendicular component, which keeps only e² of its share.
For two smooth spheres the impulse acts along the line of centres, so resolve there and leave both perpendicular components alone.

Further Mechanics 2Further Maths10 topics

Angular speed and horizontal circular motion

Circular motion at constant speed still accelerates, towards the centre, with magnitude rω² or v²/r, as differentiating the position vector twice shows.
Some real force must supply that acceleration, so name it before writing an equation.
On a banked track the reaction alone suffices at the design speed given by tan θ = v²/rg.
With two strings from the same vertical line the geometry fixes the radius and both angles, and the lower string stays taut while rω² ≥ g tan α.

Motion in a vertical circle

Energy relates speed to height, since the tension does no work; the radial equation then gives the tension at any point.
A string or an inside track can act inwards only, so it needs v² ≥ gr at the top; a rigid rod or a wire can also push, so its limiting condition is v² ≥ 0 and passing through the top needs v > 0.
From the lowest point, u² ≥ 5gr completes the circle and u² ≤ 2gr oscillates; anything between leaves the circle above the horizontal.

Centre of mass of a discrete distribution

The centre of mass is the mass-weighted average of the positions, taken one coordinate at a time, and it follows from moments, so an object balances when supported there and hangs with it below any point of suspension.

Centres of mass of plane figures and frameworks

For a uniform lamina, weight each piece by its area at its own centre.
The Pearson Edexcel 9FM0 formulae booklet gives the centres of seven standard uniform bodies.
Anything removed goes in with a negative area at its own centre.
For a framework, weight each rod by its length at its own midpoint, so the wire and the lamina of the same shape generally differ.

Centres of mass by integration

Cut into strips: x_G is ∫xy dx over ∫y dx, but y_G is ∫½y² dx over ∫y dx, because each strip acts at its own halfway height.
For a solid of revolution use y² in place of y and take the centre on the axis by symmetry; for a non-uniform body put ρ inside both integrals.

Equilibrium, suspension, toppling and sliding

A couple is two equal and opposite forces on different lines, of moment Fd about any point, which is why the pivot for taking moments may be chosen to suit you.
A freely suspended body hangs with its centre of mass vertically below the point of suspension.
On a slope, sliding needs tan θ = μ and toppling needs tan θ = a/h, with a the base half-width and h the height of G.
Whichever of those two angles is smaller is the one that happens.

Newton's laws with a variable force

Use v dv/dx when the force depends on position and dv/dt when it depends on time; SUVAT is unavailable either way.
For gravitation, write GM as gR² so the inverse square force is mgR²/x², and integrate it for the work done.

Simple harmonic motion

Simple harmonic motion is the equation acceleration = −ω²x, with solutions a sin ωt or a cos ωt.
The period is 2π/ω whatever the amplitude.
Speed and displacement are linked by v² = ω²(a² − x²): fastest at the centre, at rest at the ends.

Oscillations on strings and springs

Measured from equilibrium the weight cancels, leaving acceleration = −(λ/ml)x: simple harmonic with ω² = λ/ml.
A spring stays simple harmonic throughout; a string goes slack above its natural length, so compare the amplitude with the equilibrium extension.

Further kinematics: acceleration as a function of x, t or v

Match the form of the acceleration to what it depends on: dv/dt for t or v, v dv/dx for x or v.
Separate, integrate, then apply the conditions at once.
A terminal speed is found by setting the acceleration to zero, not by taking a limit.

Decision Mathematics 1Further Maths11 topics

Algorithms, sorting and bin packing

An algorithm is a precise finite recipe, and its order says how the work grows with the size of the problem.
Count the operations on a list of n items, keep the dominant term and drop its multiplier: that is the order, written O(n^k).
Next fit, first fit, first fit decreasing and full bin packing are all quick and none is guaranteed optimal.
Always compare a packing with the lower bound of total size over bin size, rounded up.

Graphs: order, Eulerian paths and planarity

The orders always total twice the number of edges, so the number of odd nodes is always even.
For a connected graph, no odd nodes means Eulerian, exactly two means semi-Eulerian, and more than two means neither.
The planarity algorithm needs a Hamiltonian cycle: draw it as a circle and try to split the chords between inside and outside.
For a connected plane drawing, nodes − edges + regions = 2 with the region outside counted, so a simple planar graph holds at most 3V − 6 edges.

Minimum spanning trees: Prim and Kruskal

A spanning tree of n nodes has exactly n − 1 edges and no cycle; the minimum one has least total weight.
Prim grows outwards from a node and Kruskal works down the sorted edges rejecting cycles; both give the same minimum total, though the edges chosen can differ when the minimum spanning tree is not unique.
An adjacency matrix counts the edges joining each pair, so it is symmetric for an undirected graph and its row sums are the orders.

Shortest paths: Dijkstra and Floyd

Dijkstra requires non-negative edge weights, and makes permanent the smallest temporary label anywhere in the network rather than the cheapest edge at the current node.
Backtrack from the destination through matching labels, since the match alone only names an edge on some shortest route; Floyd instead does every pair at once, one intermediate node per iteration.

Route inspection

In a connected network, odd nodes force repetition, so pair them up and repeat a shortest path between each pair.
2n odd nodes have 1 × 3 × 5 × ... × (2n − 1) pairings, so four give three and six give fifteen.
The answer is the total weight of the network plus the cost of the cheapest pairing, and the repeated edges must be named.
Closing an arc changes the parity of both its ends, so a modified network needs its odd nodes and its pairings found again.

Further packing and the knapsack problem

A knapsack problem is an integer programme: a nought-or-one variable for each item, a profit to maximise and one mass constraint.
Loading by profit per unit mass is quick and can fall short, so treat the load it gives as a candidate and check it.
The table V(i, w), the best profit from the first i items under a limit of w, settles the answer, and running up its last column names the items.
In two dimensions pack by shelves of decreasing height and compare the length used with the total area divided by the width.

The travelling salesman problem

Any tour at all is an upper bound, and nearest neighbour finds one quickly, rarely the best one.
Doubling a minimum spanning tree also gives an upper bound, which short cuts then improve.
A lower bound comes from deleting a node, finding a minimum spanning tree on the rest, and adding back the two shortest edges from it.

Critical path analysis

The forward pass takes the largest incoming finish and the backward pass the smallest outgoing start.
An activity is critical when its earliest and latest starts agree; critical activities form one or more continuous paths from start to finish, each with total duration equal to the project duration.
Activity on node draws each activity as a box of six numbers and each dependency as an arrow; dummy activities are not used in activity-on-node networks.

Float, Gantt charts and scheduling

Total float is latest finish minus earliest start minus duration; independent float swaps the two event times over and is recorded as zero if negative.
Float is shared along a chain, so two activities on the same path cannot both use it all: that shared part is the interfering float, and total minus independent is what measures it.
The lower bound on workers is total work divided by project duration, rounded up; levelling shifts non-critical activities within their float to reach it.

Linear programming: formulation and graphical solution

The optimum of a linear program sits at a vertex of the feasible region, though not necessarily the furthest one from the origin.
A ≤ constraint gains a slack variable; a ≥ constraint loses a surplus variable and gains an artificial one.
The optimal corner survives while the objective's gradient stays between the gradients of the two constraints meeting there.
Branch and bound splits on a fractional variable and cuts off any branch whose relaxed optimum falls short of the best integer answer so far.

The Simplex algorithm

Choose the pivot column by the most negative entry in the objective row.
Choose the row by the smallest non-negative ratio of value to pivot-column entry, skipping negative and zero entries.
Stop when no negative entries remain in the objective row; ≥ constraints need the two-stage or big-M method to get started.

Decision Mathematics 2Further Maths9 topics

Transportation problems and the north-west corner method

Balance the problem with a zero-cost dummy first, then fill from the north-west corner without looking at any cost.
A solution to an m by n problem uses m + n − 1 cells; fewer means degeneracy, fixed by recording a zero allocation.

The stepping-stone method

Shadow costs satisfy R + K = cost for every cell in use, and the improvement index of an unused cell is cost − R − K.
The most negative index enters; θ is the smallest minus-cell allocation, that cell exits, and the cost changes by θ times the (negative) index.
As a linear program, minimise Σ c x subject to one equation per source and one per destination.

Allocation and the Hungarian algorithm

Reducing by rows then columns removes the same amount from every complete allocation, so the cheapest one is unchanged.
If the minimum covering lines number fewer than the matrix size, augment using the smallest uncovered entry and test again.

Flows in networks: cuts and capacity

A cut's capacity is the total of the arcs crossing from the source side to the sink side only.
Every flow is bounded by every cut, so a small cut is a proof of an upper bound; restricted vertices are split into two joined by one arc.
An arc with a lower capacity has to carry its floor, so a cut is valued at the upper capacities forward less the floors crossing back.

Maximum flow and the labelling procedure

Label spare capacity forwards and existing flow backwards; an augmenting path carries the smallest of those numbers along it.
The maximum flow equals the minimum cut, so a flow is proved maximal by exhibiting a cut of the same capacity.
The minimum cut separates the vertices still reachable from the source from those that are not.
Where arcs carry floors, start from a feasible flow and label backwards with the flow less the lower capacity.

Dynamic programming and Bellman's principle

Bellman's principle says any part of an optimal path is optimal, which licenses working backwards from the end.
Tabulate stage against state, quoting values already found.
For minimax or maximin replace the addition with a maximum or a minimum along the route.

Game theory: play safe and stable solutions

The matrix is from the row player's view, so the row player maximises the row minima and the column player minimises the column maxima.
The game has a pure-strategy saddle point exactly when maximin equals minimax, and that common number is the value; when they differ, the equilibrium is a mixed one.
Delete any strictly dominated row or column before doing anything else.

Mixed strategies in game theory

Plot the expected pay-off against each opposing choice as a line in p; the optimum is the highest point of the lower boundary, which is a crossing or an end.
Equate the pair meeting there for p and the value, test p = 0 and p = 1 too, and check against the other player's mix; the method covers 2 × n and n × 2 games, and larger ones are formulated as linear programmes.

Decision trees, expected monetary value and utility

Chance nodes take the probability-weighted average and decision nodes retain the greatest value under the criterion in use, worked back to the first decision.
Expected monetary value is an average over repetitions, so for a one-off decision with large stakes utility may favour the safer option.

Each topic links to its full lesson. See also the equation index, key definitions and the revision checklist.