Hard A-Level Proof by deduction and exhaustion Questions

Challenging, exam-style A-Level Proof by deduction and exhaustion questions with worked solutions. Stretch yourself on the hardest divisibility, factorising, modular reasoning, consecutive integers problems.

divisibilityfactorisingmodular reasoningconsecutive integerscubesproof by exhaustion
A-Level34 questionsStep-by-step solutions
Question 1
8 markschallenging
Prove that (a2+b2+c2)(x2+y2+z2)≥(ax+by+cz)2(a^2+b^2+c^2)(x^2+y^2+z^2)\ge (ax+by+cz)^2 for all real numbers, and state when equality holds.
Show worked solution

Worked solution

  1. State the target

    (a2+b2+c2)(x2+y2+z2)≥(ax+by+cz)2(a^2+b^2+c^2)(x^2+y^2+z^2)\ge (ax+by+cz)^2

    This is the Cauchy–Schwarz inequality in three dimensions. We prove it via an exact identity.

  2. Expand the left product

    ∑a2∑x2=a2x2+a2y2+a2z2+b2x2+b2y2+b2z2+c2x2+c2y2+c2z2\textstyle\sum a^2\sum x^2=a^2x^2+a^2y^2+a^2z^2+b^2x^2+b^2y^2+b^2z^2+c^2x^2+c^2y^2+c^2z^2

    We multiply out the two brackets, giving nine terms.

  3. Expand the right square

    (ax+by+cz)2=a2x2+b2y2+c2z2+2(axby+bycz+axcz)(ax+by+cz)^2=a^2x^2+b^2y^2+c^2z^2+2(axby+bycz+axcz)

    We square the linear combination, obtaining three squared terms and three cross terms.

  4. Form the difference

    D=(a2+b2+c2)(x2+y2+z2)−(ax+by+cz)2D=(a^2+b^2+c^2)(x^2+y^2+z^2)-(ax+by+cz)^2

    We compute the left minus the right and hope to recognise a sum of squares.

  5. Cancel the matching squares

    a2x2, b2y2, c2z2 cancela^2x^2,\ b^2y^2,\ c^2z^2\ \text{cancel}

    These three terms appear on both sides and disappear in the difference.

  6. Write the surviving terms

    D=a2y2+b2x2+b2z2+c2y2+a2z2+c2x2−2(abxy+bcyz+acxz)D=a^2y^2+b^2x^2+b^2z^2+c^2y^2+a^2z^2+c^2x^2-2(abxy+bcyz+acxz)

    Six mixed square terms remain, minus twice the three cross terms.

  7. Group into three pairs

    (a2y2−2abxy+b2x2)+(b2z2−2bcyz+c2y2)+(a2z2−2acxz+c2x2)(a^2y^2-2abxy+b^2x^2)+(b^2z^2-2bcyz+c^2y^2)+(a^2z^2-2acxz+c^2x^2)

    Each pair of square terms is matched with a cross term to complete a square.

  8. Write as three squares

    D=(ay−bx)2+(bz−cy)2+(az−cx)2D=(ay-bx)^2+(bz-cy)^2+(az-cx)^2

    This is Lagrange's identity: the difference is exactly a sum of three squares.

  9. Use non-negativity

    (ay−bx)2,(bz−cy)2,(az−cx)2≥0(ay-bx)^2,(bz-cy)^2,(az-cx)^2\ge 0

    Each square is non-negative, so their sum is non-negative.

  10. Deduce D≥0D\ge0

    D≥0D\ge 0

    Since D is a sum of squares, it is at least 0.

  11. Rearrange

    (a2+b2+c2)(x2+y2+z2)≥(ax+by+cz)2(a^2+b^2+c^2)(x^2+y^2+z^2)\ge (ax+by+cz)^2

    D\ge0 is exactly the required inequality.

  12. State equality condition

    ay=bx, bz=cy, az=cxay=bx,\ bz=cy,\ az=cx

    Equality needs all three squares to vanish, which means (a,b,c) and (x,y,z) are proportional.

  13. Interpret geometrically

    equality  ⟺  (a,b,c)∥(x,y,z)\text{equality}\iff (a,b,c)\parallel(x,y,z)

    Cauchy–Schwarz becomes an equality precisely when the two vectors are parallel.

  14. Verify an example

    (1,2,2)⋅(2,1,2): 9⋅9=81≥82=64(1,2,2)\cdot(2,1,2):\ 9\cdot9=81\ge 8^2=64

    Checking a=(1,2,2), x=(2,1,2): left is 9\times9=81, right is (2+2+4)^2=64, and 81\ge64.

  15. Conclude

    (a2+b2+c2)(x2+y2+z2)≥(ax+by+cz)2(a^2+b^2+c^2)(x^2+y^2+z^2)\ge (ax+by+cz)^2

    Therefore the inequality holds for all real numbers, with equality iff the vectors are proportional.

