Discrete Mathematics

Proof By Induction

Mathematical induction is a method of mathematical proof typically used to establish a given statement for all natural numbers.

Proof by induction is done in two steps.

  1. The first step, known as the base case, is to prove the given statement for the first natural number
  2. 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.

Proof by Induction


Proof by Induction - Example 1

Download PDF

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:

  1. The basis (base case): prove that the statement holds for the first natural number n. Usually, n = 0 or n = 1.
  2. 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.

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 of Divisibility by induction


This is a proof by induction for divisibility

Download PDF

code here

Copyright © 2013, Everything Computer Science.