Mathematicians know that different types of infinite sequences exist. Lets start off by discussing two different types of infinite sequences: countably infinite sequences and uncountably infinite sequences.

Countably Infinite Sets

Lets take a look at a small sample of the set of all binary strings. The set looks like the following:

0, 1, 00, 01, 10, 11, 000, 101, …

The set of all possible sets of binary strings is countably infinite. This is quite interesting because this means that the number of computer programs that can be written is also countable infinite. For the purpose of this example we can assume that a compiled program can be represented as a single binary string.

Uncountably Infinite Sets

To think about infinite sets that are uncountable, let us consider the following statement. The set of all problems that exist is uncountable. In other words, there is an infinite number of possible problems in the universe. Because there is a never ending number of problems, this means that there are problems which cannot be computed. This is because the number of programs that exist is countably infinite, but the number of problems is not.

The set of Natural Numbers

The notation N represents the set of natural numbers.

Some examples of subsets of N could be:

Θ, {1}, {2}, {1, 2, 3}, {2, 4, 6, 8, …}, {1, 3, 5, 7, 9, …}, {2, 3, 5, 7, 11, …}, and so on.

The notation 2^N represents the power set of N. The power set of N is uncountable.

We can prove that 2^N is uncountable.

Proof: Suppose, to the contrary, that 2^N is countably infinite. Then, there exists some countably infinite listing, say S1, S2, S3… of all possible subsets of the natural numbers of N. Consider the following chart.

Cantor’s Diagonalization

S = {1, 2, 3, …}

Define a set S as follows:

for each i = 1, 2, 3, ...
    if i ∈ Si, then i ∉ S
    if i ∉ Si, then i ∈ S

The set S is a subset of N but S ≠ Si for any i. In other words, S is not in the list of all possible subsets of N. Therefore 2^N is uncountable.

Future Writing

In my next post I will talk more about Cantor’s Denationalization within a three dimensional graph. I will also be introducing the continuum hypothesis which states that there is no set whose cardinality is strictly between that of the integers and the real numbers.

1. if n is even, then 3n² + 5 is odd.

n is even n = 2k

direct:

if n² + 8 is even, then n is even. n² is even if n is odd, then n² + 8 is odd n² = 2k n is odd . n = 2k + 1 . . . . n = 2(___) contrapositive

If A is an underlined subset of B, then A (upside down U) is an underlined subset of B (upside down U) C Assume A underlined subset B. direct

New Topic: 15 = 3 * 5

3 is a factor if 15 3 is a divisor of 15 15 is a multiple of 3 15 is divisible by 3

Definition: For integers a and b with b != 0, we say that b divides a if a = bc for some integer c. We write b|a

3 divides 15 because 15 = 3 * 5 3	15
5	15
2 /	15 (char needs to be replaced with a bar with a slash through it)

All of these statements mean the same thing:

b is a divisor of a
b is a factor of a
a is a multiple of b
a is divisiable by b

-3 divides 15 since 15 = (-3)(-5) 4|0 0 = 4 * 0 7|0 12|0 -42|0

not allowed: 0|0 because: 0 = 0 * x where x is not unique.

Example: Find all positive divisors of 12. 1, 2, 3, 4, 6, 12

1 * 12 = 12 2 * 6 = 12 3 * 4 = 12

Definition of a prime

1. A prime is any non-zero positive integer that is only divisible by 1 and itself.
2. A integer is prime if its only positive divisors are 1 and itself.
3. An integer p is prime if it has exactly two different positive divisors.
4. An integer n > 1 is prime if and only if for all positive integers r and s, if n = rs, then r = 1 or s = 1.

Primes 2, 3, 5, 7, 11, 13, 17…

Definition of a composit

1. An integer n > 1 is composit if it is not prime.
2. An integer n is composit if there exist integers a and b with 1 < a < n and 1 < b < n such that n = ab.
3. There exit positive integers r and s such that n = rs and r != 1 and s != 1.

Is 5377 prime? 2 /| 5377 3 /| 3577 5 + 3 + 7 + 7 = 22 3 /| 22 5 /| 5377 7 /| 5377 7 root(5377) root(5377) is roughly equal to 73

boolean isPrime(int n) {

    if (n <= 1) {
        // Fail fast if n is zero or negative
        return false;
    }

    for (int d = 2; d <= (int)Math.sqrt(n); d++) {
        if (n % d == 0) {
            return false;
        }
    }
    return true;
}

Result: For all n > 1, if n is not divisible by any positive integer that is greater than 1 and less than or equal to sqrt(n), then n is prime.

Proof: (by contrapositive) Let n > 1 be an integer. Assume n is composite. Then there exist integers r and s with 1 < r < n and 1 < s < n such that n = rs. Furthermore it is imposible for both r > sqrt(n) and s > sqrt(n) for otherwise n = rs > sqrt(n) * sqrt(n) = n. So either 1 < r <= sqrt(n) or 1 < s <= sqrt(n)> Thus n is divisible by a positive integer that is greater than 1 and less than of equal to sqrt(n).

The Sieve of Eratosthenes

History:

Def. An integer n > 1 is composit if and only if there exist positive integers r and s such that n = rs and r != 1 and s != 1.

Def. An integer n > 1 is prime if and only if for all positive integers r and s, if n = rs, then r = 1 or s = 1.

Prove or Disprove:

1. For every positive integer n, the integer 3n is composit.
   False (universally quantified –> disprove)
   Counter example: Let n = 1. Then 3n = 3 * 1 = 3, which is prime.

1. There exists an integer m such that m^2 - 1 is prime.
   True (existentially quantified –> proove)
   Proof: Let m = 2. Then m^2 - 1 = 2^2 -1 = 3, which is prime

1. For all positive integers n, 2n^2 + 4 is composite. Factor: 2n^2 + 4 = 2(n^2 + 2) True (universlly quantified), this expression can be factored into two statements, neither of which are composit. Proof: Let n be any positive integer. Then 2n^2 + 4 = 2(n^2 + 2). So 2 and n^2 + 2 are both integers. And 2 != 1, also n^2 + 2 >= 1^2 + 2 = 3. Thus n^2 + 2 != 1. Therefore 2n^2 + 4 is composite.