Answer
D=(ay−bx)2+(bz−cy)2+(az−cx)2≥0D=(ay-bx)^2+(bz-cy)^2+(az-cx)^2\ge 0
Question 2
7 markschallenging
Prove that a2b+b2c+c2a≥a+b+c\dfrac{a^2}{b}+\dfrac{b^2}{c}+\dfrac{c^2}{a}\ge a+b+c for all positive real numbers a,b,ca,b,c.
Show worked solution

Worked solution

  1. State the target

    a2b+b2c+c2a≥a+b+c\frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{a}\ge a+b+c

    We prove this for positive a, b, c. Positivity keeps every denominator positive.

  2. Set up the key lemma

    claim: x2y≥2x−y for x,y>0\text{claim: } \frac{x^2}{y}\ge 2x-y\ \text{for }x,y>0

    We prove a single-fraction bound and then sum it cyclically.

  3. Rearrange the lemma

    x2y−2x+y≥0\frac{x^2}{y}-2x+y\ge 0

    We move everything to one side to look for a square.

  4. Multiply by y>0y>0

    x2−2xy+y2≥0x^2-2xy+y^2\ge 0

    Multiplying by the positive number y clears the fraction without changing the inequality direction.

  5. Recognise the square

    (x−y)2≥0(x-y)^2\ge 0

    The left-hand side is a perfect square, hence non-negative.

  6. Conclude the lemma

    x2y≥2x−y\frac{x^2}{y}\ge 2x-y

    Dividing back by y (positive) gives the lemma, with equality when x=y.

  7. Apply to the first fraction

    a2b≥2a−b\frac{a^2}{b}\ge 2a-b

    Using the lemma with x=a, y=b.

  8. Apply to the second fraction

    b2c≥2b−c\frac{b^2}{c}\ge 2b-c

    Using the lemma with x=b, y=c.

  9. Apply to the third fraction

    c2a≥2c−a\frac{c^2}{a}\ge 2c-a

    Using the lemma with x=c, y=a.

  10. Add the three inequalities

    a2b+b2c+c2a≥(2a−b)+(2b−c)+(2c−a)\frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{a}\ge (2a-b)+(2b-c)+(2c-a)

    We add the left sides and the right sides separately.

  11. Simplify the right side

    (2a−b)+(2b−c)+(2c−a)=a+b+c(2a-b)+(2b-c)+(2c-a)=a+b+c

    Collecting terms: 2a-a=a, 2b-b=b, 2c-c=c.

  12. Combine

    a2b+b2c+c2a≥a+b+c\frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{a}\ge a+b+c

    The sum of the lemma applications gives exactly the required bound.

  13. State equality condition

    equality  ⟺  a=b=c\text{equality}\iff a=b=c

    Each lemma is an equality only when its two variables are equal, forcing a=b=c.

  14. Verify an example

    a=2,b=1,c=1: 4+1+0.5=5.5 ≥ 4a=2,b=1,c=1:\ 4+1+0.5=5.5\ \ge\ 4

    Checking a=2, b=1, c=1: the left side is 5.5 and the right is 4, consistent with the inequality.

  15. Conclude

    a2b+b2c+c2a≥a+b+c\frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{a}\ge a+b+c

    Therefore the inequality holds for all positive real a, b, c.

