Sixth Term Examination Paper (STEP) Problem-Solving, Proof and Mathematical Reasoning Syllabus

Problem-Solving, Proof and Mathematical Reasoning syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Problem-Solving, Proof and Mathematical Reasoning in Sixth Term Examination Paper (STEP), not a summary of it.

1. 1

   Methods of Proof

   5 topics

   • Direct proof and proof by deduction
   • Proof by contradiction and proof of irrationality
   • Proof by exhaustion and counterexamples
   • Proof by mathematical induction
     • Strong induction
     • Induction for inequalities and matrices
   • Logical implication, converse and necessary/sufficient conditions
2. 2

   Inequalities and Estimation

   5 topics

   • Manipulating and proving algebraic inequalities
   • The AM-GM inequality and its applications
   • Cauchy-Schwarz and related inequalities
   • Bounding sums and integrals for estimation
   • Optimisation by inequality and by calculus
3. 3

   Number and Discrete Reasoning

   5 topics

   • Divisibility, factors and the Euclidean algorithm
   • Modular arithmetic and congruences
   • Properties of primes and the fundamental theorem of arithmetic
   • Combinatorial identities and the pigeonhole principle
   • Functional equations and substitution strategies
4. 4

   Strategy for STEP Problems

   5 topics

   • Reading long multi-part questions and using earlier parts
   • Generalising, specialising and exploiting symmetry
   • Translating between algebraic, geometric and graphical views
   • Constructing rigorous, fully justified written solutions
   • Checking results: limiting cases, dimensions and sanity tests

Problem-Solving, Proof and Mathematical Reasoning flashcards for Sixth Term Examination Paper (STEP)

22 of 50 cards from the Problem-Solving, Proof and Mathematical Reasoning deck — real questions with worked answers.

1. What is the basic structure of a direct proof (proof by deduction) of an implication $P \Rightarrow Q$?

   Assume the hypothesis $P$ is true, then proceed through a chain of valid logical/algebraic deductions, each following from previous statements or known axioms, until you arrive at the conclusion $Q$. No gaps may be left.

2. In a direct proof, how do you represent an arbitrary even integer and an arbitrary odd integer?

   An even integer is written as $2k$ and an odd integer as $2k+1$ (or $2k-1$), where $k \in \mathbb{Z}$. Using a general $k$ ensures the result holds for all such integers, not a special case.

3. What is the logical principle underlying proof by contradiction?

   To prove statement $P$, assume its negation $\neg P$ is true. Derive a logical contradiction (a statement that is both true and false). Since the assumption leads to absurdity, $\neg P$ must be false, so $P$ is true.

4. Outline the proof by contradiction that $\sqrt{2}$ is irrational.

   Assume $\sqrt{2}=\frac{p}{q}$ in lowest terms ($\gcd(p,q)=1$). Then $p^{2}=2q^{2}$, so $p^{2}$ is even, hence $p$ is even, say $p=2m$. Then $4m^{2}=2q^{2}$, so $q^{2}=2m^{2}$, making $q$ even too. This contradicts $\gcd(p,q)=1$, so $\sqrt{2}$ is irrational.

5. What is proof by exhaustion, and when is it valid?

   Proof by exhaustion splits the statement into a finite number of cases that together cover every possibility, then verifies the claim in each case. It is valid only when the cases are exhaustive (cover all possibilities) and finite in number.

6. What is a counterexample and what does it establish?

   A counterexample is a single specific instance satisfying the hypothesis of a universal statement but violating its conclusion. One counterexample is sufficient to prove that a universal ('for all') statement is false; e.g. $n^{2}-n+41$ is prime fails at $n=41$.

7. State the principle of (weak) mathematical induction.

   To prove $P(n)$ for all integers $n \geq n_{0}$: (1) Base case — show $P(n_{0})$ is true. (2) Inductive step — assume $P(k)$ true for some $k \geq n_{0}$ and deduce $P(k+1)$. Then $P(n)$ holds for all $n \geq n_{0}$.

8. How does strong (complete) induction differ from weak induction?

   In strong induction the inductive hypothesis assumes $P(j)$ holds for all $j$ with $n_{0} \leq j \leq k$ (not just $j=k$), and from this you prove $P(k+1)$. It is useful when $P(k+1)$ depends on several earlier values, e.g. proving every integer $\geq 2$ has a prime factorisation.

9. Prove by induction the formula $\sum_{r=1}^{n} r = \frac{n(n+1)}{2}$ — what are the two steps?

   Base: $n=1$ gives $1=\frac{1\cdot 2}{2}=1$. Step: assume $\sum_{r=1}^{k} r=\frac{k(k+1)}{2}$; then $\sum_{r=1}^{k+1} r=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}$, which is the formula with $n=k+1$. Hence true for all $n\geq 1$.