1. There exists a positive integer n such that n^2 + 3n + 2 is prime. False (existentialy quantified) we know this is false because n^2 + 3n + 2 = (n + 2)(n + 1) <– that factors to two expressions where neither is equal to 1 Prove: For all positive integers n, n^2 + 3n + 2 is composite. Disproof: Let n be a positive integer. Then n^2 + 2n + 2 = (n + 1)(n + 2). Observe n+ 1 and n+ 2are positive integers and n + 2 != 1 since n + 2 >= 3. Therefore n^3 + 3n + 2 is composite.

Summary:

Proove P => Q Direct proof: Assume P. Proove Q. Proof by contrapositive: Assume ~Q. Proove ~P.

Universal for all x, P(x) proof: Let x be arbitrary

True: (don’t argue from an example)

False: counter example let x = _____ Show ~P(x)

Existential there exists x such that

True: proof: Let x = _____ (okey to argue from an example)

False Disproof: For all x, ~P(x) Let x be arbitrary Proove ~P(x)

Def For integers a and b with b ≠ 0, we say that b divides a, written b|a if and only if a = b * c for some integer c.

2|10 because 10 = 2 * 5 and 5 ∈ ℤ.
4∤22 because 22 != 4 * c for any integer c there is no integer c such that 22 = 4c.

Properties of Divisibility

• Transative For integers a, b, c, if a|b and b|c, then a|c.

  Proof: Let a, b, c, be integers.
  Assume a|b and b|c.
  So b = a * c for some integer x and
  c = b * y for some integer y.
  Thus c = a * x * y = a(xy). Since x and y are integers
  we know xy is an integer.
  Thus a|c.

Divisibility Test

6|n <=> 2|n and 3|n
ab|c <= a|c and b|c
Notice: The use of the Walker Property in this example. Result: For integers a, b, c, if
a|c and b|c, then ab|c.
Proof: Let a, b, c be integers.
Assume a|b anf b|c.
Then c = ax and c = by for some integers x and y.
At this point we see that there was a problem in prooving this.
Counterexample: a = 2 b = 4 c = 12
2|12 and 4|14
2 * 4 = 8 and 8∤12.

Result: (Anti-Walker Property)
For integers a, b, c, if ab|c, then a|c and b|c.
Proof: Let a, b, c, be integers.
Assume ab|c. Then c = ab*x for some integer x.
Thus c = a(bx) and we know bx ∈ ℤ. So a|c.
Also c = b * (ax) and we know ax ∈ ℤ.
Thus b|c.

• True or False (proove or disproove)

  1. If a

     b and a

     c, then a

     bc.

  2. If a

     bc, then a

     b and a

     c.

  3. If a

     bc, then a

     b or a

     c.

  4. If a

     b and b

     d, then ac

     bd.

  5. If a

     b and c

     d, then a+c

     b+d.

• Therem: Any integer n > 1 is divisible by a prime number.

• For any integer n > 1, there exists a prime number p such that p

  n.

Examples:
n = 2 p = 2 2|2
n = 3 p = 3 3|3
n = 7 p = 7 7|7

p p p

p

Theorem: Unique Factorization Theorem - Given any integer n > 1, there exists a positive integer k and distinct prie numbers p1, p2, …, pk and positive integers e1, e2, …, ek such that n = p1, p2, …, pk and this factorization is unique (disreguarding the order of factors).

• Note: The number 1 is not prime.
• Cryptography
• RSA
• Note: A 200-digit number took 18 months and used over half a century of computing time.

Proof by Contradiction

Contradiction rule ~p => c (Where c is a contradiction)
Therefore P

Proof by Contradiction
Suppose, to the contrary, that p is false.
.
.
.
[Show some contradiction]
Therefore, P.

Example
Theorem: There is no greatest integer.
Suppose, to the contrary, that there is a greatest integer, say N.
However, N + 1 is an integer and N + 1 > N.
Threrfore, there is no greater integer.

Example
Theorem: There is no smallest positive real number.

Example
Theorem: The square root of 2 is irrational.
Suppose, to the contrary, that the square root of 2 is rational.
Then there exist integers a and b with b != 0 such that the square root of 2 != a/b and we assume that a/b is in lowest terms.
Squaring both sides, we have 2 = a^2/b^2 or 2b^2 = a^2.
Now since b^2 is an integer, 2b^2 is even.
Thus a^2 is even, which implies a is even.
Thus a = 2k for some integer k. It follows that 2b^2 = (2k)^2 = 4k^2.
So b^2 = 2k^2. Hence b^2 is even, implying b is even.
So b = 2l for some integer l. But this contradicts that a/b is in lowest terms.
Therefore the square root of 2 is irrational.

Alternate Example
Unique Factorization Theorem

Example
Lemma: For any integer a and prime p, if p|a, then p /| (a+1).
Proof: Suppose not. That there exists an integer a and a prime p such that p|a and p|(a+1).
Then a = pr for some integer r
and a+1 = ps for some integer s.
Subtracting, we get 1 = a + 1 = a = ps - pr = p(s-r).
Thus p|1. So p = 1 or p = -1.
This contridicts that p is prime (p >= 2).

Example
Theorem: There are infinately many primes.
Proof: Suppose to the contrary, that there are finitely many primes p1, p2, …, pk. Let a = p1, p2, …, pk. Notice that each pi divides a.
Thus pi /| (a+1). So the integer a+1 has no other prime divisors and thus must be prime.
But this contradicts that the list of p1, p2, …, pk contained all possible primes.

Proof by cases

Two integers m and n have the same parity if they are either both even or both odd.

Theorem: For every two integers m and n, 3m + 5 is even if and only if m and n have the same parity.

Proof (<=) Proove if m and n have the same parity, then 3m + 5n is even.
Assume m and n have the same parity.
Case 1: m and n are both even.
[Proove 3m + 5n is even]
Case 2: m and n are both odd.
[Proove 3m + 5n is even.]

(=>) Prove if 3m + 5n is even, then m and n have the same parity (by contrapositive).
Assume m and n have opposite parity.
Case 1: m is even and n is odd.
[Prove 3m + 5n is odd.]
Case 2: m is odd and n is even.
[Proove 3m + 5n is odd.]

Result: For any sets A, B, and C, (A-B) ⋃ (A-C) = A - (B ⋂ C)

