Assiut University
قومية كلية
ل معتمدة من الهيئة ال عتماد
ضمان جودة التعليم واال
Course Title: Discrete Structures
Course Code: CS201
Prof. Dr. Khaled F. Hussain
Proof by induction
• Proof by induction is a powerful technique used to prove
statements about sequences or structures that are defined
recursively. To prove that P(n) is true for all positive integers n,
where P(n) is a propositional function, we complete two steps:
• Base Step :
• We verify that P(1) is true.
• Inductive Step:
• We show that the conditional statement P(k) → P(k + 1) is true for all positive integers k.
• Conclusion:
• If the statement is true for the base case and for all k+1 whenever it is true for k, then
it is true for all values greater than or equal to the base case.
Proof by induction (Cont.)
• Expressed as a rule of inference, this proof technique can be stated as:
(P (1) ∧ ∀k(P(k) → P(k + 1))) → ∀nP (n)
Proof by induction (Cont.)
• Example: For all positive integers n, 1 + 2 + 3 + ... + n = n(n+1)/2.
• Proof by induction:
• Base case: For n = 1, 1 = 1(1+1)/2, which is true.
• Inductive step: Assume the statement is true for n = k: 1 + 2 + 3 + ... + k =
k(k+1)/2. Now, we need to prove it's true for n = k+1:
1 + 2 + 3 + ... + k + (k+1) = k(k+1)/2 + (k+1)
Simplifying the right side: (k+1)(k+2)/2
• Therefore, the statement is true for n = k+1.
Proof by induction (Cont.)
• Example: Use mathematical induction to show that
1 + 2 + 22 +· · ·+2n = 2n+1 − 1 for all nonnegative integers n.
• Proof by induction: Solution: Let P(n) be the proposition that 1 + 2 + 22 +· · ·+2n = 2n+1 − 1 for the integer n.
• BASIS STEP: P(0) is true because 20 = 1 = 21 − 1.
• INDUCTIVE STEP: We assume that P(k) is true for an arbitrary nonnegative integer k. That is, we assume that
1 + 2 + 22 +· · ·+2k = 2k+1 − 1.
• We must show that when we assume that P(k) is true, then P(k + 1) is also true. That is, we must show that
1 + 2 + 22 +· · ·+2k + 2k+1 = 2(k+1)+1 − 1 = 2k+2 − 1
assuming the inductive hypothesis P(k). Under the assumption of P(k), we see that
1 + 2 + 22 +· · ·+2k + 2k+1 = (1 + 2 + 22 +· · ·+2k) + 2k+1
= (2k+1 − 1) + 2k+1 using IH
= 2 · 2k+1 − 1
= 2k+2 − 1.
• We have completed the inductive step.
Strong induction
• Strong induction is a mathematical proof technique that extends
the principle of mathematical induction. Strong induction allows
you to assume that the statement holds for all values up to a
particular value.
• The Principle of Strong Induction
1.Base Case: Prove that the statement is true for the base case (often the
smallest possible value).
2.Inductive Step: Assume that the statement is true for all values from the
base case up to and including a particular value, k.
3.Inductive Conclusion: Use the assumption from step 2 to prove that the
statement is also true for the next value, k+1.
Strong induction (Cont.)
• Example: Proving the Fibonacci Number Formula
The Fibonacci numbers are defined recursively as follows:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n ≥ 2
• We can prove the following formula for the nth Fibonacci number
using strong induction:
F(n) = [(1 + √5)/2]^n - [(1 - √5)/2]^n / √5
Strong induction (Cont.)
• Base Cases:
• For n = 0: F(0) = 0, which matches the formula.
• For n = 1: F(1) = 1, which matches the formula.
• Inductive Step: Assume that the formula holds for all values from 0 to k, where k ≥ 1.
• Inductive Conclusion: We need to prove that the formula holds for k+1. Using the recursive definition of Fibonacci numbers:
• F(k+1) = F(k) + F(k-1)
• By the inductive hypothesis, we can substitute the formula for F(k) and F(k-1):
• F(k+1) = [(1 + √5)/2]^k - [(1 - √5)/2]^k / √5 + [(1 + √5)/2]^(k-1) - [(1 - √5)/2]^(k-1) / √5
• Simplifying and factoring, we can show that this expression is equivalent to the formula for F(k+1).
• Therefore, by strong induction, the formula holds for all non-negative integers n.
Recursive Definitions
• Recursively Defined Functions
• BASIS STEP: Specify the value of the function at zero.
• RECURSIVE STEP: Give a rule for finding its value at an integer from its values at smaller integers.
• Example: Suppose that f is defined recursively by
f (0) = 3,
f (n + 1) = 2f (n) + 3. Find f (1), f (2), f (3), and f (4).
• Solution: From the recursive definition it follows that
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.
Recursive Definitions (Cont.)
• Example: Give a recursive definition of an, where a is a nonzero real number and
n is a nonnegative integer.
• Solution: The recursive definition contains two parts. First a0 is specified, namely, a0 = 1. Then
the rule for finding an+1 from an, namely, an+1 = a · an, for n = 0, 1, 2, 3, . . . , is given. These two
equations uniquely define an for all nonnegative integers n.
Recursive Algorithms
• An algorithm is called recursive if it solves a problem by reducing it to an instance of the same problem with
smaller input.
• Example: Give a recursive algorithm for computing n!, where n is a nonnegative integer.
procedure factorial(n: nonnegative integer)
if n = 0 then return 1
else return n · factorial(n − 1)
Recursive Algorithms (Cont.)
• Example: Give a recursive algorithm for computing an, where a is a nonzero real number and n is a
nonnegative integer.
procedure power(a: nonzero real number, n: nonnegative integer)
if n = 0 then return 1
else return a · power(a, n − 1)
Recursive Algorithms (Cont.)
• Example: Give a recursive algorithm for computing the greatest common divisor of two nonnegative integers a and
b with a < b.
procedure gcd(a, b: nonnegative integers with a < b)
if a = 0 then return b
else return gcd(b mod a, a)
• We illustrate the workings of the function with a trace when the input is a = 5, b = 8.
• gcd(5, 8) = gcd(8 mod 5, 5) = gcd(3, 5).
• gcd(3, 5) = gcd(5 mod 3, 3) = gcd(2, 3)
• cd(2, 3) = gcd(3 mod 2, 2) = gcd(1, 2)
• gcd(1, 2) = gcd(2 mod 1, 1) = gcd(0, 1).
• Finally, to find gcd(0, 1) it uses the first step with a = 0 to find that gcd(0, 1) = 1.
• Consequently, the function finds that gcd(5, 8) = 1.
Recursive Algorithms (Cont.)
• Example: Give a recursive algorithm for Fibonacci Numbers
procedure fibonacci(n: nonnegative integer)
if n = 0 then return 0
else if n = 1 then return 1
else return fibonacci(n − 1) + fibonacci(n − 2)
Recursive Algorithms (Cont.)
• An Iterative Algorithm for Computing Fibonacci Numbers
• This algorithm requires far less computation than does the recursive algorithm.
procedure iterative fibonacci(n: nonnegative integer)
if n = 0 then return 0
else
x := 0
y := 1
for i := 1 to n − 1
z := x + y
x := y
y := z
return y
