Proofs

I greet you this day:

First: read the notes.
Second: view the videos.
Third: solve the questions/solved examples.
Fourth: check your solutions with my thoroughly-explained solutions.

Comments, ideas, areas of improvement, questions, and constructive criticisms are welcome. You may contact me.
If you are my student, please do not contact me here. Contact me via the school's system. Thank you.

Samuel Dominic Chukwuemeka (Samdom For Peace) B.Eng., A.A.T, M.Ed., M.S

Overview

Objectives

Vocabulary Words

Prerequisites

(1.) Factoring

Introduction

Definitions

A natural number is any positive integer.
It is also known as a counting number. It is a number you can count.
It does not include zero.
It does not include the negative integers.
It is not a fraction.
It is not a decimal.

A whole number is any nonnegative integer.
It includes zero and the positive integers.
It does not include the negative integers.
It is not a fraction.
It is not a decimal.

An integer is any whole number or its opposite.
Integers include the whole numbers and the negative values of the whole numbers.

Ask students to explain:
(1.) The difference between a positive integer and a nonnegative integer
(2.) The difference between a negative integer and a nonpositive integer

Show/Hide Answer

A rational number is any number that can be written as a fraction where the denominator is not equal to zero.
You can also say that a rational number is a ratio of two integers where the denominator is not equal to zero.
A rational number is a number that can be written as: $${c\over d}$$ where $c, d$ are integers and $d \neq 0$
A rational number can be an integer.
It can be a terminating decimal. Why?
It can be a repeating decimal. Why?
It cannot be a non-repeating decimal. Why?

Ask students to tell you what happens if the denominator is zero.

An irrational number is a number that cannot be expressed as a fraction, terminating decimal, or repeating decimal.
When you compute irrational numbers, they are non-repeating decimals.

A real number is any rational or irrational number.
It includes all numbers that can be found on the real number line.

An even number is any integer that is divisible by $2$ without a remainder.
These includes zero and numbers that are multiples of $2$.
Examples include: $2, 4, 6, 8, 10, 12, 70, 84$, etc.

Student: Is zero an even number?
Teacher: Yes, $0$ is an even number because it is divisible by $2$ without a remainder.
$0 \div 2 = 0$

In most contexts, we see even numbers as positive numbers. However, even numbers can also be negative.
Examples include: $-2, -4, -6, -8, -10, -12, -70, -84$, etc.

An integer say $m$ is even if $m = 2 * n$ for some integer $n$

An odd number is any integer that is not a multiple of $2$.
Examples include: $1, 3, 5, 7, 9, 75$, etc.
In most contexts, we see odd numbers as positive numbers. However, odd numbers can also be negative.
Examples include: $-1, -3, -5, -7, -9, -75$, etc.

An integer say $m$ is odd if $m = 2 * n + 1$ for some integer $n$

Factors and Multiples
A number say $c$ is a factor of another number say $d$ if $c$ can divide $d$ without a remainder.
A number say $d$ is a multiple of another number say $c$ if $d$ can be divided by $c$ without a remainder.
This implies that:
If $c$ is a factor of $d$, then $d$ is a multiple of $c$

$ Say: \\[3ex] 2 * 3 = 6 \\[3ex] 2\:\:is\:\:a\:\:factor\:\:of\:\:6 \\[3ex] 3\:\:is\:\:a\:\:factor\:\:of\:\:6 \\[3ex] 6\:\:is\:\:a\:\:multiple\:\:of\:\:2 \\[3ex] 6\:\:is\:\:a\:\:multiple\:\:of\:\:3 \\[3ex] NOTE: \\[3ex] 1\:\:is\:\:a\:\:factor\:\:of\:\:Everything \\[3ex] Everything\:\:is\:\:a\:\:multiple\:\:of\:\:1 \\[3ex] 2\;\;is\;\;a\;\;factor\;\;of\;\;all\;\;even\;\;numbers \\[3ex] All\;\;even\;\;numbers\;\;are\;\;multiples\;\;of\;\;2 \\[3ex] $ An integer say $c$ is a factor of another integer say $d$ if $d = some\;\;integer * c$
An integer say $d$ is a multiple of another integer say $c$ if $d = some\;\;integer * c$

A prime number is a whole number greater than $1$, which is divisible by only $1$ and itself without a remainder.
Let us look at a prime number in another way...in terms of Factors and Multiples

A prime number is a number whose factors are only $1$ and itself.
In other words, for a prime number: the only factors are $1$ and that number. No other number is a factor.
Examples include: $2, 3, 5, 7, 11, 13, 17, 19$, etc.

A perfect square is the square of a rational number.
Examples include: $1, 4, 9, 16, 25, 36$, etc.

$ 1^2 = 1 \\[3ex] 2^2 = 4 \\[3ex] 5^2 = 25 $