Proof: First we show (A-B) ⋃ (A-C) ⊆ A - (B ⋂ C)
Let x ∈ (A-B) ⋃ (A-C).
Then x x ∈ A-B OR x ∈ A-C
Case 1: x ∈ A - B
[Show x ∈ A - (B ⋂ C)]
Case 2: x ∈ A - C
[Show x ∈ A - (B ⋂ C)]

Sequences

2, 4, 6, 8, 10, …
1, 2, 4, 8, 16, …
1/2, 2/3, 3/4, 4/5, …

A sequence is an ordered list of terms.

2, 4, 6, 8, …
1st, 2nd, 3rd, 4th, …
12, 22, 32, 42, …

A general (or explicit) formula for the nth term.

a_n = 2n

Notation

I want to write the shorthand version of: 1/2 + 2/3 + 3/4 + 4/5 + … see note sheet #9q34

Principle of Mathematical Induction

To proove statements of the form: “For all integers n >= 1, P(n).”

If 1) P(1) is true
and 2) the statement
“for all integers k >= 1, P(k) => P(k+1)”
is true

The metaphore for this is a ladder. If I can get the next rung, then I can get the the rung after that one.

To use the principle of Mathematical Induction

1. Proove the statement is true for n=1 (base step or base case).
2. Let k >= 1 be some arbitrary integer.
3. Assume P(k). This is called the inductive hypothesis.
4. Proove P(k+1). This is called the inductive step.
5. Therefor, P(n) for all n >= 1.

Continued on paper notes: #zrepryt

Statement of Mathematical Induction

Let a be some fixed non-negative integer. Let P(n) be a statement define d for all integers n >= a. If P(a) is true …

Conjecture: Using 3 cent coins and 5 cent coins, any change amount n >= 8 can be made.

8 = 3 + 5 9 = 3 + 3 + 3 10 = 5 + 5 11 = 3 + 3 + 5 12 = 3 + 3 + 3

Case 1 = no 5 cent coins Case 2 = at least oe 5 cent coin

Result: For all change amounts n >= 8, you can make n cents using only 3 cent coins and 5 cent coins.

Proof by induction: Observe that 8 = 3 + 5, prooving the base case. Let k >= 8 be any arbitrary integer. Assume that k cents can be made by using only 3 cent and 5 cent coins. We claim that (k + 1) cents can be made using only 3 cent coins and at least one 5 cent coin. Case 1: at lest one 5 cent coin is used to make k cents. Trade one 5 cent coin for each 3 cent coins. The total would then be k - 5 + 2 * 3 = k + 1 cents. Case 2: no 5 cent coins are used in making k cent coins. Since k >= 8 and only 3 cent coins are used, we have at least three 3 cent coins. Trade three 3 cent coins or two 5 cent coins. The total would then be k - 3 * 3 + 2 * 5 = k + 1. Therefore, by the Principle of Mathematical Induction, any amount n >= 8 can be made.

Proof by Mathematical Induction using Factorials 1 * 1! + 2 * 2! + 3 * 3! .. + n * n! = (n + 1)! = 1 for all n >= 1. Proof: Observe that when n = 1, 1 * 1! = 1 == 2! - 1 = (1 + 1)! - 1 prooving the base case. Let k >= 1 be any arbitrary integer. Assume 1 * 1! + 2 * 2! + 3 * 3! .. + k * k! = (k + 1)! - 1. We want to show that 1 * 1! + 2 * 2! + 3 * 3! .. + k * k! = (k + 1) * (k + 1)! = (k + 2)! - 1 1 * 1! + 2 * 2! + 3 * 3! .. + k * k! = (k + 1) * (k + 1)! = (k + 1)! - 1 + (k + 1) * (k + 1)! = (k + 1)! * (1 + k + 1) - 1 = (k + 1)! * (k + 2) - 1 = (k + 2)! - 1 By the P.M.I., Eⁿ_i=1 i * i = (n + 1)! - 1 for all n >= 1. The statement above should be formatted in the inductive notation format which wont work in markdown.

Prove that n < 2ⁿ for all n >= 1. Proof: Observe that 1 < 2¹, prooving the base case. Let k >= 1 be any arbitrary integer. Assume k < 2^{k</sub>. We want to show that k + 1 < 2k+1 Observe that 2k+1 = 2k * 2 > k * 2 = 2k = k + k >= k + 1 By the P.M.I., n < 2n for all n >= 1.}

Prove that n! is > 2ⁿ for all n >= 4. Proof: Notice that 4 ! = 24 > 16 = 2⁴. Let k >= 4 be any arbitrary integer. Assume k! > 2^k. We want to show (k + 1)! > 2^k+1 Observe (k + 1)! = (k + 1) * k! > (k + 1) * 2^k >= 5 * 2 > 2 * 2^k = 2^k+1. By P.M.I. n! > 2ⁿ for all n >= 4.

A number is…

divisible by 2 if and only if it’s ones digit is even (i.e. 0, 2, 4, 6, 8).

For instance, 8 is even because 8 / 4 = 2. In other words, its even because its evenly divisible by something.

divisible by 5 if and only if its ones digit it 0 or 5.

2 and 5 are the easiest to test because we are working with a base 10 system.
2 and 5 are divisors of 10.
Whatever system your in, the divisors of that system will be the easiest to work with.

divisible by 10 if and only if its ones digit is 0.

In an expression a + b + c, if a and b are multiples of 5, then in order for the result to be a multiple of 5, c must also be divisible by 5.
For example, 10 + 15 + 20 can be written as 5 * 2 + 5 * 3 + 5 * 4 = 5(2 + 3 + 4)
Another example, a number 473 = 4 * 100 + 7 * 10 + 3

divisible by 3 if and only if the sum of its digits is divisible by 3.

Example 1: 3	3120 since
3	3 + 1 + 3 + 0
The symbol “	” means “divides into”
Example 2: 713 is not divisible by 3 since 7 + 1 + 3 = 11 and 3 does not	11.

divisible by 9 if and only if the sum of its digits is divisible by 9.

Example: 347 = 3(100) + 4(10) + 7 = 3(99 + 1) + 4(9 + 1) + 7 = 3 * 99 + 4 * 9 + (3 + 4 + 7) Notice the 99 and the 9

