krit.club logo

Number and Algebra - Proof (including Proof by Induction for HL)

Grade 11IB

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

🔑Concepts

•

Direct Proof: This method involves a logical sequence of statements, starting from known axioms or previously proven theorems, to reach a conclusion. It follows a linear, forward-moving path. Visually, think of this as a series of connected arrows pointing from the premise PP directly to the conclusion QQ, where each arrow represents a valid logical step.

•

Proof by Contradiction: This concept relies on assuming the negation of the statement you wish to prove and showing that this leads to a logical impossibility or contradiction (e.g., 1=01=0 or a number being both even and odd). Visually, imagine a traveler reaching a fork in the road; by showing that one path leads to a cliff, the traveler proves the other path must be the correct one.

•

Proof by Counter-example: To disprove a universal statement such as 'All xx satisfy property PP', you only need to find a single instance where the statement is false. Visually, if a hypothesis claims all shapes in a box are circles, simply pulling out one square serves as a complete disproof. This is a powerful tool for testing the validity of conjectures.

•

Mathematical Induction (HL) - The Domino Effect: This is a formal method used to prove that a statement P(n)P(n) is true for all positive integers nn. Visually, it is compared to an infinite line of dominoes. If you can knock down the first domino (Base Case) and show that any falling domino will always knock down the next one (Inductive Step), then all dominoes will eventually fall.

•

Induction Step 1 - The Base Case: This involves verifying that the statement P(n)P(n) is true for the smallest possible value of nn (usually n=1n=1). In the domino analogy, this corresponds to checking that the first domino in the sequence is actually tipped over. Without this, the chain reaction cannot begin.

•

Induction Step 2 - The Inductive Hypothesis: We assume that the statement is true for an arbitrary integer kk, written as P(k)P(k). This assumption acts as our 'bridge' or our 'middle domino' in the sequence. It allows us to use P(k)P(k) as a tool to prove the next case.

•

Induction Step 3 - The Inductive Step: We must prove that if P(k)P(k) is true, then P(k+1)P(k+1) must also be true. Visually, this is the mechanism that connects the kk-th domino to the (k+1)(k+1)-th domino. Once this link is proven, the Principle of Mathematical Induction concludes that the statement is true for all n∈Z+n \in \mathbb{Z}^+.

•

Divisibility Proofs: In algebraic proofs, we say aa is divisible by bb if there exists an integer kk such that a=bka = bk. In induction, this often requires manipulating an expression for n=k+1n=k+1 to factor out the divisor bb. Visually, imagine a large rectangular block of area aa being perfectly partitioned into smaller identical blocks of area bb without any remainder.

📐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=1nr3=(n(n+1)2)2\sum_{r=1}^{n} r^3 = \left(\frac{n(n+1)}{2}\right)^2

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

P(k)  ⟹  P(k+1)P(k) \implies P(k+1)

(n+1)!=(n+1)×n!(n+1)! = (n+1) \times n!

💡Examples

Problem 1:

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

Solution:

Step 1: Base Case Let n=1n=1. LHS=2(1)−1=1LHS = 2(1)-1 = 1 RHS=12=1RHS = 1^2 = 1 Since LHS=RHSLHS = RHS, P(1)P(1) is true.

Step 2: Inductive Hypothesis Assume P(k)P(k) is true for some k∈Z+k \in \mathbb{Z}^+, i.e., ∑r=1k(2r−1)=k2\sum_{r=1}^{k} (2r-1) = k^2.

Step 3: Inductive Step We need to show P(k+1)P(k+1) is true: ∑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) = \sum_{r=1}^{k} (2r-1) + [2(k+1)-1] Substituting the hypothesis: =k2+(2k+2−1)=k2+2k+1= k^2 + (2k+2-1) = k^2 + 2k + 1 Factoring the quadratic: =(k+1)2= (k+1)^2 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}^+ by the Principle of Mathematical Induction.

Explanation:

This example demonstrates the standard summation induction. We use the assumption for n=kn=k to replace the first kk terms of the sum for n=k+1n=k+1, then simplify algebraically to match the target expression.

Problem 2:

Prove that 7n−17^n - 1 is divisible by 66 for all n∈Z+n \in \mathbb{Z}^+.

Solution:

Step 1: Base Case Let n=1n=1. 71−1=67^1 - 1 = 6, which is divisible by 66. P(1)P(1) is true.

Step 2: Inductive Hypothesis Assume P(k)P(k) is true: 7k−1=6m7^k - 1 = 6m for some integer mm. This implies 7k=6m+17^k = 6m + 1.

Step 3: Inductive Step Consider n=k+1n=k+1: 7k+1−17^{k+1} - 1. 7k+1−1=7(7k)−17^{k+1} - 1 = 7(7^k) - 1 Substitute the expression for 7k7^k: =7(6m+1)−1= 7(6m + 1) - 1 =42m+7−1=42m+6= 42m + 7 - 1 = 42m + 6 Factor out 66: =6(7m+1)= 6(7m + 1) Since 7m+17m+1 is an integer, 7k+1−17^{k+1}-1 is divisible by 66. Conclusion: By the Principle of Mathematical Induction, 7n−17^n - 1 is divisible by 66 for all n∈Z+n \in \mathbb{Z}^+.

Explanation:

This example uses induction for divisibility. The key strategy is to isolate the base of the exponent from the inductive hypothesis (7k7^k) and substitute it into the n=k+1n=k+1 expression.