Answer
x2y≥2x−y⇒∑a2b≥∑(2a−b)=a+b+c\frac{x^2}{y}\ge 2x-y\Rightarrow \sum\frac{a^2}{b}\ge \sum(2a-b)=a+b+c
Question 3
7 markschallenging
Prove the identity (a2+b2)(c2+d2)=(ac+bd)2+(ad−bc)2(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2, and hence show that the product of two numbers, each of which is a sum of two squares, is itself a sum of two squares.
Show worked solution

Worked solution

  1. State the plan

    expand both sides and compare\text{expand both sides and compare}

    We prove the identity by expanding the left and right and showing they match.

  2. Expand the left side

    (a2+b2)(c2+d2)=a2c2+a2d2+b2c2+b2d2(a^2+b^2)(c^2+d^2)=a^2c^2+a^2d^2+b^2c^2+b^2d^2

    We multiply each term of the first bracket by each term of the second.

  3. Expand (ac+bd)2(ac+bd)^2

    (ac+bd)2=a2c2+2abcd+b2d2(ac+bd)^2=a^2c^2+2abcd+b^2d^2

    We square the first bracket on the right.

  4. Expand (ad−bc)2(ad-bc)^2

    (ad−bc)2=a2d2−2abcd+b2c2(ad-bc)^2=a^2d^2-2abcd+b^2c^2

    We square the second bracket on the right.

  5. Add the two right-hand squares

    (ac+bd)2+(ad−bc)2=a2c2+b2d2+a2d2+b2c2(ac+bd)^2+(ad-bc)^2=a^2c^2+b^2d^2+a^2d^2+b^2c^2

    The +2abcd and -2abcd cancel when we add.

  6. Compare the two sides

    a2c2+a2d2+b2c2+b2d2=a2c2+b2d2+a2d2+b2c2a^2c^2+a^2d^2+b^2c^2+b^2d^2=a^2c^2+b^2d^2+a^2d^2+b^2c^2

    The expanded left and right sides contain exactly the same four terms.

  7. State the identity

    (a2+b2)(c2+d2)=(ac+bd)2+(ad−bc)2(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2

    The two sides are equal, so the identity (Brahmagupta–Fibonacci) is proved.

  8. Set up the deduction

    let M=a2+b2, N=c2+d2\text{let }M=a^2+b^2,\ N=c^2+d^2

    Suppose M and N are each a sum of two squares, with integers a, b, c, d.

  9. Apply the identity

    MN=(ac+bd)2+(ad−bc)2MN=(ac+bd)^2+(ad-bc)^2

    By the identity, the product MN is written as a sum of two squares.

  10. Check the parts are integers

    ac+bd, ad−bc∈Zac+bd,\ ad-bc\in\mathbb{Z}

    Both ac+bd and ad-bc are integers, so MN is genuinely a sum of two integer squares.

  11. Verify an example

    5×13=65=(22+12)(32+22)5\times13=65=(2^2+1^2)(3^2+2^2)

    Take 5=2^2+1^2 and 13=3^2+2^2, so a=2,b=1,c=3,d=2.

  12. Compute the two squares

    (ac+bd)2+(ad−bc)2=82+12=64+1=65(ac+bd)^2+(ad-bc)^2=8^2+1^2=64+1=65

    Here ac+bd=6+2=8 and ad-bc=4-3=1, giving 65=8^2+1^2, as claimed.

  13. State the deduction

    sum of two squares×sum of two squares=sum of two squares\text{sum of two squares}\times\text{sum of two squares}=\text{sum of two squares}

    The identity shows this closure property directly.

  14. Verify a second example

    2×13=26=(12+12)(22+32)=52+122\times13=26=(1^2+1^2)(2^2+3^2)=5^2+1^2

    Take 2=1^2+1^2 and 13=2^2+3^2; then ac+bd=2+3=5 and ad-bc=3-2=1, giving 26=5^2+1^2, another sum of two squares.

  15. Conclude

    MN is a sum of two squaresMN\ \text{is a sum of two squares}

    Therefore the product of two sums of two squares is itself a sum of two squares.

Answer
(a2+b2)(c2+d2)=(ac+bd)2+(ad−bc)2(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2
Question 4
7 markschallenging
Prove that n7−nn^7-n is divisible by 4242 for every integer nn.
Show worked solution

Worked solution

  1. Write the expression

    n7−nn^7-n

    We must show 42 divides this for every integer n. Note 42=2\times3\times7.

  2. Factor out nn

    =n(n6−1)=n(n^6-1)

    n is common to both terms.

  3. Factor the difference of squares

    =n(n3−1)(n3+1)=n(n^3-1)(n^3+1)

    n^6-1 is a difference of squares: (n^3)^2-1=(n^3-1)(n^3+1).

  4. Factor the cubes

    =n(n−1)(n2+n+1)(n+1)(n2−n+1)=n(n-1)(n^2+n+1)(n+1)(n^2-n+1)

    Using a^3-1=(a-1)(a^2+a+1) and a^3+1=(a+1)(a^2-a+1).

  5. Identify consecutive integers

    (n−1) n (n+1) appear as factors(n-1)\,n\,(n+1)\ \text{appear as factors}

    The three consecutive integers n-1, n, n+1 are all factors, handling divisibility by 2 and 3.

  6. Divisibility by 2

    2∣(n−1)n(n+1)2\mid (n-1)n(n+1)

    Three consecutive integers include an even number.

  7. Divisibility by 3

    3∣(n−1)n(n+1)3\mid (n-1)n(n+1)

    Three consecutive integers include a multiple of 3.

  8. Set up divisibility by 7

    consider n mod 7\text{consider }n\ \mathrm{mod}\ 7

    For 7 we check the seven possible remainders of n on division by 7.

  9. Cases where 7 divides a linear factor

    n≡0,1,6⇒7∣n, n−1, n+1n\equiv0,1,6\Rightarrow 7\mid n,\ n-1,\ n+1

    If n\equiv0,1 or 6 mod 7, then n, n-1 or n+1 is a multiple of 7.

  10. Case n≡2n\equiv2 or 55

    n≡2,5⇒n2+n+1 or n2−n+1≡0 (mod 7)n\equiv2,5\Rightarrow n^2+n+1\ \text{or}\ n^2-n+1\equiv0\ (\mathrm{mod}\ 7)

    For n\equiv2: n^2-n+1=3-... check 4-2+1=3, n^2+n+1=7\equiv0; and n\equiv5 similarly gives a factor of 7.

  11. Case n≡3n\equiv3 or 44

    n≡3,4⇒n2−n+1 or n2+n+1≡0 (mod 7)n\equiv3,4\Rightarrow n^2-n+1\ \text{or}\ n^2+n+1\equiv0\ (\mathrm{mod}\ 7)

    For n\equiv3: 9-3+1=7\equiv0; for n\equiv4: 16+4+1=21\equiv0. So one quadratic factor is divisible by 7.

  12. Conclude divisibility by 7

    7∣n7−n in all cases7\mid n^7-n\ \text{in all cases}

    Every residue class mod 7 makes one of the factors a multiple of 7 (this is Fermat's little theorem in action).

  13. Combine the primes

    2,3,7 pairwise coprime, each divides n7−n2,3,7\ \text{pairwise coprime, each divides }n^7-n

    Since 2, 3 and 7 are distinct primes each dividing the expression, their product divides it.

  14. Verify with an example

    n=2: 27−2=126=42×3n=2:\ 2^7-2=126=42\times3

    Checking n=2: 128-2=126=42\times3, divisible by 42, supporting the general argument.

  15. Conclude

    42∣n7−n42\mid n^7-n

    Therefore n^7-n is divisible by 42 for every integer n.

Answer
42∣n(n−1)(n+1)(n2+n+1)(n2−n+1)42\mid n(n-1)(n+1)(n^2+n+1)(n^2-n+1)
Question 5
7 markschallenging
Prove that a4+b4+c4≥abc(a+b+c)a^4+b^4+c^4\ge abc(a+b+c) for all real numbers a,b,ca,b,c.
Show worked solution

Worked solution

  1. State the target

    a4+b4+c4≥abc(a+b+c)a^4+b^4+c^4\ge abc(a+b+c)

    We prove this for all real a, b, c by building a chain of two known inequalities.

  2. Expand the right side

    abc(a+b+c)=a2bc+ab2c+abc2abc(a+b+c)=a^2bc+ab^2c+abc^2

    We multiply out so we can see what we must dominate.

  3. Recall a lemma

    x2+y2≥2xy for all real x,yx^2+y^2\ge 2xy\ \text{for all real }x,y

    This follows from (x-y)^2\ge0 and will be applied to squared variables.

  4. Apply to a2,b2a^2,b^2

    a4+b4≥2a2b2a^4+b^4\ge 2a^2b^2

    Using the lemma with x=a^2, y=b^2.

  5. Apply to b2,c2b^2,c^2

    b4+c4≥2b2c2b^4+c^4\ge 2b^2c^2

    Using the lemma with x=b^2, y=c^2.

  6. Apply to c2,a2c^2,a^2

    c4+a4≥2c2a2c^4+a^4\ge 2c^2a^2

    Using the lemma with x=c^2, y=a^2.

  7. Add the three

    2(a4+b4+c4)≥2(a2b2+b2c2+c2a2)2(a^4+b^4+c^4)\ge 2(a^2b^2+b^2c^2+c^2a^2)

    Adding the three inequalities; each of a^4,b^4,c^4 appears twice on the left.

  8. Divide by 2

    a4+b4+c4≥a2b2+b2c2+c2a2a^4+b^4+c^4\ge a^2b^2+b^2c^2+c^2a^2

    This is the first link in our chain.

  9. Recall a second inequality

    X2+Y2+Z2≥XY+YZ+ZXX^2+Y^2+Z^2\ge XY+YZ+ZX

    This standard result holds for all real X, Y, Z (proved via sums of squares).

  10. Substitute X=ab,Y=bc,Z=caX=ab,Y=bc,Z=ca

    (ab)2+(bc)2+(ca)2≥(ab)(bc)+(bc)(ca)+(ca)(ab)(ab)^2+(bc)^2+(ca)^2\ge (ab)(bc)+(bc)(ca)+(ca)(ab)

    We apply the second inequality to the products of pairs.

  11. Simplify the right side

    a2b2+b2c2+c2a2≥ab2c+bc2a+a2bca^2b^2+b^2c^2+c^2a^2\ge ab^2c+bc^2a+a^2bc

    Each product simplifies, e.g. (ab)(bc)=ab^2c.

  12. Recognise the target terms

    ab2c+bc2a+a2bc=abc(a+b+c)ab^2c+bc^2a+a^2bc=abc(a+b+c)

    Factoring out abc from the right side gives exactly abc(a+b+c).

  13. Chain the two inequalities

    a4+b4+c4≥a2b2+b2c2+c2a2≥abc(a+b+c)a^4+b^4+c^4\ge a^2b^2+b^2c^2+c^2a^2\ge abc(a+b+c)

    Linking the two results gives the full inequality.

  14. State equality condition

    equality  ⟺  a=b=c\text{equality}\iff a=b=c

    Both inequalities become equalities only when a=b=c.

  15. Conclude

    a4+b4+c4≥abc(a+b+c)a^4+b^4+c^4\ge abc(a+b+c)

    Therefore the inequality holds for all real a, b, c.

Answer
a4+b4+c4≥a2b2+b2c2+c2a2≥abc(a+b+c)a^4+b^4+c^4\ge a^2b^2+b^2c^2+c^2a^2\ge abc(a+b+c)

Unlock 29 more Proof by deduction and exhaustion questions

Create a free account to work through every A-Level Proof by deduction and exhaustion question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Proof by deduction and exhaustion practice

Practice QuestionsWorked Solutions

Related Pure Maths topics

Areas and further applicationsMathematical argument and notationArithmetic sequences and seriesBinomial expansion (rational powers)Binomial expansionCircles