divisible by 6 if and only if and only if it is divisible by both 2 and 3.

Breaking 24 into it’s prime number factorizations: 24 = 2 * 3 * 2 * 2 24/6 = 2 * 3 n/6 = P1 * P2 * P3… / 2 * 3 Example: n = 3120 Since 2 | n and 3 | n then we know 6 | n

For the following number determine all possible ways to fill in the missing ones digit so that the number is divisible by 6.

4,32_
The ones digit must be either 0, 2, 4, 6 or 8.
3 | 4320? Yes, 4 + 3 + 2 == 9 and 3 | 9
3 | 4 + 3 + 2 and 3 does not go into 4 + 3 + 2 + 2
…

divisible by 4 if and only if the number represented by its lats two digits is divisible by 4.

Ex 1: 1784 = (1 * 1000) + (7 * 100) + (8 * 10) + 4
Ex 2: Does 4 divide 342?
No, because 4 does not divide 42.

divisible by 8 if and only if the number represented by its last 3 digits is divisible by 8.

Ex: 8

3120 since 8

120, i.e. 120 = 8 * 15.

Interesting therem:
For 2^1 check the last digit
For 2 squared check the the last two
For 2 cubed chek the last three

divisible by 11 if and only if the alternating sum of its digits is divisible by 11.

• (Altername means alternate signs between + and -)

Ex: Let n = 6314
6 - 3 + 1 - 4 = 0
So, since 11 | 0 it must be that 11 | 6314
Ex: Let n = 3120
3 - 1 + 2 - 0 = 4
Since 11 does not | 4, then 11 does not | 3120.
What if we computed - 3 + 1 - 2 + 0 = -4?
So since 11 does not | -4 (and in general, if 11 does not | a then 11 | -a)
then the divisibility rule is unaffected.

divisible by 7 if and only if

• Use the following iterative process:
• Step 1: Take the last digit and remove it from the rest of the number.
• Last digit: d = n % 10, remove last digit: n = n/10
• Step 2: Subtract twice the last digit from the number formed by the remaining digits
• n = n - 2 * d
• Repeat steps one and two as needed.
• The origional number n is divisible by 7 if and only if the number obtained by this iterative process is divisible by 7.

Ex: n = 392
Step 1: d = 2, n = 39
Step 2: n - 2d = 39 - 4 = 35
True since 7 | 35, then 7 | 392

Ex: n = 1384
Step 1: d = 4, n = 138
Step 2: 138 - 2d = 130
Repeat:
Step 1: d = 0, n = 13
Step 2: 13 - 2(0) = 13
Since 7 does not | 13, then 7 does not divide 1384.

Countably infinite

• A set A is countably infinite if there is a one-to-one correspondence from ℕ = {1, 2, 3, …} to A.
• Countably infinite is like “listing”.
• The set of positive even integers is countably infinite.

Statement - A mathematical phrase that is true or false

Examples:

• P: Today is Monday. –> false
• Q: The integer 5 is even. –> false
• R: The integer 0 is even. –> true

Unrelated: This shows how it is possible to proove that 0 is even. n is even if and only if n = 2k for some integer k. 0 = 2 * 0 ***

The following examples of P, Q and R display their meaning in plain terms.

• P v Q is true –> “At least one of these is true.”
• Q ^ R is true –> “Both of these are true.”
• P ⊕ R is true –> “One of these is true but not both.”

Laws

Demorgan’s law:
~(PvQ) ≡ ~P ^ ~Q
~(P^Q) ≡ ~P v ~Q

Examples:

~(1 ≤ n < 3)
<=========○—–●=========>
1 3
Also: n < 1 OR n ≥ 3

1 ≤ n < 3
<———●=====○———>
1 3

1.) Negate the following statements.
The earth has two moons or 3 + 5 < 2
The earth does not have two moons and 3 + 5 ≥ 2

2.) Negate the following statements.
A stack overflow has occured and the sector size is not supported.
A stack overflow has not occured and the sector size is supported.

3.) Negate the following statements.
x is positive or y is negative.
x is not positive or y is not negative.

Conditional Statements (Implications)

P –> The hypothesis
Q –> The conclusion

If P then Q

If n is even, then n² is even
Hypothesis: n is even
Conclusion: n² is even

There is many ways in which implications can be worded. Some examples are:

P => Q
If P, then Q
P implies Q
P only if Q
Q if P
P is sufficient for Q
Q is necessary for P

Negating an if then statement (negating an implication)

~(P => Q) ≡ ~(~P v Q)
~(~P v Q) ≡ p ^ ~Q

Examples:

Negate the following.
If x > y, then x² > y²
x > y and x² ≤ y²
Note: Do not write the If in the negation.

Negate the following.
If rs = 0, then r = 0 or s = 0
rs = 0 and r != 0 and s != 0
Notice: The negation results in the form P ^ ~Q.

Contrapositive and converse statements

If P, then Q.
Contrapositive: If ~Q, then ~P.
Converse: If Q, then P.

If T is equalateral, then T is isosceles.
Note: isosceles defines a triangle in which two sides are congruent.
Contrapositive: If T is not isoscelesm then T is not equalateral.
Converse: If T is isosceles, then T is equalateral.
Note: The contrapositive of this statement is true while the converse of this statement is false.
The contrapositive will always be logically equivilant to the origional statement.

Biconditional statements

P <=> Q
“P if and only if Q”
“If p, then Q and if Q then P”

Examples:

If ab is even, then a is even and b is even.
False, 2 * 3 = 6, 6 is even but 2 is even and 3 is not even.

If ab is even then, a is even or b is even.
True
Converse: If a is even or b is even, then ab is even.
True
Biconditional: ab is even if and only if a is even or b is even.
Note: The statement and the converse are not always both true, but when they are it means the biconditional is true.

Set notation

• ℕ is the set of natural numbers.
• Mathemeticians and computer scientists define the set of natural numbers diferently.
• Mathemeticians: ℕ = {1, 2, 3, …}

• Computer scientists: ℕ = {0, 1, 2, …}

• ℤ is the set of integers.

• ℤ = {…, -3, -2, -1, 0, 1, 2, 3, …}

• ℝ is the set of real numbers.

