1/17/2019

Tassos Dimitriou

CpE-203
Discrete Structures

Set 6

Prof. Tassos Dimitriou

Computer Engineering Department

Kuwait University

CpE-203: Discrete Structures 1

Tassos Dimitriou

Outline
Induction
 Definition
 Examples
 Wrong applications

CpE-203: Discrete Structures 2

1
 1/17/2019

Tassos Dimitriou

Induction
The principle of mathematical
induction is a useful tool for proving
that a certain predicate is true for all
natural numbers.

It cannot be used to discover

theorems, but only to prove them.

Example:
 Suppose that we have an infinite
ladder.
 What does it take to make sure that we
can reach every step on this ladder?

CpE-203: Discrete Structures 3

Tassos Dimitriou

Induction
If we have a propositional function P(n), and we want to prove
that P(n) is true for any natural number n, we do the following:
• Show that P(0) is true.
(Basis step)
• Show that if P(k) then P(k + 1) for any kN.
(Inductive step)
• Then P(n) must be true for any nN.
(Conclusion)

• How can this be stated as a rule of inference?

CpE-203: Discrete Structures 4

2
 1/17/2019

Tassos Dimitriou

Induction
Let P(n) be the proposition that
domino n is knocked over.
 If the first domino is knocked over—
i.e., if P(1) is true—and
 if, whenever the kth domino is
knocked over, it also knocks the
(k + 1)st domino over—i.e., if
P(k) → P(k + 1) is true for all
positive integers k—
 then all the dominoes are
knocked over.

CpE-203: Discrete Structures 5

Tassos Dimitriou

Good or bad?
The good thing about mathematical induction is that it can be
used to prove a conjecture once it is has been made (and is
true).

The bad thing about it is that it cannot be used to find new

theorems.
 You can prove a theorem by mathematical induction even if you
do not have the slightest idea why it is true!

CpE-203: Discrete Structures 6

3
 1/17/2019

Tassos Dimitriou

Example 1
Show that n < 2n for all positive integers n.

Let P(n) be the proposition “n < 2n.”

1. Show that P(1) is true.

(Basis step)

 P(1) is true, because 1 < 21 = 2.

CpE-203: Discrete Structures 7

Tassos Dimitriou

Example 1 (cont.)
2. Show that if P(k) is true, then P(k + 1) is true.
(Inductive step)

 Assume that k < 2k is true.

 We need to show that P(k + 1) is true, i.e. k + 1 < 2k+1. How?

 We will use our assumption that k < 2k to get the inequality for
k + 1 as follows:
k + 1 < 2k + 1  2k + 2k = 2k+1

 Therefore, if k < 2k then k + 1 < 2k+1

3. Hence P(n) is true for every positive integer.

CpE-203: Discrete Structures 8

4
 1/17/2019

Tassos Dimitriou

Example 2
“Gauss” formula: 1 + 2 + … + n = n(n + 1)/2

1. Show that P(1) is true.

(Basis step)

 For n = 1 we get 1 = 1. So, P(1) is true.

CpE-203: Discrete Structures 9

Tassos Dimitriou

Example 2 (cont.)
2. Show that if P(k) then P(k + 1) for any nN. (Inductive
step)

 We will use our assumption about P(k) to prove P(k+1)

1 + 2 + … + k + (k + 1) = k(k + 1)/2 + (k + 1)
= (k + 1) (k/2 + 1)
= (k + 1) (k + 2)/2
= (k + 1) ((k + 1) + 1)/2

3. Hence, P(n) must be true for any nN. (Conclusion)

1 + 2 + … + n = n (n + 1)/2 is true for all nN.

CpE-203: Discrete Structures 10

5
 1/17/2019

Tassos Dimitriou

More examples
Use mathematical induction to show that

1 + 2 + 22 +· · ·+2n = 2n+1 − 1

CpE-203: Discrete Structures 11

Tassos Dimitriou

Using Induction the wrong way

To uncover errors in proofs by mathematical induction,
remember that in every such proof, both the basis step and
the inductive step must be done correctly.

CpE-203: Discrete Structures 12

6
 1/17/2019

Tassos Dimitriou

Guidelines for correct proofs

CpE-203: Discrete Structures 13

Tassos Dimitriou

Some more practice

Prove by induction that the sum of the first n odd numbers is
equal to n2, i.e.

For the Fibonacci numbers show that

and

Show that a set of n 2 elements has n(n – 1)/2 subsets

with 2 elements.

CpE-203: Discrete Structures 14

7
 1/17/2019

Tassos Dimitriou

Recursive Definitions
Recursion is a principle closely related to mathematical
induction.

In a recursive definition, an object is defined in terms of itself.

We can recursively define sequences, functions and sets.

CpE-203: Discrete Structures 15

Tassos Dimitriou

Recursively Defined Sequences

Example:

The sequence {an} of powers of 2 is given by an = 2n for n = 0,

1, 2, … .

The same sequence can also be defined recursively:

 a0 = 1
 an+1 = 2an for n = 0, 1, 2, …

When we define a sequence recursively by specifying how

terms of the sequence are found from previous terms, we can
use induction to prove results about the sequence..

CpE-203: Discrete Structures 16

8
 1/17/2019

Tassos Dimitriou

Recursively Defined Functions

We can use the following method to define a function with the
natural numbers as its domain:

1. Specify the value of the function at zero.

2. Give a rule for finding its value at any integer from its values at
smaller integers.

Such a definition is called recursive or inductive definition.

CpE-203: Discrete Structures 17

Tassos Dimitriou

Recursively Defined Functions

Example:

 f(0) = 3
 f(n + 1) = 2f(n) + 3

f(0) = 3
f(1) = 2f(0) + 3 = 23 + 3 = 9
f(2) = 2f(1) + 3 = 29 + 3 = 21
f(3) = 2f(2) + 3 = 221 + 3 = 45
f(4) = 2f(3) + 3 = 245 + 3 = 93

What is this function equal to?

CpE-203: Discrete Structures 18

9
 1/17/2019

Tassos Dimitriou

Recursively Defined Functions

How can we define recursively the factorial function f(n) = n! ?
Answer
 f(0) = 1
 f(n + 1) = (n+1)f(n)

A famous example: The Fibonacci numbers

 f(0) = 0, f(1) = 1
 f(n) = f(n – 1) + f(n - 2)

f(0) = 0, f(1) = 1 f(5) = f(4) + f(3) = 3 + 2 = 5

f(2) = f(1) + f(0) = 1 + 0 = 1 f(6) = f(5) + f(4) = 5 + 3 = 8
f(3) = f(2) + f(1) = 1 + 1 = 2 f(7) = f(6) + f(5) = 8 + 5 = 13
f(4) = f(3) + f(2) = 2 + 1 = 3 ….

CpE-203: Discrete Structures 19

Tassos Dimitriou

CpE-203: Discrete Structures 20

10