Mathematical induction is the process of verifying or proving a mathematical statement is true for all values of
within given parameters. For example:
![{\displaystyle {\text{Prove that }}f(n)=5^{n}+8n+3{\text{ is divisible by }}4,{\text{ for }}n\in \mathbb {Z} ^{+}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8925751a9b9df56aeb313fb308ee8d67a9df609d)
We are asked to prove that
is divisible by 4. We can test if it's true by giving
values.
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b) |
![{\displaystyle f(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c1c49fad1eccc4e9af1e4f23f32efdc3ac4da973) |
|
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 16}](https://wikimedia.org/api/rest_v1/media/math/render/svg/960615e346e1c003a911f45b1225113ea01b4ff7) |
|
![{\displaystyle 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/901fc910c19990d0dbaaefe4726ceb1a4e217a0f) |
![{\displaystyle 44}](https://wikimedia.org/api/rest_v1/media/math/render/svg/007b371fb10b4cfe6e52ef5102e0a13eab5d46d6) |
|
![{\displaystyle 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/991e33c6e207b12546f15bdfee8b5726eafbbb2f) |
![{\displaystyle 152}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e996d076039352b9a0895374c788d8807a0a5b3) |
|
![{\displaystyle 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/295b4bf1de7cd3500e740e0f4f0635db22d87b42) |
![{\displaystyle 660}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13242c60f1fbf602472ae74450a9233c14d5eda6) |
|
![{\displaystyle 5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29483407999b8763f0ea335cf715a6a5e809f44b) |
![{\displaystyle 3168}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a8c983c2bbeda78d2d015edc8174e297a7406be) |
|
So, the first 5 values of n are divisible by 4, but what about all cases? That's where mathematical induction comes in.
Mathematical induction is a rigorous process, as such all proofs must have the same general format:
- Proposition – What are you trying to prove?
- Base case – Is it true for the first case? This means is it true for the first possible value of
.
- Assumption – We assume what we are trying to prove is true for a general number. such as
, also known as the induction hypothesis.
- Induction – Show that if our assumption is true for the (
term, then it must also be true for the (
term.
- Conclusion – Formalise your proof.
There will be four types of mathematical induction that you will come across in FP1:
- Summation of series;
- Divisibility;
- Recurrence relations;
- Matrices.
(Empty)
Proposition:
Notice our parameter,
. This means that what we want to prove must be true for all values of
which belong to the set (denoted by
) of positive integers (
).
Base case:
Assumption (Induction Hypothesis): Now we let
where
is a general positive integer, and we assume that
.
Remember that
.
Induction: Now we want to prove that the
term is also divisible by 4
Hence:
This is where our assumption comes in, if
then 4 must also divide
.
So:
Now we've shown
and thus
. This implies that
because you have successfully shown that 4 divides
, where
is a general, positive integer (
) and also the consecutive term after the general term (
)
Conclusion:
(Empty)
(Empty)