1

Week 1-2
Discrete Mathematics
for IT
LESSON 1, TOPIC 3: PROOF
TECHNIQUES
 2
Proof Techniques

LESSON OBJECTIVES:
❑ Introduce proof methods: direct proof, proof by
contrapositive, proof by contradiction, and
mathematical induction.
❑ Walk through examples of using these techniques to prove
statements in discrete mathematics.
❑ Emphasize the role of proofs in validating algorithms and
ensuring correctness in IT applications.
 3
Proof Techniques

Common proof methods used in mathematics:

❑ direct proof
❑ proof by contrapositive
❑ proof by contradiction
❑ mathematical induction
 4
Direct Proof Technique

Direct Proof:

A direct proof is a straightforward method where you start with

the given premises and logically deduce the conclusion using a
series of valid logical steps. This method involves showing that if the
premises are true, then the conclusion must also be true. It's often
used for proving statements that follow a clear cause-and-effect
relationship.
 5
Direct Proof Technique

► Example 1: Direct Proof Statement: If a positive integer is

even, then its square is also even.
► Proof: Let's assume that 'n' is a positive even integer. By
definition, an even integer can be written as 'n = 2k’ for some
integer 'k'. Now, let's consider the square of 'n’: n2=(2k)2=4k2.
► Since '4k^2’ is also divisible by 2 (it's twice '2k^2’), 'n^2' is an
even number. Thus, we've shown that if 'n' is even, then 'n^2' is also
even.
 6
Proof by Contrapositive Technique

Proof by Contrapositive:
Proof by contrapositive is a technique where you prove a statement by
considering the contrapositive, which is the negation of the
conclusion followed by the negation of the hypothesis. If you
can show that the contrapositive is true, then the original statement
must also be true. This method is particularly useful when proving
statements involving implications.
 7
Proof by Contrapositive Technique

► Example 2: Proof by Contrapositive Statement: If n^2 is an even

integer, then n is also an even integer.
► Proof: To prove this by contrapositive, we'll show that if 'n' is an odd
integer, then 'n^2' is also odd. Assume 'n' is odd, so 'n = 2k + 1' for
some integer 'k’. Then, n2=(2k+1)2 =4k2 + 4k+1=2(2k2+2k)+1. Since
'2k^2 + 2k' is an integer, 'n^2' is of the form '2m + 1', where 'm' is an
integer. Hence, 'n^2' is odd, which completes the proof.
 8
Proof by Contradiction Technique

Proof by Contradiction:
Proof by contradiction involves assuming the opposite of what
you want to prove and then deriving a logical contradiction from
those assumptions. If you can show that assuming the opposite leads
to an inconsistency or contradiction, then the original statement must
be true. This method is often used for proving statements that are
difficult to tackle directly.
 9
Proof by Contradiction Technique

► Example Proof by Contradiction Statement: There is no

smallest
3: positive rational number.
► Proof: Let's assume the opposite, that there exists a
smallest positive rational number, say 'r'. But we can always find a
smaller positive rational number by considering 'r/2', which is also
positive and smaller than 'r'. This contradicts the assumption that
'r' is the smallest positive rational number. Thus, our assumption is
false, and there is no smallest positive rational number.
 10
Proof by Contradiction Technique

► Examples of Rational Numbers

• Number 9 can be written as 9/1 where 9 and 1 both are integers.
• 0.5 can be written as ½, 5/10 or 10/20 and in the form of all termination
decimals.
• √81 is a rational number, as it can be simplified to 9 and can be
expressed as 9/1.
• 0.7777777 is recurring decimals and is a rational number
 11
Mathematical Induction Technique

Mathematical Induction:
used to prove statements that are true for all natural numbers. There
are two steps in mathematical induction: the base case and the
inductive step. In the base case, you prove that the statement
holds for the smallest value (often 0 or 1). In the inductive step, you
assume that the statement is true for some arbitrary value 'n' and then
show that it must also be true for 'n + 1'. This process creates a chain
of implications that proves the statement for all natural numbers.
 12