• ℝ = {1, 12.38, -0.8625, 3/4, √2, 198}

• ℚ is the set of rational numbers.

• ℚ = { a/b

  a, b ∈ ℤ, b != 0}

• 3/7 ∈ ℚ
• -4000/201 ∈ ℚ
• 4 = 4/1 ∈ ℚ
• π ∉ ℚ

Note: The symbol ‘∈’ is pronounced is a subset of.

* Definition of a prime: An integer n>1 is prime if it is only divisible by one and itself.

• A number is rational if it can be written as ab where a and b are integers and b≠0.
• Direct - If P then Q
• Negation - P and Q̸
• Converse - If Q then P
• Contrapositive - If Q̸ then P̸ divisible by 10 if and only if its ones digit is 0. In an expression a + b + c, if a and b are multiples of 5, then in order for the result to be a multiple of 5, c must also be divisible by 5. For example, 10 + 15 + 20 can be written as 5 * 2 + 5 * 3 + 5 * 4 = 5(2 + 3 + 4) Another example, a number 473 = 4 * 100 + 7 * 10 + 3

divisible by 3 if and only if the sum of its digits is divisible by 3. Example 1: 3 | 3120 since 3 | 3 + 1 + 3 + 0 The symbol “|” means “divides into” Example 2: 713 is not divisible by 3 since 7 + 1 + 3 = 11 and 3 does not | 11.

divisible by 9 if and only if the sum of its digits is divisible by 9. Example: 347 = 3(100) + 4(10) + 7 = 3(99 + 1) + 4(9 + 1) + 7 = 3 * 99 + 4 * 9 + (3 + 4 + 7) Notice the 99 and the 9

divisible by 6 if and only if and only if it is divisible by both 2 and 3. Breaking 24 into it’s prime number factorizations: 24 = 2 * 3 * 2 * 2 24/6 = 2 * 3 n/6 = P1 * P2 * P3… / 2 * 3 Example: n = 3120 Since 2 | n and 3 | n then we know 6 | n For the following number determine all possible ways to fill in the missing ones digit so that the number is divisible by 6. 4,32_ The ones digit must be either 0, 2, 4, 6 or 8. 3 | 4320? Yes, 4 + 3 + 2 == 9 and 3 | 9 3 | 4 + 3 + 2 and 3 does not go into 4 + 3 + 2 + 2

divisible by 4 if and only if the number represented by its last two digits is divisible by 4. Ex 1: 1784 = (1 * 1000) + (7 * 100) + (8 * 10) + 4 Ex 2: Does 4 divide 342? No, because 4 does not divide 42. divisible by 2 if and only if it’s ones digit is even (i.e. 0, 2, 4, 6, 8). For instance, 8 is even because 8 / 4 = 2. In other words, its even because its evenly divisible by something. divisible by 5 if and only if its ones digit it 0 or 5. 2 and 5 are the easiest to test because we are working with a base 10 system. 2 and 5 are divisors of 10. Whatever system your in, the divisors of that system will be the easiest to work with.

divisible by 8 if and only if the number represented by its last 3 digits is divisible by 8. Ex: 8 | 3120 since 8 | 120, i.e. 120 = 8 * 15. Interesting therem: For 2^1 check the last digit For 2 squared check the the last two For 2 cubed chek the last three

divisible by 11 if and only if the alternating sum of its digits is divisible by 11.

• (Altername means alternate signs between + and -) Ex: Let n = 6314 6 - 3 + 1 - 4 = 0 So, since 11 | 0 it must be that 11 | 6314 Ex: Let n = 3120 3 - 1 + 2 - 0 = 4 Since 11 does not | 4, then 11 does not | 3120. What if we computed - 3 + 1 - 2 + 0 = -4? So since 11 does not | -4 (and in general, if 11 does not | a then 11 | -a) then the divisibility rule is unaffected.

divisible by 7 if and only if

• Use the following iterative process:
• Step 1: Take the last digit and remove it from the rest of the number.
• Last digit: d = n % 10, remove last digit: n = n/10
• Step 2: Subtract twice the last digit from the number formed by the remaining digits
• n = n - 2 * d
• Repeat steps one and two as needed.
• The original number n is divisible by 7 if and only if the number obtained by this iterative process is divisible by 7. Ex: n = 392 Step 1: d = 2, n = 39 Step 2: n - 2d = 39 - 4 = 35 True since 7 | 35, then 7 | 392 Ex: n = 1384 Step 1: d = 4, n = 138 Step 2: 138 - 2d = 130 Repeat: Step 1: d = 0, n = 13 Step 2: 13 - 2(0) = 13 Since 7 does not | 13, then 7 does not divide 1384.

Primes 2, 3, 5, 7, 11, 13, 17… Definition of a composite 1. An integer n > 1 is composite if it is not prime. 2. An integer n is composite if there exist integers a and b with 1 < a < n and 1 < b < n such that n = ab. 3. There exist positive integers r and s such that n = rs and r != 1 and s != 1. Proof (contrapositive):

1. Assume n is even.
2. Then n=2k for some integer k
3. So n2=(2k)2=4k2=2(2k2).
4. Since 2k2 is an integer, n2 is even. Proof (contradiction):
5. Assume n2 is odd.
6. Suppose, to the contrary, that n is even.
7. Then n=2k for some integer k.
8. So n2−(2k)2=4k2−2(2k2).
9. Since 2k2 is an integer, n2 is even, contradicting that n2 is odd.
10. Therefore, n is odd. For any two integers m and n, 3m+5n is even if and only if m and n are of the same parity.
    • NOTE: (Two integers m and n have the same parity if they are either both even or both odd.) If 3m+5n is even, then m and n are of the same parity. Proof (contrapositive): If m and n are of opposite parity, then 3m+5n is odd. Case 1: m is even and n is odd. Case 2: m is odd and n is even. if m and n are of the same parity, then 3m+5n is even. Proof (direct): Case 1: m and n are both even. Case 2: m and n are both odd. For any sets A, B, and C, (A−B)∪(A−C)=A−(B∩C).
