1.5.1 Proof by Induction

Proof by Induction

Proof by induction is a way of proving a result is true for a set of integers by showing that if it is true for one integer then it is true for the next integer
It can be thought of as dominoes:

For example: To prove $\sum_{r = 1}^{n} r^{2} = \frac{1}{6} n (n + 1) (2 n + 1)$ is true for all integers n ≥ 1 you would first need to show it is true for n = 1:
$\sum_{r = 1}^{1} r^{2} = \frac{1}{6} (1) ((1) + 1) (2 (1) + 1)$

For example: Assume $\sum_{r = 1}^{k} r^{2} = \frac{1}{6} k (k + 1) (2 k + 1)$ is true

For example: $L H S = \sum_{r = 1}^{k + 1} r^{2}$ and $R H S = \frac{1}{6} (k + 1) ((k + 1) + 1) (2 (k + 1) + 1)$

If true for n = k then it is true for n = k + 1
Since true for n = 1 the statement is true for all n ∈ ℤ, n ≥ 1 by mathematical induction

The sentence will be the same for each proof just change the base case from n = 1 if necessary

Sums of sequences
- If the terms involve factorials then $(k + 1)! = (k + 1) \times (k!)$ is useful
- These can be written in the form $\sum_{r = 1}^{n} f (r) = g (n)$
- A useful trick for the inductive step is using $\sum_{r = 1}^{k + 1} f (r) = f (k + 1) + \sum_{r = 1}^{k} f (r)$
Divisibility of an expression by an integer
- These can be written in the form $f (n) = m \times q_{n}$ where m & q_n are integers
- A useful trick for the inductive step is using $a^{k + 1} = a \times a^{k}$
Complex numbers
- You can use proof by induction to prove de Moivre’s theorem
Derivatives
- Such as chain rule, product rule & quotient rule
- These can be written in the form $f^{(n)} (x) = g (x)$
- A useful trick for the inductive step is using $f^{(k + 1)} (x) = \frac{d}{d x} (f^{(k)} (x))$
- You will have to use the differentiation rules

Learn the steps for proof by induction and make sure you can use the method for a number of different types of questions before going into the exam
The trick to answering these questions well is practicing the pattern of using each step regularly

Prove by induction that $\sum_{r = 1}^{n} r (r - 3) = \frac{1}{3} n (n - 4) (n + 1)$ for $n \in ℤ^{+}$ .

1-5-1-ib-aa-hl-proof-by-induction-we-solution