Mathematical Induction Technique

Example 4: ► Proof:
Mathematical Induction • Base Case:
Statement: For all positive • When 'n = 1', the left side is 1
integers 'n', 1 + 3 + 5 + ...
and the right side is 12 = 1
+
which matches.
(2n - 1) = n^2.
 13
Mathematical Induction Technique

Example 4: ► Proof:
• Inductive Step: Assume the statement
Mathematical Induction is true for some positive integer 'k’:
Statement: For all positive 1+3+5+…+(2k−1)=k2. We want to prove
integers 'n', 1 + 3 + 5 + ... it's true for 'k + 1’: 1+3+5+…
2
+(2k−1)+(2(k+1)−1)=(k+1) .
+ Adding 2(k+1)−1 to both sides, we get:
(2n - 1) = n^2. k2+2(k+1)−1=k2+2k+1=(k+1)2. Thus, the
statement holds for 'k + 1', completing the
inductive step.
 14
Important Tips

✔ Direct Proof: Straightforward logical deductions from given premises

to reach a conclusion.
✔ Proof by Contrapositive: Proving a statement by showing that its
contrapositive is true.
✔ Proof by Contradiction: Assuming the opposite of what's to be
proven and deriving a contradiction.
✔ Mathematical Induction: Proving statements for all natural numbers
through base case and inductive step reasoning.
 15
IT applications

► Proof techniques play a crucial role in the field of

discrete mathematics when it comes to validating algorithms
and ensuring correctness in IT applications.
► Here's how these proof methods are applied in this context:
 16
IT applications

Algorithm Validation:
Algorithms are step-by-step procedures designed to solve
specific problems. Before implementing an algorithm in a real-world
application, it's important to validate its correctness. This involves
ensuring that the algorithm produces the desired output for all
possible inputs. Proof methods help in this validation process by
providing rigorous mathematical evidence of an algorithm's correctness.
 17
IT applications

Ensuring Correctness:
IT applications often involve critical tasks such as data processing,
security, financial calculations, and more. Errors in these applications
can lead to serious consequences. By using proof techniques, one can
establish that algorithms and software components function correctly
under all possible scenarios. This helps prevent errors, bugs,
and vulnerabilities that could otherwise compromise the integrity
of the application.
 18
IT applications

Verifying Properties:
Proofs can be used to verify specific properties of algorithms or
software, such as termination (whether the algorithm will always
halt), correctness (whether the algorithm produces the expected
output), and efficiency (whether the algorithm performs within
acceptable time and resource limits). This is particularly important in
safety-critical systems where errors could lead to catastrophic
outcomes.
 19
IT applications

Complexity Analysis:
Discrete mathematics proof methods can also be applied to analyze
the time and space complexity of algorithms. Proving that an
algorithm has a certain time complexity helps in understanding its
efficiency and scalability. Such analyses are crucial in making
informed decisions about algorithm selection for specific applications.
 20
IT applications

Formal Verification:
Formal methods, which include proof techniques, are used to formally
verify that software or algorithms adhere to their specifications.
This involves proving that the implementation satisfies a given
set of requirements. Formal verification is used in safety-critical
systems, where mistakes can have dire consequences. Proofs help
ensure that the software behaves as intended and doesn't exhibit
unexpected behaviors.
 21
IT applications

Debugging and Troubleshooting:

Proofs can also be employed in debugging and troubleshooting
processes. When an unexpected behavior or bug arises, proof
techniques can be used to analyze the algorithm's logic and
pinpoint where the error occurred. This systematic approach can
save time and effort in identifying and resolving issues.
 22
Summary

Proof techniques from discrete mathematics provide a rigorous and

structured approach to ensuring the correctness and reliability of
algorithms and IT applications.

By using these techniques, developers and engineers can confidently

deploy software that performs as intended, avoids errors, and meets the
demands of modern technology and critical systems.