11. Let A, B, and C be sets. First we show that (A−B)∪(A−C)⊆A−(B∩C)
12. Let x∈(A−B)∪(A−C).
13. So x∈A−B or x∈A−C. Case 1: x∈A−B
14. Then x∈A and x∉B.
15. So x∈A and since x∉B, we know x∉B∩C.
16. So x∈A−(B∩C). Case 2: x∈A−C
17. Then x∈A and x∉C.
18. So x∈A and since x∉C, we know x∉B∩C.
19. So x∈A−(B∩C).
20. Thus x∈A−(B∩C), implying (A−B)∪(A−C)⊆A−(B∩C). Next we show A−(B C)⊆(A−B)∪(A−C).
21. Let x∈A−(B∩C).
22. Then x∈A and x∉B∩C.
23. So x∈!(B∩C), which implies x∈!B∪!C.
24. So x∉B or x∉C. Case 1: x∉B
25. Since x∈X and x∉B, we know x∈A−B.
26. Therefore x∈(A−B)∪(A−C). Case 2: x∉C
27. Since x∈A and x∉C, we know x∈A−C.
28. Therefore x∈(A−B)∪(A−C) For all integers a, b, and c, if a|c and b|c, then ab|c. = False. Let a=2, b=4, and c=12.
29. Then 2|12 and 4|12, but 2∗4=8/|12. For all integers a, b, c, and d, if a|b and c|d, then ac|bd. = True. bd=ax∗cy=ac∗xy

30. Assume a

    b and c

    d.

31. Then b=ax and c=dy for some integers x and y.
32. So bd=ax∗cy=ac(xy)

33. Since xy is an integer, ac

    bd.

Proof by Mathematical Induction using Factorials 1 * 1! + 2 * 2! + 3 * 3! .. + n * n! = (n + 1)! = 1 for all n >= 1. Proof: Observe that when n = 1, 1 * 1! = 1 == 2! - 1 = (1 + 1)! - 1 proving the base case. Let k >= 1 be any arbitrary integer. Assume 1 * 1! + 2 * 2! + 3 * 3! .. + k * k! = (k + 1)! - 1. We want to show that 1 * 1! + 2 * 2! + 3 * 3! .. + k * k! = (k + 1) * (k + 1)! = (k + 2)! - 1 1 * 1! + 2 * 2! + 3 * 3! .. + k * k! = (k + 1) * (k + 1)! = (k + 1)! - 1 + (k + 1) * (k + 1)! = (k + 1)! * (1 + k + 1) - 1 = (k + 1)! * (k + 2) - 1 = (k + 2)! - 1 By the P.M.I., Eni=1 i * i = (n + 1)! - 1 for all n >= 1.

Common Stock

• Securities - all of the investments, stocks, bonds, mutual funds, options, and commodities that are bought and sold on the stock market.
• Private corporation - a company that issues stock to a small group of people.
• Public corporation - a company that sells its shares openly in stock markets. Prefered Stock
• par value - an assigned dollar value that is printed on a stock certificate.
• Cumulative preferred stock - a stock whose unpaid dividends build up and must be paid before any cash dividend is paid to the common stockholders.
• Convertible preferred stock - a stock that can be exchanged for a specific number of shares of common stock.
• Participation Feature - allows preferred stock holders to share in the corporation’s earnings with the common stockholders.

Types of Stock Investments

• Blue-chip stock - a stock that is issued by the strongest and most respected companies, that have a history of stable earnings.
• Income stock - pays higher-than-average dividends compared to other issues. Buyers are attracted this kind of stock because the dividends are predictable.
• Growth stock - issued by a corporation that has higher that average predicted earnings.
• Cyclical stock - has a market value that tends to reflect the state of the economy.
• Defensive stock - a stock that remains stable during declines in the economy.
• Large-cap-stock - a stock from a corporation that has issued a large number of shares of stock and has had large amounts of capitalization.
• Small-cap-stock - a stock issued by a company with a capitalization of $500 million or less.
• Penny stock - typically sells for less than $1 per share, although it can sell for as much as $10 per share.

Factors that influence the price of stock

• bull market - a market that occurs when investors are optimistic about the economy and buy bulky stocks.
• bear market - a market condition where investors are optimistic about the economy and sell stocks.
• Current yield - the annual calculation that includes the annual dividend by the current market value.
• Total return - a calculation that includes the annual dividend as well as any increase or decrease in the original purchase price of the investment.

