krit.club logo

Number and Algebra - Methods of proof

Grade 11IB_AA

Review the key concepts, formulae, and examples before starting your quiz.

🔑Concepts

•

A direct proof uses a sequence of logical statements to show that a theorem is true. It often uses definitions of even numbers (2n2n) and odd numbers (2n+12n+1), where n∈Zn \in \mathbb{Z}.

•

Proof by contradiction involves assuming the negation of the statement is true and showing that this leads to an impossibility or a logical inconsistency.

•

A counter-example is a single specific case that shows a general statement is false. If a statement claims to be true for all xx, finding one xx where it fails disproves the entire statement.

•

Proof by deduction uses known facts, identities, and algebraic manipulation to derive the required result.

•

Mathematical Induction (HL only) is a formal method to prove a statement P(n)P(n) for all n∈Z+n \in \mathbb{Z}^{+}. It consists of three main parts: 1. The Basis step (showing P(1)P(1) is true), 2. The Inductive Hypothesis (assuming P(k)P(k) is true), and 3. The Inductive Step (proving P(k+1)P(k+1) is true based on the assumption).

•

Proof by exhaustion involves breaking the statement down into a finite number of cases and proving each case individually.

📐Formulae

n=2k (Definition of an even integer, k∈Z)n = 2k \text{ (Definition of an even integer, } k \in \mathbb{Z})

n=2k+1 (Definition of an odd integer, k∈Z)n = 2k + 1 \text{ (Definition of an odd integer, } k \in \mathbb{Z})

If a∣b and a∣c, then a∣(b+c) (Divisibility rule)\text{If } a | b \text{ and } a | c, \text{ then } a | (b + c) \text{ (Divisibility rule)}

∑r=1nr=n(n+1)2 (Sum of first n integers proof by induction)\sum_{r=1}^{n} r = \frac{n(n+1)}{2} \text{ (Sum of first } n \text{ integers proof by induction)}

💡Examples

Problem 1:

Prove that the square of any odd integer is also an odd integer.

Solution:

Let the odd integer be n=2k+1n = 2k + 1 where k∈Zk \in \mathbb{Z}. Squaring both sides: n2=(2k+1)2n^2 = (2k + 1)^2 n2=4k2+4k+1n^2 = 4k^2 + 4k + 1 n2=2(2k2+2k)+1n^2 = 2(2k^2 + 2k) + 1 Since kk is an integer, m=2k2+2km = 2k^2 + 2k must also be an integer. Therefore, n2=2m+1n^2 = 2m + 1, which satisfies the definition of an odd integer.

Explanation:

This is a direct proof using the algebraic definition of an odd number.

Problem 2:

Disprove the statement: 'For all n∈Z+n \in \mathbb{Z}^{+}, n2+n+41n^2 + n + 41 is a prime number.'

Solution:

We seek a counter-example. Let n=41n = 41. n2+n+41=412+41+41n^2 + n + 41 = 41^2 + 41 + 41 412+41+41=41(41+1+1)41^2 + 41 + 41 = 41(41 + 1 + 1) 412+41+41=41×4341^2 + 41 + 41 = 41 \times 43 Since the result is a product of two integers greater than 1, it is not prime.

Explanation:

To disprove a 'for all' statement, we only need to provide one case where the statement is false.

Problem 3:

Prove by induction that ∑r=1n(2r−1)=n2\sum_{r=1}^{n} (2r - 1) = n^2 for n∈Z+n \in \mathbb{Z}^{+}.

Solution:

  1. Basis step: For n=1n=1, LHS=2(1)−1=1LHS = 2(1)-1 = 1 and RHS=12=1RHS = 1^2 = 1. True for n=1n=1.
  2. Assumption: Assume true for n=kn=k: ∑r=1k(2r−1)=k2\sum_{r=1}^{k} (2r - 1) = k^2.
  3. Inductive step: For n=k+1n=k+1: ∑r=1k+1(2r−1)=[∑r=1k(2r−1)]+[2(k+1)−1]\sum_{r=1}^{k+1} (2r - 1) = [\sum_{r=1}^{k} (2r - 1)] + [2(k+1) - 1] Using the assumption: =k2+2k+2−1=k2+2k+1=(k+1)2= k^2 + 2k + 2 - 1 = k^2 + 2k + 1 = (k+1)^2.
  4. Conclusion: Since P(1)P(1) is true and P(k)  ⟹  P(k+1)P(k) \implies P(k+1), the statement is true for all n∈Z+n \in \mathbb{Z}^{+}.

Explanation:

This follows the standard four-step layout for a proof by mathematical induction.