10. What is the difference between an implication, its converse, and its contrapositive?

    For $P \Rightarrow Q$: the converse is $Q \Rightarrow P$; the contrapositive is $\neg Q \Rightarrow \neg P$. The contrapositive is logically equivalent to the original; the converse is not (it may be true or false independently).

11. Define necessary condition and sufficient condition for a statement $P$.

    $Q$ is a necessary condition for $P$ if $P \Rightarrow Q$ (P cannot hold without Q). $Q$ is a sufficient condition for $P$ if $Q \Rightarrow P$ (Q guarantees P). If both hold ($P \Leftrightarrow Q$), $Q$ is necessary and sufficient.

12. What must you prove to establish an 'if and only if' ($\Leftrightarrow$) statement?

    You must prove both implications: the forward direction $P \Rightarrow Q$ and the reverse direction $Q \Rightarrow P$. Equivalently, prove $P\Rightarrow Q$ and its contrapositive, or show a chain of equivalences each of which is reversible.

13. State the trivial inequality and explain why it is the foundation for proving many algebraic inequalities.

    For any real number $x$, $x^{2} \geq 0$, with equality iff $x=0$. Many inequalities are proved by rearranging into a sum of squares (e.g. $a^{2}+b^{2}\geq 2ab$ comes from $(a-b)^{2}\geq 0$).

14. Prove that $a^{2}+b^{2} \geq 2ab$ for all real $a,b$, and state when equality holds.

    Since $(a-b)^{2}\geq 0$, expanding gives $a^{2}-2ab+b^{2}\geq 0$, i.e. $a^{2}+b^{2}\geq 2ab$. Equality holds iff $a=b$.

15. When manipulating an inequality, what operation reverses the inequality sign?

    Multiplying or dividing both sides by a negative number reverses the sign; also taking reciprocals of both sides reverses it when both sides have the same (positive) sign. Adding/subtracting any quantity, and multiplying by a positive quantity, preserve the direction.

16. State the AM-GM inequality for two non-negative reals and for $n$ non-negative reals.

    For $a,b\geq 0$: $\frac{a+b}{2}\geq\sqrt{ab}$. For $a_{1},\dots,a_{n}\geq 0$: $\frac{a_{1}+\cdots+a_{n}}{n}\geq\sqrt[n]{a_{1}\cdots a_{n}}$. Equality holds iff all the $a_{i}$ are equal.

17. Use AM-GM to find the minimum of $x+\frac{1}{x}$ for $x>0$.

    By AM-GM, $x+\frac{1}{x}\geq 2\sqrt{x\cdot\frac{1}{x}}=2$, with equality iff $x=\frac{1}{x}$, i.e. $x=1$. So the minimum value is $2$, attained at $x=1$.

18. State the Cauchy-Schwarz inequality for real sequences.

    For real numbers $a_{1},\dots,a_{n}$ and $b_{1},\dots,b_{n}$: $\left(\sum_{i=1}^{n} a_{i}b_{i}\right)^{2}\leq\left(\sum_{i=1}^{n} a_{i}^{2}\right)\left(\sum_{i=1}^{n} b_{i}^{2}\right)$, with equality iff the vectors $(a_i)$ and $(b_i)$ are proportional.

19. State the integral (Schwarz) form of the Cauchy-Schwarz inequality.

    $\left(\int_{a}^{b} f(x)g(x)\,dx\right)^{2}\leq\left(\int_{a}^{b} f(x)^{2}\,dx\right)\left(\int_{a}^{b} g(x)^{2}\,dx\right)$, with equality iff $f$ and $g$ are proportional on $[a,b]$.

20. State the triangle inequality for real numbers and its reverse form.

    $|a+b|\leq|a|+|b|$ for all real $a,b$. The reverse triangle inequality is $\big||a|-|b|\big|\leq|a-b|$.

21. How can you bound a sum $\sum_{r=1}^{n} f(r)$ above and below using an integral when $f$ is decreasing?

    For a decreasing positive function $f$: $\int_{1}^{n+1} f(x)\,dx \leq \sum_{r=1}^{n} f(r) \leq f(1)+\int_{1}^{n} f(x)\,dx$. Comparing each term $f(r)$ to areas of rectangles relative to the curve gives the bounds (sign of inequalities reverses if $f$ is increasing).

22. What technique uses rectangles under/over a curve to estimate an integral, and how does monotonicity matter?

    The integral test / rectangle comparison: for a monotonic $f$, the area under the curve lies between the left-endpoint and right-endpoint rectangle sums. If $f$ is decreasing, right sums underestimate and left sums overestimate $\int f$; if increasing, the roles swap.

See more Problem-Solving, Proof and Mathematical Reasoning flashcards →

Planning Problem-Solving, Proof and Mathematical Reasoning for Sixth Term Examination Paper (STEP)

Problem-Solving, Proof and Mathematical Reasoning (Sixth Term Examination Paper (STEP)) FAQ