Capacitor Marking Table (Ceramic and Monolithic Cap's)

Important: Capacitors with values below 100 pf may be marked two ways: Either with just two digits (22 pF = "22") or three digits (22 pF = "220",). In the latter case the third digit signifies the number of zeros following the first two digits. "220" = 22 pF, "221" = 220 pF, "222" = 2200 pF.

Fixed Resistors

A fixed resistor supplies a predetermined resistance to a circuit. The standard unit value of a resistor is the ohm (represented by the symbol Ω) usually with the prefix ''K'' or ''M''; ''K'' meaning thousand and ''M'' meaning million. The higher the ohm value, the more resistance the component provides to the circuit. The value on most fixed resistors is identified by color coding. The color coding starts near the edge of the resistor and comprises four, five, and sometimes six band colors.

The formula for determining the resistance from the bands is:

Resistance = ((first band color value × 10) + (second band color)) × 10^{third band color value} ohms

Additional information concerning the Axial Lead resistor can be obtained if the first band is a wide band.

(Case 1) if only the first band is wide than the resistor is wire wound.

(Case 2) if the first band is wide and there is also a blue fifth band to the right of the fourth band than the resistor is wirewound and flame proof.

Variable Resistors

Variable resistors, also known as potentiometers (pots) let you adjust a resistor to a specific resistance. The actual range of resistance is determined by the upward value of the potentiometer. Potentiometers are thus marked with this upward value, such as 10K, 50K, 100K, 1M, and so forth.

Example: A 50K potentiometer will let you set any resistance any ware from 0 to 50000 ohms.

Potentiometers are either the dial or slide type. The rotation of the dial type is nearly 360°, depending on the type of potentiometer.

Extremely precise potentiometers are referred to as multiturn pots or trimmers. Instead of of turning the dial one complete rotation to change the resistance, a multiturn pot requires that the dial is turned 3, 5, 10, or even 15 times for the span to be the same as a regular potentiometer.

Mode of application

1. Determine the available alternatives
2. Determine the consequence(s) of each action
   1. Every action you make has a consequence. Ethics dictates that the standard should be that which a reasonably intelligent person would judge the consequences of.
3. Evaluate the consequences
   1. Some sort of metric must be determined.
   2. Which consequence results in greater happiness?
4. The alternative with the best consequences is the morally right action

Deontology

• Based on consideration of individual’s rights, duties, and obligations.
• individual autonomy - we are self legislating being, we determine the laws that govern our actions.

For each right a person has, there is a corresponding duty. For instance, if someone has a right to life, then someone else has a duty not to take that life.

Perfect duties - You either stole something or you didn’t. Imperfect duties - Helping others in need. How much do you have to do to fulfill that duty?

Spectrum

• Laissez Faire Capitalism → (Libertarianism)
• Welfare State Capitalism
• Socialism - Socialism infringes upon individual autonomy
• Marxism / Communism

Equality ←→ Freedom

Benjamin Franklin

• 1706 Born in Boston, Massachusetts on January 17
• 1718 Begins an apprenticeship in his brother James’ printing shop in Boston
• 1723 Age 17, he leaves his family, running away to Philadelphia, Pennsylvania
• 1724 Moves to London, continuing his training as a printer
• 1732 begins to annually publish, until 1758, Poor Richard: an almanack
• 1737 Appointed postmaster of Philadelphia
• 1747 First writings of electrical experimentation
• 1751 His book “Experiments and Observations on Electricity” is published in london
• 1752 Founds the first American fire insurance company
• 1775 Elected to Continental Congress
• 1776 Signs the Declaration of Independence
• 1778 negotiates and signs Treaty of Alliance with France
• 1782 negotiates, with John Adams and John Jay, the Treaty of Peace with Great Britain
• 1783 While in Paris, watches the Montgolfier brothers become the first men to fly in a balloon
• 1784 negotiates treaties with Prussia and other European
• 1787 elected president of the Pennsylvania Society for promoting the abolition of slavery; serves as delegate to the Constitutional Convention
• 1790 Dies in Philadelphia on April 17

Charles Darwin

The affinities of all the beings of the same class have sometimes been represented by a great tree… As buds give rise by growth to fresh buds, and these if vigorous, branch out and overtop on all sides many a feebler branch, so by generation I believe it has been with the great Tree of Life, which fills with its dead and broken branches the crust of the earth, and covers the surface with its ever branching and beautiful ramifications.” ~ Charles Darwin, 1859

Charles Messier

The Messier objects are celestial 110 objects plotted by comet-hunter Charles Messier in the late 1700s. He wanted to catalogue the various “fuzzy” objects that he observed in the night sky to help avoid confusion with the comets he was trying to discover.

Democritus

Democritus was one of the first people to have developed an idea about atoms.

Dwight D. Eisenhower

Born in Texas and raised in Kansas, Dwight D. Eisenhower was one of America’s greatest military commanders and the thirty-fourth President of the United States. Inspired by the example of a friend who was going to the U.S. Naval Academy, Eisenhower won an appointment to the U.S. Military Academy at West Point. Although his mother had religious convictions that made her a pacifist, she did not try to stop Eisenhower from becoming a military officer.

William Herschel

William Herschel was an 18th century astronomer who began to catalog deep space objects.

Matter can be classified into two general groups; mixtures and pure substances.

Chemical changes

Chemical changes occur when substances change and a new substance is created. Signs that a chemical change has occurred include a change of temperature. If the substance experiences an increase in thermal energy than an exothermic reaction is taking place, in this type of reaction heat is released by the breaking of chemical bonds. If there is a decrease in thermal energy than a endothermic change is taking place, in this type of reaction thermal energy is absorbed into chemical bonds. A change of color or release of gases, as long as the gas is a new substance not just a change in state of matter, can indicate either a chemical or a physical change.

Atoms

People once thought that the atom was the smallest particle of matter in the universe However, scientists now know that atoms are made up of even smaller parts. There are three different kinds of particles. They are: protons, neutrons, and electrons. Most of the mass of an atom is found in the central part of the atom, called the nucleus. The nucleus of an atom is made up of protons and neutrons. These particles are packed very tightly together in the nucleus.

Electrons are found outside the nucleus. They circle the nucleus very, very quickly. Electrons are very small and have almost no mass. The number of electrons in an atom is always equal to the number of protons in the nucleus of that atom. Scientists have discovered that protons, electrons, and neutrons have different charges. You probably know that the word “charge” has something to do with electricity. There are two kinds of charges. There are positive (plus) charges and negative (minus) charges. By studying atoms, scientist, have learned that:

• PROTONS have positive (+) charges.
• ELECTRONS have negative (-) charges.
• NEUTRONS have no charges. They are neutral.

Since atoms have the same number of protons and electrons, the number of positive charges equals the number of negative charges. The opposite charges cancel each other out. Therefore, the whole atom has no overall charge.

The arrangement of electrons In the past, scientists believed that electrons circled the nucleus the same way the planets circled the sun. Today, however, scientists know that there is no exact path of an electron. The quick moving electrons form a “loud” around the nucleus.

In the modern atomic theory, electrons are arranged into energy levels, or shells. Each electron shell is labelled with a capital letter. The first shell is the “K” shell. It is the shell closest the the nucleus. The “K” shell has the least amount of energy. The next shell is the “U’ shell. After the “L” shell, comes the “M” shell, and so on.

Each shell can only hold a certain number of electrons.

• The “K” shell can hold up to 2 electrons.
• The “L” shell can hold up to 8 electrons.
• The “M” shell can hold up to 18 electrons.

The number of shells an atom has depends upon the number of electrons the atom has. In general, each shell must have its full number of electrons before a new shell starts. If there are mom electrons than a shell can hold, a new shell starts.

The difference between atomic mass and atomic number Atoms of different kinds of matter have different numbers of protons and electrons. When scientists talk about different kinds of matter, they often refer to the matter by it’s atomic number. The atomic number of an atom is the number of protons (and usually, the number of electrons) in the atom. Scientists also describe atoms by their atomic mass. Scientists do not measure the mass of atoms in grams or ounces. They measure the mass of atoms in atomic mass units (a.m.u.). You can figure out the atomic mass of an atom by using the following information:

• Each proton has a mass of 7 a.m.u.
• Each neutron has a mass of I a.m.u.
• The atomic mass of an atom is the total number of protons and neutrons in the nucleus of the atom.

What about the electrons Don’t they count? Electrons are very light. Their mass is not counted in the atomic mass. Sometimes two moms of the same kind of matter do not have the same atomic mass. How is this possible? They have a different number of neutrons. All atoms of the same kind of matter always have the same number of protons. Thus, they all have the same atomic number. Atoms of the same kind of matter that have different numbers of neutrons are called isotopes.

Properties of matter are characteristics that describe matter and can be used to identify different types. A general property, such as mass, weight, size, or shape can change for a given type of matter. A characteristic properties are always the same for a specific kind of matter and stay the same despite the size or shape of the sample. Some examples of characteristic properties include hardness, flammability, boiling point, freezing point, melting point and density.

Physical changes

Physical changes occur when a change happens to matter which does not alter the type of matter that it is . A physical change will alter the form of a substance but not its identity. The physical properties of an object or substance change but it does not change into a new substance. A change of color or release of gases can indicate either a physical or a chemical change has occurred.

Gasses

Gases have particles that are spaced far apart and will expand away from one another to fill their container. These particles travel very quickly and bounce of the solid surfaces they come in contact with. Gases do not have a definite volume because they are so easily compressed and decompressed. When a gas is heated and charged with electrons it will change into a plasma, when it is cooled it will change into a liquid.

Liquids

Liquids are less dense than solids. They have a definite volume but unlike solids they take the shape of their container. The particles of liquids have some space between them and roll over one another in a fluid or flowing motion. They also have an acute magnetism which causes the particles of a liquid to group together or puddle on a surface. When a liquid is heated it will change into a gas, when it is cooled it will change into a solid.

Solids

Solids are the most dense forms of mater. There particles are closely spaced and can only vibrate. Solids have a definite volume and shape. Unlike liquids liquids, gases and plasmas, solids have a fixed shape and do not change to take up the space of their container. When a solid is heated it will change into a liquid.

Plasma

Plasma is an ionized gas. When a plasma’s source of heat or electricity is taken away it will change into a gas.

An object is in motion when its distance from another object is changing. A reference point is a fixed place that you compare an object that is in motion to. A object is in motion if it changes position relative to a reference point. Speed is the distance an object travels in one unit of time. If an object moves at a constant speed it can be determined by dividing the distance it travels by the time taken to get to a specified point. When both the speed of an object an object and the direction the object is traveling in are stated than velocity is being described.

Link List

[HEAD]–> [ ][ ]–> [ ][/]

Circular Linked list

[HEAD]–> [ ][ ]–> [ ][ ]–> [Back to HEAD]

Doubally Linked List

[HEAD]<–>[ ][ ]<–>[ ][/]

Circular Doubally Linked List

[HEAD]<–>[ ][ ]<–>[ ][ ]<–>[Back to HEAD]

Dummy head

• Head points to the dummy head
• Has no data
• Dummy head is never removed

Tail node

• Points to last node in the list

Induction proofs

• f(0) = 0
• f(n) = f(n-1) + 3n
• Closed form: f(n) = 3n(n+1)/2

BASIS f(0) = 0 in recurrence relationship Substitute 0 for n in closed form: f(0) = 3 * 0 * (0+1) / 2 = 0

INDUCTIVE ASSUMPTION Assume k is an integer, k > 0. f(k) = 3k(k+1)/2

We want to show that f(k + 1) = 3 * (k+1) * (k+2) / 2

Proof

Plug k+1 in for n in the recursive relation
f(k+1) = f(k+1 - 1) + 3(k+1)
       = f(k) + 3(k+1)
       = 3k(k+1)/2 + 3(k+1)
       = 3k(k+1)/2 = 6(k+1)/2
       = (3k(k+1) + 6(k+1))/2
       = ((k+1)(3k+6))/2
       = 3(k+1)(K+2)/2      QED

Axioms

• Things we can write that are true about out ADT
• EX: After creating a list, the list should be empty
• EX: After creatig a list, then adding an item, then removing an item, the list should be empty.

Test Review Notes

Note: Review using recursion to traverse a list Anything that takes a node as a parameter has to be private. <– Is this statement correct? The client can never know about nodes. Nodes are package-privte.

** Generic sort are only sort arrays of objects. It cannot sort an array of int’s which don’t have a compareto method.

A heap can be stored in an array, and it does not require pointers or objects to represent the tree structure. Therefore heapsort is based on selection.

Examples:

Find the linear velocity of a point on the edge of a lawn mower blade 18 inches long evolving at 300 rpm. Find in inches per minute.

v = 300 rev / 1 min * 2Pi / 1 rev * 18 in / 1 * 1 min / 60 sec = 10800 / 60 = 180Pi inches per second

A point is 25 inches from the center of a circle. If the circle is rotating at 15 rev per sec, find the velocity of the point in feet per minute.

v = wr = 1800 Pi rad / 1 min * 24 in / 1 * 1 ft / 12 in = 3600 Pi ft / min

A point on the rim of a tir is 14 inches from the hub of the wheel. If the wheel is rotating at 120 rpm, find the linear velocity of the point in inches per second.

v = 120 rev / 1 min * 2 Pi / 1 rev * 1 min / 60 sec * 14 in / 1= 56 Pi in /sec

A point on the edge of a gear 8 inches in diameter is revolving at 180 rpm. Find the linear velocity of this point in inches per second

v = 130 rev / min * 3 pi / 1 rev * 1 min / 60 sec * 4 in / 1 = 24 Pi in / sec

A person on the end of a skating whip is 10 feet from the center person. If they want to make 20 revolutions per minute, how fast will the last person in the line have to skate?

v = 20 ev / sec * 2 Pi / 1 rev * 10 ft / 1 = 400 ft/ min

Find the angular velocity in radians per minute and the linear velocity in feet per minute of the point on the rim of a wheel with 32 inch diameter rotating at 5 rev/sec.

w = 5 rev / 1 sec * 2 Pi / 1 rev * 60 sec / 1 min = 100 Pi rad/min

v = 600Pi / 1 min * 16 in * 1 ft/ 12 in = 800 Pi ft / min

Note: In the above equation, Pi is the symbol pi and the operations of division indicate fractions.