# Proof By Induction

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^(2**k+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.

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 )

# 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