Discrete Mathematics
Proof By Induction
Mathematical induction is a method of mathematical proof typically used to establish a given statement for all natural numbers.
Overview:
Proof by induction is done in two steps.
- The first step, known as the base case, is to prove the given statement for the first natural number
- The second step, known as the inductive step, is to prove that the given statement for any one natural number implies the given statement for the next natural number.
From these two steps, mathematical induction is the rule from which we infer that the given statement is established for all natural numbers. Mathematical induction, in some form, is the foundation of all correctness proofs for computer programs.
Steps for proving by induction Description
The simplest and most common form of mathematical induction infers that a statement involving a natural number n holds for all values of n. The proof consists of two steps:
- The basis (base case): prove that the statement holds for the first natural number n. Usually, n = 0 or n = 1.
- The inductive step: prove that, if the statement holds for some natural number n, then the statement holds for n + 1.
The hypothesis in the inductive step that the statement holds for some n is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for n + 1.
Whether n = 0 or n = 1 depends on the definition of the natural numbers. If 0 is considered a natural number, as is common in the fields of combinatorics and mathematical logic, the base case is given by n = 0. If, on the other hand, 1 is taken as the first natural number, then the base case is given by n = 1.
Proof By Induction Example:
1) Prove 1+2+...+n=n(n+1)/2 using a proof by induction
Basis: Let n=1: 1 = 1( 1+1)/2 = 1(2)/2 = 1 is true,
Induction Hypothesis: Assume n=k holds: 1+2+...+k=k(k+1)/2
Show n=k+1 holds: 1+2+...+k+(k+1)=(k+1)((k+1)+1)/2
I just substitute k with k+1 in the formula to get these lines. Notice that I write out what I want to prove.
Induction Step: Now I start with the left side of the equation I want to show and proceed using the induction hypothesis and algebra to reach the right side of the equation. 1+2+...+(k+1)=1+2+...+k+(k+1)
=k(k+1)/2 + (k+1) by the Induction Hypothesis
=(k(k+1)+2(k+1))/2 by 2/2=1 and distridution of division over addition
=(k+2)(k+1)/2 by distribution of multiplication over addition
=(k+1)(k+2)/2 by commutativity of multiplication (this is the answer we wanted from the hypothesis)
Proof By Induction Divisibility
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 following steps, 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.