Divisibility

In this article we will do a proof using mathematical induction. Mathematical induction is a special way to prove things, it is a mathematical proof technique. It is typically used to prove that a property holds true for all natural numbers (0,1,2,3,4, …) .

When doing a proof by induction, you will need 2 main components, your base case, and your induction step, and 1 optional step called the induction hypothesis. The base case shows that the statement is true for the first natural number, and the induction step shows that the statement is true for the next one. As for the induction hypothesis, it’s your assumption that the statement is true for some arbitrary value.

Here we will do a proof of divisibility. When we say a number ‘a’ divides a number ‘b’ , we are just stating that b = a * C , where C is some constant.
a divides b can be written mathematically as a | b . So a is a factor of b.

a | b → b = a * C

For example if I say 5 divides 10 or 5| 10, then what I am stating is 10=5*C, where C= 2. So now we get 10= 5 * 2. Let’s get started with an example problem.

If you would like to see a video explaining the steps below, you can click on the link here, or watch the video above.

Problem:

Prove that 8 | 3^(2n) — 1 using induction for any integer value ’n’ ,
where n ≥ 0.

First we need our base case to prove that the statement holds true for some natural number n. Usually n=0 or n=1.

Base Case: Show that when n=0 the statement is true
3^(2n) — 1 = 3^(2 * 0) — 1 = 3^(0) — 1 = 1–1 = 0

and 8 | 0 is true, because 0= 8*C, in this case C=0
So the base case is true.

Induction Hypothesis: Assume for some arbitrary value ‘k’ that the statement is true.

Assume 8 | 3^(2k) — 1 is true which implies 3^(2k) — 1 = 8C is true.

Induction Step: Prove if the statement is true or assumed to be true for any one natural number ‘k’, then it must be true for the next natural number.

So we must show or prove that 8 | 3^(2(k+1)) — 1, which implies
3^(2(k+1)) — 1 = 8B , where B is some constant.

Let’s start by solving the equation 3^(2(k+1)) — 1
3^(2(k+1)) — 1
= 3^(2k+2) — 1
= 3^(2k) * 3^(2) — 1
= 3^(2k) * 9 — 1
= 3^(2k) * 8 + 3^(2k) * 1 — 1
= 3^(2k) * 8 + 3^(2k) — 1
= 3^(2k) * 8 + 8C ← From our induction hypothesis
= 8(3^(2k) + C)
= 8B , where B= (3^(2k) + C), we know 3^(2k) + C is some constant because C is a constant and k is a natural number. Therefore B is a constant.

So we have proven that

8 | 3^(2n) — 1 is true.

Image for post
Image for post
Source: https://www.slideshare.net/showslidedump/51-induction

If you want to read up on more induction problems or Discrete Math topics in general a great book to easily learn and practice these topics is Practice Problems in Discrete Mathematics by Bojana Obrenic’, and Discrete Math Workbook: Interactive Exercises by James R. bush.

Image for post
Image for post
Practice Problems in Discrete Mathematics by Bojana Obrenic’
Image for post
Image for post
Discrete Math Workbook: Interactive Exercises by James R. bush

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Algortithm Analysis:

Image for post
Image for post

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store