Mathematical induction is the process of verifying or proving a mathematical statement is true for all values of
n
{\displaystyle n}
Prove that
f
(
n
)
=
5
n
+
8
n
+
3
is divisible by
4
,
for
n
∈
Z
+
{\displaystyle {\text{Prove that }}f(n)=5^{n}+8n+3{\text{ is divisible by }}4,{\text{ for }}n\in \mathbb {Z} ^{+}}
We are asked to prove that
f
(
n
)
{\displaystyle f(n)}
n
{\displaystyle n}
n
{\displaystyle n}
f
(
n
)
{\displaystyle f(n)}
Divisible by
4
{\displaystyle {\text{Divisible by }}4}
1
{\displaystyle 1}
16
{\displaystyle 16}
4
⋅
4
{\displaystyle 4\cdot 4}
2
{\displaystyle 2}
44
{\displaystyle 44}
4
⋅
11
{\displaystyle 4\cdot 11}
3
{\displaystyle 3}
152
{\displaystyle 152}
4
⋅
38
{\displaystyle 4\cdot 38}
4
{\displaystyle 4}
660
{\displaystyle 660}
4
⋅
165
{\displaystyle 4\cdot 165}
5
{\displaystyle 5}
3168
{\displaystyle 3168}
4
⋅
792
{\displaystyle 4\cdot 792}
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?
basis case – Is it true for the first case? This means is it true for the first possible value of
n
{\displaystyle n}
Assumption – We assume what we are trying to prove is true for a general number. such as
k
{\displaystyle k}
Induction – Show that if our assumption is true for the (
k
t
h
)
{\displaystyle k^{th})}
k
+
1
t
h
)
{\displaystyle k+1^{th})}
Conclusion – Formalise your proof. There will be four types of mathematical induction you will come across in FP1:
Summing series
Divisibility
Recurrence relations
Matrices Example of a proof by summation of series Edit Example of a proof by divisibility Edit Proposition:
Prove that
4
|
f
(
n
)
=
5
n
+
8
n
+
3
,
for
n
∈
N
+
{\displaystyle {\text{Prove that }}4~|~f(n)=5^{n}+8n+3,{\text{ for }}n\in \mathbb {N} ^{+}}
Note our parameter,
for
n
∈
N
+
{\displaystyle {\text{for }}n\in \mathbb {N} ^{+}}
n
{\displaystyle n}
∈
{\displaystyle \in }
N
+
{\displaystyle \mathbb {N} ^{+}}
Basis case:
Let
n
=
1
f
(
1
)
=
5
1
+
8
(
1
)
+
3
⟹
f
(
1
)
=
16
∴
4
|
f
(
1
)
{\displaystyle {\begin{aligned}&{\text{Let }}n=1\\&f(1)=5^{1}+8(1)+3\implies f(1)=16\\&\therefore 4~|~f(1)\end{aligned}}}
Assumption: Now we let
n
=
k
{\displaystyle n=k}
k
{\displaystyle k}
4
|
f
(
k
)
{\displaystyle 4\ |\ f(k)}
Remember
f
(
k
)
=
5
k
+
8
k
+
3
{\displaystyle f(k)=5^{k}+8k+3}
Induction: Now we want to prove that the
k
+
1
t
h
{\displaystyle k+1^{th}}
Hence
let
n
=
k
+
1
⟹
f
(
k
+
1
)
=
5
k
+
1
+
8
(
k
+
1
)
+
3
{\displaystyle {\text{let }}n=k+1\implies f(k+1)=5^{k+1}+8(k+1)+3}
This is where our assumption comes in, if
4
|
f
(
k
)
{\displaystyle 4~|~f(k)}
f
(
k
+
1
)
−
f
(
k
)
{\displaystyle f(k+1)-f(k)}
So:
f
(
k
+
1
)
−
f
(
k
)
=
5
k
+
1
+
8
(
k
+
1
)
+
3
−
(
5
k
+
8
k
+
3
)
{\displaystyle f(k+1)-f(k)=5^{k+1}+8(k+1)+3-(5^{k}+8k+3)}
f
(
k
+
1
)
−
f
(
k
)
=
5
(
5
k
)
−
5
k
+
8
f
(
k
+
1
)
−
f
(
k
)
=
4
(
5
k
)
+
8
∴
f
(
k
+
1
)
−
f
(
k
)
=
4
(
5
k
+
2
)
{\displaystyle {\begin{aligned}&f(k+1)-f(k)=5(5^{k})-5^{k}+8\\&f(k+1)-f(k)=4(5^{k})+8\\&\therefore ~f(k+1)-f(k)=4(5^{k}+2)\end{aligned}}}
Now we've shown
4
|
(
f
(
k
+
1
)
−
f
(
k
)
)
{\displaystyle 4~|~{\bigl (}f(k+1)-f(k){\bigr )}}
4
|
f
(
k
+
1
)
{\displaystyle 4~|~f(k+1)}
4
|
f
(
n
)
{\displaystyle 4~|~f(n)}
f
(
n
)
{\displaystyle f(n)}
n
{\displaystyle n}
k
{\displaystyle k}
k
+
1
{\displaystyle k+1}
Conclusion:
4
|
f
(
k
)
⟹
4
|
f
(
k
+
1
)
∴
4
|
f
(
n
)
,
∀
n
∈
Z
+
{\displaystyle {\begin{aligned}&4~|~f(k)\implies 4~|~f(k+1)\\&\therefore ~4~|~f(n),\forall n\in \mathbb {Z} ^{+}\end{aligned}}}
If
4
divides
f
(
k
)
(as we assumed) then it is implies that
4
also divides
f
(
k
+
1
)
therefore
4
divides
f
(
n
)
,
for all values of
n
that belong to the set of positive integers.
{\displaystyle {\begin{aligned}&{\text{If }}4{\text{ divides }}f(k){\text{ (as we assumed) then it is implies that }}4{\text{ also divides }}f(k+1)\\&{\text{therefore }}4{\text{ divides }}f(n),{\text{ for all values of }}n{\text{ that belong to the set of positive integers.}}\end{aligned}}}
References Edit 
