Unit 1 - Number and Algebra
Required Prior Knowledge
Questions
Factorise:
a) \(3x\left(x+1\right)^{2} - 5\left(x+1\right)\)
b) \(\frac{x}{3}\left(x-2\right)^{3}+2x^{2}\left(x-2\right)^{2}\)
Solutions
Get Ready
Questions
By examining the cases when \(n=1,2,3,4\) make a conjecture about the sum $$S_{n}=\frac{1}{1\times 2}+\frac{1}{2\times 3}+\frac{1}{3\times 4}+\frac{1}{4\times 5} + … + \frac{1}{n\left(n+1\right)}$$
Solutions
Notes
By looking at patterns we can sometimes conjecture a general rule for a series.
But this is a conjecture, and not a theorem, whilst it remains unproven.
Proof by induction is a mathematical technique used to establish the truth of an infinite number of statements. It consists of four main steps:
Base Case: you must verify the statement is true for a specific starting value, typically \(n=1\) or \( n = 0 \). This step demonstrates that the statement holds true for the initial case.
Assumption: assume that the statement is true for some arbitrary integer \( n = k \). This assumption is sometimes referred to as the inductive hypothesis.
Inductive Step: the goal now is to show that if the statement holds for \( n = k \), it must also hold for \( n = k + 1 \).
Conclusion: with this shown we conclude the proof. We have shown that it is true for the base case, and also that if it is true when \(n=k\) it is also true for \(n=k+1\).
This process shows it is true for all integers greater than or equal to the base case. Sometimes we think of proof by induction as similar to set of dominoes falling. Once the first domino is pushed over (the base case) we know that each domino (\(n=k\)) will knock over the next domino (\(n=k+1\)).
The power of induction lies in its ability to infer the validity of an infinite series of cases based on a finite verification process.
One common question type for which proof by induction can be used is to prove the formula for a given series.
Examples and Your Turns
Example
Use mathematical induction to prove that, for \(n\in\mathbb{Z}^{+}\), $$1^{3}+2^{3}+3^{3}+…+n^{3} = \frac{n^{2}}{4}\left(n+1\right)^{2}$$
Proof
Step 1 (Base Case \(n=1\))
$$LHS = 1^{3}=1\\RHS=\frac{1^{2}}{4}\left(1+1\right)^{2}=\frac{1}{4}\times 4=1$$\(\therefore\) when \(n=1\) the statement is true and so the base case holds.
Step 2 (Assumption \(n=k\))
Assume that $$1^{3}+2^{3}+3^{3}+…+k^{3} = \frac{k^{2}}{4}\left(k+1\right)^{2}$$
Step 3 (Inductive Step \(n=k+1\))
WTS (want to show) $$1^{3}+2^{3}+3^{3}+…+\left(k+1\right)^{3} = \frac{\left(k+1\right)^{2}}{4}\left(k+2\right)^{2}$$
We start with the left hand side:$$\begin{align}LHS&=1^{3}+2^{3}+3^{3}+…+k^{3}+\left(k+1\right)^{3} \\ &= \frac{k^{2}}{4}\left(k+1\right)^{2}+\left(k+1\right)^{3} \\ &= \frac{\left(k+1\right)^{2}}{4}\left(k^{2}+4\left(k+1\right)\right) \\ &=\frac{\left(k+1\right)^{2}}{4}\left(k^{2}+4k+4\right) \\ &=\frac{\left(k+1\right)^{2}}{4}\left(k+2\right)^{2} \\ &= RHS \end{align}$$
Step 4 (Conclusion)
Hence, by the principle of mathematical induction, since the statement is true for the base case when \(n=1\), and if the statement holds for \(n=k\) it also holds for \(n=k+1\), it must hold for all \(n\in \mathbb{Z}^{+}\).
Q.E.D.
There is also a handwritten version of this proof here.
Your Turn
Use mathematical induction to prove that, for \(n\in\mathbb{Z}^{+}\), $$1+3+5+…+\left(2n-1\right) = n^{2}$$
Your Turn
Use mathematical induction to prove that, for \(n\in\mathbb{Z}^{+}\), $$2+4+6+8+…+2n = n^{2}+n$$
Your Turn
Use mathematical induction to prove that, for \(n\in\mathbb{Z}^{+}\), $$2^{0}+2^{1}+2^{2}+2^{3}+…+2^{n-1} = 2^{n}-1$$
Your Turn
Use mathematical induction to prove that, for \(n\in\mathbb{Z}^{+}\), $$\frac{1}{1\times 2}+\frac{1}{2\times 3}+\frac{1}{3\times 4}+\frac{1}{4\times 5} + … + \frac{1}{n\left(n+1\right)} = \frac{n}{n+1}$$
Notes
Another common question type for proof by induction is to show that a given expression will always be a multiple of a specific integer.
If \(k\) is divisible by \(n\), then we can write \(k=an\) for some value \(a\in\mathbb{N}\).
If \(k\) is a multiple of \(n\), then we can write \(k=an\) for some value \(a\in\mathbb{N}\).
Examples and Your Turns
Example
Use mathematical induction to prove that \(3^{2n}+7\) is divisible by \(8\) for all \(n\in\mathbb{N}\).
Proof
Step 1 (Base Case \(n=0\))
\(3^{0}+7=1+7=8\) which is divisible by \(8\).
\(\therefore\) when \(n=0\) the statement is true and so the base case holds.
Step 2 (Assumption \(n=k\))
Assume that \(3^{2k}+7\) is divisible by \(8\). That is $$3^{2k}+7=8A \text{ for some }A\in\mathbb{N}$$
Step 3 (Inductive Step \(n=k+1\))
WTS (want to show) $$3^{2\left(k+1\right)}+7=8B$$
We start with the left hand side:$$\begin{align}LHS&=3^{2k+2}+7 \\&=\left(3^{2k}\right)\left(3^{2}\right)+7 \\ &=\left(8A-7\right)\left(9\right)+7 \\ &=72A-63+7 \\ &=72A-56 \\ &=8\left(9A-7\right) \\ &= RHS \end{align}$$ where \(B=9A-7\).
Step 4 (Conclusion)
Hence, by the principle of mathematical induction, since the statement is true for the base case when \(n=0\), and if the statement holds for \(n=k\) it also holds for \(n=k+1\), it must hold for all \(n\in \mathbb{Z}^{+}\).
Q.E.D.
Your Turn
Use mathematical induction to prove that \(7^{n}-1\) is divisible by \(6\) for all \(n\in\mathbb{N}\).
Your Turn
Use mathematical induction to prove that \(9^{n}-1\) is divisible by \(8\) for all \(n\in\mathbb{N}\).
Your Turn
Use mathematical induction to prove that \(n^{3}+5n\) is divisible by \(6\) for all \(n\in\mathbb{N}\).
Notes
A final common type of proof by induction question involves a series given in sigma notation.
For these there are two algebraic techniques which are very useful.
First we have that $$\sum_{i=1}^{5}i=1+2+3+4+5=\left(\sum_{i=1}^{4}i\right)+5$$
More generally $$\sum_{i=1}^{n}f\left(i\right)=\left(\sum_{i=1}^{n-1}f\left(i\right)\right)+f\left(n\right)$$
Secondly it is useful to be able to factorise expressions.
We know that we can factorise $$3k+5ak=k\left(3+5a\right)$$
Similarly we can factorise $$3\left(k+1\right)+5a\left(k+1\right)=\left(k+1\right)\left(3+5a\right)$$
Examples and Your Turns
Example
Use mathematical induction to prove that $$\sum_{r=1}^{n}r\left(2r+6\right)=\frac{2}{3}n\left(n+1\right)\left(n+5\right)$$
Proof
Step 1 (Base Case \(n=1\))
$$LHS = \sum_{r=1}^{1}r\left(2r+6\right)=1\left(2\left(1\right)+6\right)=8\\RHS=\frac{2}{3}\left(1\right)\left(1+1\right)\left(1+5\right)=\frac{2}{3}\left(12\right)=8$$\(\therefore\) when \(n=1\) the statement is true and so the base case holds.
Step 2 (Assumption \(n=k\))
Assume that $$\sum_{r=1}^{k}r\left(2r+6\right)=\frac{2}{3}k\left(k+1\right)\left(k+5\right)$$
Step 3 (Inductive Step \(n=k+1\))
WTS (want to show) $$\sum_{r=1}^{k+1}r\left(2r+6\right)=\frac{2}{3}\left(k+1\right)\left(k+2\right)\left(k+6\right)$$
We start with the left hand side:$$\begin{align}LHS&=\sum_{r=1}^{k}r\left(2r+6\right)+\left(k+1\right)\left(2\left(k+1\right)+6\right) \\&=\frac{2}{3}k\left(k+1\right)\left(k+5\right)+\left(k+1\right)\left(2k+8\right) \\&=\frac{2}{3}\left(k+1\right)\left(k\left(k+5\right)+\frac{3}{2}\left(2k+8\right)\right) \\ &=\frac{2}{3}\left(k+1\right)\left(k^{2}+5k+3k+12\right) \\ &=\frac{2}{3}\left(k+1\right)\left(k^{2}+8k+12\right) \\ &=\frac{2}{3}\left(k+1\right)\left(k+2\right)\left(k+6\right) \\ &= RHS \end{align}$$
Step 4 (Conclusion)
Hence, by the principle of mathematical induction, since the statement is true for the base case when \(n=1\), and if the statement holds for \(n=k\) it also holds for \(n=k+1\), it must hold for all \(n\in \mathbb{Z}^{+}\).
Q.E.D.
Your Turn
Use mathematical induction to prove that $$\sum_{r=1}^{n}r\left(r+2\right)=\frac{n}{6}\left(n+1\right)\left(2n+7\right)$$
Your Turn
Use mathematical induction to prove that $$\sum_{r=1}^{n}2^{r-1}=2^{n}-1$$
Your Turn
Use mathematical induction to prove that $$\sum_{r=1}^{n}r=\frac{n\left(n+1\right)}{2}$$
Your Turn
Use mathematical induction to prove that $$\sum_{r=1}^{n}r^{2}=\frac{n\left(n+1\right)\left(2n+1\right)}{6}$$
Your Turn
Use mathematical induction to prove that $$\sum_{r=1}^{n}r^{3}=\frac{n^{2}}{4}\left(n+1\right)^{2}$$
Key Facts
Use this applet to generate a prompt for a Key Fact that you need to know for the course. The idea is that you should KNOW these key facts in order to be able to solve problems.