Proof By Induction

randerson112358

Apr 20, 2018·4 min read

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 — 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.

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 )