A perfect cube is the cube of a rational number.
Examples include: $1, 8, 27, 64, 125$, etc.

$ 1^3 = 1 \\[3ex] 2^3 = 8 \\[3ex] 5^3 = 125 $

A perfect number is a positive integer that is equal to the sum of its proper positive divisors.
Proper positive divisors refers to all divisors excluding that number.
Examples include: $6, 28$, etc.

$ Proper\:\: divisors\:\: of\:\: 6 = 1, 2, 3 \\[3ex] 1 + 2 + 3 = 6 \\[3ex] Proper\:\: divisors\:\: of\:\: 28 = 1, 2, 4, 7, 14 \\[3ex] 1 + 2 + 4 + 7 + 14 = 28 $

An abundant number is a positive integer in which the sum of its proper positive divisors is greater than the number.
Proper positive divisors refers to all divisors excluding that number.
An abundant number is also called an excessive number.
Examples include: $12, 18$, etc.

$ For\:\: 12 \\[3ex] Proper\:\: divisors\:\: of\:\: 12 = 1, 2, 3, 4, 6 \\[3ex] Sum = 1 + 2 + 3 + 4 + 6 = 16 \\[3ex] 16 \gt 12 \\[5ex] For\:\: 18 \\[3ex] Proper\:\: divisors\:\: of\:\: 18 = 1, 2, 3, 6, 9 \\[3ex] Sum = 1 + 2 + 3 + 6 + 9 = 21 \\[3ex] 21 \gt 18 $

Two numbers are amicable (amicable numbers) if each is the sum of the proper divisors of the other.
Examples are: $220\:\:and\:\:284$, $5050\:\:and\:\:5564$, etc.

$ Proper\:\:divisors\:\:of\:\:\color{red}{220} = 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 \\[3ex] 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = \color{red}{284} \\[3ex] Proper\:\:divisors\:\:of\:\:\color{blue}{284} = 1, 2, 4, 71, 142 \\[3ex] 1 + 2 + 4 + 71 + 142 = \color{blue}{220} $

Proof by Mathematical Induction

Mathematical Induction is a technique used to prove a formula or statement regarding well-ordered sets.
The steps are:
Where $n$ is the number of terms:
(1.) Initial Step or Basis Step: Test for $n = 1$
In other words, show that the formula works for the first term

(2.) Induction Hypothesis: Assume the formula works for some members of the set, say $k$
Let $n = k$

(3.) Induction Step: Assume the formula works for the next member of the set: $k + 1$
Let $n = k + 1$

These are the steps...in a literal sense
Test the formula for the first guy to see if it works. $n = 1$
If it works, test it for the second guy: $n = 2$ and preferably the third guy: $n = 3$....my prefereence.
If the formula works for the second and third guys, test it for some guys in the set: $n = k$.
Then, test it for the next guy that comes after some guys: $n = k + 1$

Example $1$: Prove that the formula works for the set of positive integers.
$2 + 6 + 10 + ... + (4n - 2) = 2n^2$

Steps	$LHS$	$RHS$
	$2 + 6 + 10 + ... + (4n - 2)$	$2n^2$
Initial Step Test for $n = 1$	First term: $2$	$2(1)^2$ $2(1)$ $2$
The initial step works
Optional testing Test for $n = 2$	First term + Second term: $2 + 6$ $8$	$2(2)^2$ $2(4)$ $8$
Optional testing Test for $n = 3$	First term + Second term + Third term: $2 + 6 + 10$ $18$	$2(3)^2$ $2(9)$ $18$
The optional testing works
Induction Hypothesis Assume $n = k$ This is the $kth$ term $2 + 6 + 10 + ... + (4k - 2) = 2k^2...eqn.(1)$
Induction Step Assume $n = k + 1$ This is the $(k + 1)st$ term $2 + 6 + 10 + ... + (4k - 2) + [4(k + 1) - 2] = 2(k + 1)^2...eqn.(2)$
Induction Step	$\color{red}{2 + 6 + 10 + ... + (4k - 2)} + [4(k + 1) - 2]$ From $\color{red}{eqn. (1)}$, substitute: $\color{red}{2k^2} + 4(k + 1) - 2$ $2k^2 + 4k + 4 - 2$ $2k^2 + 4k + 2$ $2(k^2 + 2k + 1)$ $2(k + 1)^2$	$2(k + 1)^2$
$LHS = RHS$ The formula is proved.

References

Chukwuemeka, S.D (2019, April 30). Samuel Chukwuemeka Tutorials - Math, Science, and Technology. Retrieved from https://www.samuelchukwuemeka.com

Johnsonbaugh, R. (2019). Discrete Mathematics. Pearson.

Rosen, K. H. (2019). Discrete Mathematics and Its Applications. New York: McGraw-Hill Education.