krit.club logo

Number and Algebra - Mathematical Proof (Induction, Contradiction)

Grade 12IB

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

🔑Concepts

•

Mathematical Induction Principle: A three-step logical process used to prove a statement P(n)P(n) is true for all n∈Z+n \in \mathbb{Z}^+. It can be visualized as a sequence of falling dominoes; if the first domino falls (Base Case) and every falling domino knocks over the next (Inductive Step), then all dominoes will eventually fall.

•

The Base Case: The initial step of induction where you verify that P(n)P(n) is true for the smallest possible value of nn (usually n=1n=1 or n=0n=0). This establishes the foundation of the proof.

•

The Inductive Hypothesis: A crucial assumption made within the proof where you assume P(k)P(k) is true for some arbitrary positive integer kk. This serves as the 'bridge' to reach the next term.

•

The Inductive Step: The algebraic process of showing that if P(k)P(k) is true, then P(k+1)P(k+1) must also be true. Visually, this is like showing that the kk-th rung of a ladder allows you to reach the (k+1)(k+1)-th rung.

•

Proof by Contradiction (Reductio ad Absurdum): A logic-based proof method where you assume the negation of the statement you wish to prove. By showing that this assumption leads to a logical impossibility or a 'dead end' (contradiction), you conclude that the original statement must be true.

•

Divisibility Proofs via Induction: Often involve showing that a function f(n)f(n) is divisible by a number mm. In the inductive step, you typically manipulate f(k+1)f(k+1) to express it as a combination of f(k)f(k) and other terms that are clearly multiples of mm.

•

Irrationality Proofs: A common application of contradiction where a number is assumed to be rational (expressible as pq\frac{p}{q} in simplest form). If algebraic manipulation shows that pp and qq share a common factor, the 'simplest form' premise is violated, proving the number is irrational.

📐Formulae

∑r=1nr=n(n+1)2\sum_{r=1}^{n} r = \frac{n(n+1)}{2}

∑r=1nr2=n(n+1)(2n+1)6\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}

∑r=1narr−1=a(rn−1)r−1,r≠1\sum_{r=1}^{n} ar^{r-1} = \frac{a(r^n - 1)}{r-1}, r \neq 1

a∣b  ⟺  b=ak for some k∈Za | b \iff b = ak \text{ for some } k \in \mathbb{Z}

x∈Q  ⟺  x=pq, where p,q∈Z,q≠0,gcd(p,q)=1x \in \mathbb{Q} \iff x = \frac{p}{q}, \text{ where } p, q \in \mathbb{Z}, q \neq 0, \text{gcd}(p, q) = 1

💡Examples

Problem 1:

Use mathematical induction to prove that ∑r=1n(2r−1)=n2\sum_{r=1}^{n} (2r-1) = n^2 for all n∈Z+n \in \mathbb{Z}^+.

Solution:

  1. Base Case: Let n=1n=1. LHS: 2(1)−1=12(1)-1 = 1. RHS: 12=11^2 = 1. Since LHS = RHS, P(1)P(1) is true.
  2. Inductive Hypothesis: Assume P(k)P(k) is true for some k∈Z+k \in \mathbb{Z}^+, so ∑r=1k(2r−1)=k2\sum_{r=1}^{k} (2r-1) = k^2.
  3. Inductive Step: Prove P(k+1)P(k+1) is true, i.e., ∑r=1k+1(2r−1)=(k+1)2\sum_{r=1}^{k+1} (2r-1) = (k+1)^2. ∑r=1k+1(2r−1)=(∑r=1k(2r−1))+[2(k+1)−1]\sum_{r=1}^{k+1} (2r-1) = \left( \sum_{r=1}^{k} (2r-1) \right) + [2(k+1)-1] =k2+(2k+2−1)= k^2 + (2k + 2 - 1) (using inductive hypothesis) =k2+2k+1= k^2 + 2k + 1 =(k+1)2= (k+1)^2
  4. Conclusion: Since P(1)P(1) is true and P(k)  ⟹  P(k+1)P(k) \implies P(k+1), by the principle of mathematical induction, P(n)P(n) is true for all n∈Z+n \in \mathbb{Z}^+.

Explanation:

The solution first verifies the smallest case, then uses the summation of kk terms as a starting point to find the sum of k+1k+1 terms, showing it simplifies to the target formula.

Problem 2:

Prove by contradiction that 2\sqrt{2} is irrational.

Solution:

  1. Assumption: Assume 2\sqrt{2} is rational. Then 2=pq\sqrt{2} = \frac{p}{q} where p,q∈Z,q≠0p, q \in \mathbb{Z}, q \neq 0 and pq\frac{p}{q} is in simplest form (no common factors).
  2. Algebraic Manipulation: 2=p2q2  ⟹  p2=2q22 = \frac{p^2}{q^2} \implies p^2 = 2q^2. This means p2p^2 is even, so pp must be even. Let p=2kp = 2k.
  3. Substitution: (2k)2=2q2  ⟹  4k2=2q2  ⟹  q2=2k2(2k)^2 = 2q^2 \implies 4k^2 = 2q^2 \implies q^2 = 2k^2. This means q2q^2 is even, so qq must be even.
  4. Contradiction: If pp and qq are both even, they share a common factor of 2. This contradicts our assumption that pq\frac{p}{q} was in simplest form.
  5. Conclusion: Therefore, the assumption is false, and 2\sqrt{2} is irrational.

Explanation:

The proof relies on the fact that if a square of an integer is even, the integer itself must be even. By showing both numerator and denominator are even, we invalidate the 'simplest form' requirement of rational numbers.