Mathematical induction is the process of verifying or proving a mathematical statement is true for all values of
n
{\displaystyle n}
P
r
o
v
e
t
h
a
t
f
(
n
)
=
5
n
+
8
n
+
3
i
s
d
i
v
i
s
i
b
l
e
b
y
4
,
f
o
r
n
∈
Z
+
{\displaystyle Prove\ that\ f(n)=5^{n}+8n+3\ is\ divisible\ by\ 4,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)}
D
i
v
i
s
i
b
l
e
b
y
4
{\displaystyle Divisible\ by\ 4}
1
{\displaystyle 1}
16
{\displaystyle 16}
4
∗
4
{\displaystyle 4*4}
2
{\displaystyle 2}
44
{\displaystyle 44}
4
∗
11
{\displaystyle 4*11}
3
{\displaystyle 3}
152
{\displaystyle 152}
4
∗
38
{\displaystyle 4*38}
4
{\displaystyle 4}
660
{\displaystyle 660}
4
∗
165
{\displaystyle 4*165}
5
{\displaystyle 5}
3168
{\displaystyle 3168}
4
∗
792
{\displaystyle 4*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.
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 proofs by Induction involving Summing series
edit
Proposition:
P
r
o
v
e
b
y
i
n
d
u
c
t
i
o
n
t
h
a
t
,
∑
r
=
1
n
r
3
=
1
4
n
2
(
n
+
1
)
2
{\displaystyle Prove\ by\ induction\ that,\displaystyle \sum _{r=1}^{n}r^{3}={\frac {1}{4}}n^{2}(n+1)^{2}}
,
f
o
r
n
∈
N
+
{\displaystyle ,for\ n\in \mathbb {N^{+}} }
Note our parameter,
f
o
r
n
∈
N
+
{\displaystyle for\ n\in \mathbb {N^{+}} }
n
{\displaystyle n}
∈
{\displaystyle \in }
N
+
{\displaystyle \mathbb {N^{+}} }
Basis case:
L
e
t
n
=
1
{\displaystyle Let\ n=1\ }
∑
r
=
1
1
r
3
=
1
3
[
L
H
S
]
{\displaystyle \displaystyle \sum _{r=1}^{1}r^{3}=1^{3}\ [LHS]}
1
4
1
2
(
1
+
1
)
2
=
1
[
R
H
S
]
{\displaystyle {\frac {1}{4}}1^{2}(1+1)^{2}=1\ [RHS]}
The Left hand side of our equation is equal to the right hand side of our equation, therefore our basis case holds true.
L
H
S
=
R
H
S
⟶
∑
r
=
1
n
r
3
=
1
4
n
2
(
n
+
1
)
2
,
f
o
r
n
=
1
{\displaystyle LHS=RHS\longrightarrow \displaystyle \sum _{r=1}^{n}r^{3}={\frac {1}{4}}n^{2}(n+1)^{2},for\ n=1}
Now you make your assumption:
N
o
w
,
l
e
t
n
=
k
a
n
d
a
s
s
u
m
e
t
r
u
e
∀
k
∈
Z
+
{\displaystyle Now,\ let\ n=k\ and\ assume\ true\ \forall \ k\in \mathbb {Z^{+}} }
This is what we are assuming to be true for all values of K which belong to the set of positive integers:
∑
r
=
1
k
r
3
=
1
4
k
2
(
k
+
1
)
2
{\displaystyle \displaystyle \sum _{r=1}^{k}r^{3}={\frac {1}{4}}k^{2}(k+1)^{2}}
Induction: For the induction we need to utilise the fact we are assuming
n
=
k
{\displaystyle n=k}
(
k
+
1
)
{\displaystyle (k+1)}
k
t
h
{\displaystyle k^{th}}
(
k
+
1
)
t
h
{\displaystyle (k+1)^{th}}
H
e
n
c
e
,
l
e
t
n
=
k
+
1
:
∑
r
=
1
k
+
1
r
3
=
∑
r
=
1
k
r
3
+
(
k
+
1
)
3
{\displaystyle Hence,\ let\ n=k+1:\displaystyle \sum _{r=1}^{k+1}r^{3}=\displaystyle \sum _{r=1}^{k}r^{3}+(k+1)^{3}}
∑
r
=
1
k
+
1
r
3
=
1
4
k
2
(
k
+
1
)
2
+
(
k
+
1
)
3
{\displaystyle \displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}k^{2}(k+1)^{2}+(k+1)^{3}}
Factoring out
1
4
(
k
+
1
)
2
{\displaystyle {\frac {1}{4}}(k+1)^{2}}
∑
r
=
1
k
+
1
r
3
=
1
4
(
k
+
1
)
2
[
k
2
+
4
(
k
+
1
)
]
{\displaystyle \displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}(k+1)^{2}[k^{2}+4(k+1)]}
This gives us:
∑
r
=
1
k
+
1
r
3
=
1
4
(
k
+
1
)
2
(
k
+
2
)
2
{\displaystyle \displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}(k+1)^{2}(k+2)^{2}}
n
{\displaystyle n}
k
+
1
{\displaystyle k+1}
Summary:
∴
t
r
u
e
f
o
r
n
=
k
+
1
⟶
t
r
u
e
∀
n
∈
Z
+
{\displaystyle \therefore \ true\ for\ n=k+1\longrightarrow \ true\ \forall \ n\in \mathbb {Z^{+}} }
n
=
k
{\displaystyle n=k}
n
=
k
+
1
{\displaystyle n=k+1}
n
{\displaystyle n}
n
{\displaystyle n}
Example of a proof by induction involving Divisibility
edit
Proposition:
P
r
o
v
e
t
h
a
t
4
|
f
(
n
)
=
5
n
+
8
n
+
3
,
f
o
r
n
∈
N
+
{\displaystyle Prove\ that\ 4\ |\ f(n)=5^{n}+8n+3,\ for\ n\in \mathbb {N^{+}} }
Again, note our parameter,
f
o
r
n
∈
N
+
{\displaystyle for\ n\in \mathbb {N^{+}} }
n
{\displaystyle n}
∈
{\displaystyle \in }
N
+
{\displaystyle \mathbb {N^{+}} }
Basis case:
L
e
t
n
=
1
{\displaystyle Let\ n=1}
f
(
1
)
=
5
1
+
8
(
1
)
+
3
⇒
f
(
1
)
=
16
{\displaystyle f(1)=5^{1}+8(1)+3\Rightarrow f(1)=16}
∴
4
|
f
(
1
)
{\displaystyle \therefore \ 4\ |\ f(1)}
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
l
e
t
n
=
k
+
1
→
f
(
k
+
1
)
=
5
k
+
1
+
8
(
k
+
1
)
+
3
{\displaystyle let\ n=k+1\rightarrow \ 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
{\displaystyle f(k+1)-f(k)=5(5^{k})-5^{k}+8}
f
(
k
+
1
)
−
f
(
k
)
=
4
(
5
k
)
+
8
{\displaystyle f(k+1)-f(k)=4(5^{k})+8}
∴
f
(
k
+
1
)
−
f
(
k
)
=
4
(
5
k
+
2
)
{\displaystyle \therefore f(k+1)-f(k)=4(5^{k}+2)}
Now we've shown
4
|
f
(
k
+
1
)
−
f
(
k
)
{\displaystyle 4\ |\ f(k+1)-f(k)}
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:
If
4
|
f
(
k
)
⇒
4
|
f
(
k
+
1
)
{\displaystyle 4\ |\ f(k)\Rightarrow 4\ |\ f(k+1)}
∴
4
|
f
(
n
)
,
∀
n
∈
Z
+
{\displaystyle \therefore \ 4\ |\ f(n),\forall \ n\in \mathbb {Z^{+}} }
I
f
4
d
i
v
i
d
e
s
f
(
k
)
(
a
s
w
e
a
s
s
u
m
e
d
)
t
h
e
n
i
t
i
s
i
m
p
l
i
e
s
t
h
a
t
4
a
l
s
o
d
i
v
i
d
e
s
f
(
k
+
1
)
,
{\displaystyle If\ 4\ divides\ f(k)\ (as\ we\ assumed)\ then\ it\ is\ implies\ that\ 4\ also\ divides\ f(k+1),}
t
h
e
r
e
f
o
r
e
4
d
i
v
i
d
e
s
f
(
n
)
,
f
o
r
a
l
l
v
a
l
u
e
s
o
f
n
t
h
a
t
b
e
l
o
n
g
t
o
t
h
e
s
e
t
o
f
p
o
s
i
t
i
v
e
i
n
t
e
g
e
r
s
.
{\displaystyle therefore\ 4\ divides\ f(n),\ for\ all\ values\ of\ n\ that\ belong\ to\ the\ set\ of\ positive\ integers.}
Example of recurrence Relations proofs by Induction
edit
Example of proofs by Induction involving Matrices
edit
![{\displaystyle \displaystyle \sum _{r=1}^{1}r^{3}=1^{3}\ [LHS]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32875919c173989ba6b988a517d16639cd443691)
![{\displaystyle {\frac {1}{4}}1^{2}(1+1)^{2}=1\ [RHS]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab4a7ab2ef467afed4eb6e080d966352c42bbc84)
![{\displaystyle \displaystyle \sum _{r=1}^{k+1}r^{3}={\frac {1}{4}}(k+1)^{2}[k^{2}+4(k+1)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3242fe54029b6cc2d14e5cffe60504f717fba2d3)
