ECNG2013
LECTURE 8
Proof Technique
Mathematical Induction
Consider the following lists of numbers
1. 5, 7, 9, 11, 13, __
2. 1, 9, 17, 25, 33, 41, __
3. 1, 4, 9, 16, 25, 36, __
4. 1, 2, 6, 24, 120, 720, __
5. 1 2 , 2 3 , 3 4 , 4 5 , __
What is the next number in each of the following list?
Observe
(a) Each term is related to the previous term by arithmetical operations
(b) Each term can be described relative to its position in the sequence
Definition
A recursive formula for a sequence is one where each term is described in relation
to a previous term or terms of the sequence. The description must include enough
information on how the list begins
Examples
a 5
1. 1
a 1
2. 1
a 1
3. 1
a n a n 1 2
a n a n 1 8
a n a n 1 8
Definition
An explicit or closed formula for a sequence is a formula where each term is
described in relation to its position in the list
Examples
a 2n 3
1. n
3. a n n 2
4.
a n n!
Find an explicit formula for the sequence in #5
Mathematical Induction
Inductive reasoning is fundamental to the fundamental or observational sciences. It
is the inference of an event from past events.
The main mathematical tool used to verify conjectures about patterns governing the
arrangement of terms in a sequence is mathematical induction. For example, we
may use the fact that some property is true for integers 1 100 to prove that the
same property is true for the integer 101.
Method of Proof by Mathematical Induction
Consider a statement of the form , For all integers n a , a property P(n) is true.
To prove such a statement, perform the following two steps.
Step 1 (basis step)
Show that the property is true for n=a
Step 2 (Inductive step)
Show that for all integers k a , if the property is true for n=k , then it is true for
n=k+1
Example
Use Mathematical Induction to prove that
1 + 2 + 3 + ------- + n = n(n+1)/2 for all integers n 1
Proof
Let P(n) be the statement 1 + 2 + 3 + ------- + n = n(n+1)/2
1 = 1(1+1)/2
Hence statement is true for n=1
Assume that the statement is true for n = k i.e P(k) is true
Hence 1 + 2 + 3 + ------- + k = k(k+1)/2
1 + 2 + 3 + ------- + k + (k+1) = k(k+1)/2 + k +1 since P(k) is true
k (k 1) 2(k 1) (k 2)(k 1)
(k 1)((k 1) 1) / 2
2
2
Hence statement is true for n=k+1
It follows by the principle of mathematical induction that P(n) is true for all integers
n 1
Example
Use mathematical induction to prove that for all integers n 3, 2n 1 2 n
Proof
When n=3,
2(3) + 1 = 7 < 8 = 2 3
Hence statement is true for n = 3
Assume statement is true for n = k
2k 1 2 k
when n k 1
2( k 1) 1 2k 3 ( 2k 1) 2 2 k 2
Since statement is true for n = k
2(k 1) 1 2 k 21 2 k 2 k wherek
2(k 1) 1 2(2 k ) 2 k 1
Hence the statement is true for n = k+1
Therefore the statement is true by the principle of mathematical induction
Strong Mathematical Induction
Many textbooks refer to the induction used in the earlier examples as weak or
ordinary mathematical induction. Here, we only used the immediate prior statement
P(k) after basis step.
In so-called strong mathematical induction, the basis step may contain proofs for
several initial values, and in the inductive step, the truth of the statement P(n) is
assumed not only true for n=k-1, but for all values through k-1. Following this the
truth of P(k) is proved.
Principle of Strong Mathematical Induction
Let P(n) be a property that is defined for integers n, and let a and b be fixed
integers with a b .
Suppose the following two statements are true.
1. P(a), P(a+1), ., and P(b) are all true. (basis step)
2. For any integer k > b, if P(i) is true for all integers i, with a i k , then P(k) is
true. (Inductive step). Then the statement is true for all integers n a , P(n) is
true.
Note:
The two types of induction (strong and ordinary) are equally valid as any statement
that can be proved with ordinary mathematical induction can also be proved with
strong mathematical induction.
Example
Prove that every natural number has a binary representation
Prof
Let P(n) be the statement that n has a binary representation.
0 02 ,
1 12
Hence statement is true for n=0 and n=1
Assume that P(i) is true for all 0 i k
Consider n=k .
By the division rule, there are integers q (the quotient) and r (the remainder) such
that
k = 2q+r where r=0 or r=1.
Since q < k, we know that q has a binary representation which can be expressed as
s
or q bi 2 i
bs bs 1 .........b2 b1b0
i 0
i 0
i 0
Now k 2q r 2( bi 2 i ) r ( bi 2 i 1 ) r
k bs bs 1 ..........b2 b1b0 r
Hence statement is true for n = k.
It follows by the principle of Mathematical induction that the statement is true.
