This is a beta course, so its structure, chapters, and examples may continue to change.
Proving Divisibility
Proving divisibility problems with mathematical induction is common in number theory. The key is to use the properties of divisibility and modular arithmetic.
Basic Knowledge
Divisibility notation: a∣b means that a divides b, i.e., there exists an integer k such that b=ka.
Properties of divisibility:
If a∣b and a∣c, then a∣(b±c)
If a∣b, then a∣kb (k is any integer)
Proof Strategy
The steps to prove a∣f(n):
Base case: verify that a∣f(n0)
Inductive hypothesis: assume a∣f(k), i.e., f(k)=ma (m is an integer)
Inductive step: express f(k+1) in a form containing f(k), then use the inductive hypothesis
Worked Examples
Example 1: Basic Divisibility
Proposition: prove that n3−n is divisible by 6.
Proof:
Base case: when n=1, 13−1=0=6×0, divisible by 6.
Inductive hypothesis: assume k3−k is divisible by 6, i.e., k3−k=6m (m is an integer)
Conclusion: by mathematical induction, 7n−1 is divisible by 6 for all n≥1.
Example 3: Divisibility in the Fibonacci Sequence
Proposition: the Fibonacci sequence F1=1,F2=1,Fn+2=Fn+1+Fn. Prove that F3n is divisible by 2.
Proof:
First compute the first few terms: F1=1,F2=1,F3=2,F4=3,F5=5,F6=8,F7=13,F8=21,F9=34
Base case: when n=1, F3=2, divisible by 2.
Inductive hypothesis: assume F3k is divisible by 2.
Inductive step: we need to prove that F3(k+1)=F3k+3 is divisible by 2.
Use the property of the Fibonacci sequence: Fn+3=Fn+2+Fn+1=(Fn+1+Fn)+Fn+1=2Fn+1+Fn
Therefore:
F3k+3=2F3k+1+F3k
By the inductive hypothesis, F3k is divisible by 2, while 2F3k+1 is clearly divisible by 2, so F3k+3 is divisible by 2.
Conclusion: by mathematical induction, F3n is divisible by 2 for all n≥1.
Practice Problems
Exercise 1
Prove: 5n−1 is divisible by 4.
mathematical inductiondivisibility proof
Approach: Prove the divisibility by mathematical induction: first check the divisibility in the base case, then use the induction hypothesis to obtain the divisibility for n+1.
Steps:
Base case: when n=1, 51−1=4, divisible by 4.
Inductive hypothesis: assume 5k−1 is divisible by 4, i.e., 5k−1=4m
Inductive step:
5k+1−1=5⋅5k−1=5(5k−1)+5−1=5×4m+4=4(5m+1)
Conclusion: by mathematical induction, 5n−1 is divisible by 4.
Answer: By mathematical induction, 5n−1 is divisible by 4.
Exercise 2
Prove: n5−n is divisible by 5.
mathematical inductiondivisibility proof
Approach: Prove the divisibility by mathematical induction: first check the divisibility in the base case, then use the induction hypothesis to obtain the divisibility for n+1.
Steps:
Base case: when n=1, 15−1=0, divisible by 5.
Inductive hypothesis: assume k5−k is divisible by 5.