This is a random collection of notes that I
have accumulated from various classes that I
have taken.
Hosting them here is mainly to help me stay
organized and be able to find them.
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.
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.
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 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.
1  2  3  4  5  ...  

S1  N  N  N  N  N  
S2  Y  N  N  N  N  
S3  N  Y  N  N  N  
S4  N  Y  N  Y  N  
...  
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.
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.
n is even n = 2k
direct:
if n^{2} + 8 is even, then n is even. n^{2} is even if n is odd, then n^{2} + 8 is odd n^{2} = 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 ba > 3 divides 15 because 15 = 3 * 5 315 > 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) 40 0 = 4 * 0 70 120 420
not allowed: 00 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 nonzero 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.
 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
 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.
 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.
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 ba if and only if a = b * c for some integer c.
210 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.
6n <=> 2n and 3n
abc <= ac and bc
Notice: The use of the Walker Property in this example. Result: For integers a, b, c, if
ac and bc, then abc.
Proof: Let a, b, c be integers.
Assume ab anf bc.
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
212 and 414
2 * 4 = 8 and 8∤12.
Result: (AntiWalker Property)
For integers a, b, c, if abc, then ac and bc.
Proof: Let a, b, c, be integers.
Assume abc. Then c = ab*x for some integer x.
Thus c = a(bx) and we know bx ∈ ℤ. So ac.
Also c = b * (ax) and we know ax ∈ ℤ.
Thus bc.
If a  b and a  c, then a  bc. 
If a  bc, then a  b and a  c. 
If a  bc, then a  b or a  c. 
If a  b and b  d, then ac  bd. 
If a  b and c  d, then a+c  b+d. 
For any integer n > 1, there exists a prime number p such that p  n. 
Examples:
n = 2 p = 2 22
n = 3 p = 3 33
n = 7 p = 7 77
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).
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 pa, then p / (a+1).
Proof: Suppose not. That there exists an integer a and a prime p such that pa 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(sr).
Thus p1. 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.
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, (AB) ⋃ (AC) = A  (B ⋂ C)
Proof: First we show (AB) ⋃ (AC) ⊆ A  (B ⋂ C)
Let x ∈ (AB) ⋃ (AC).
Then x x ∈ AB OR x ∈ AC
Case 1: x ∈ A  B
[Show x ∈ A  (B ⋂ C)]
Case 2: x ∈ A  C
[Show x ∈ A  (B ⋂ C)]
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
I want to write the shorthand version of: 1/2 + 2/3 + 3/4 + 4/5 + … see note sheet #9q34
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
Let a be some fixed nonnegative 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^{n}_{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^{n} for all n >= 1. Proof: Observe that 1 < 2^{1}, 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^{n} for all n >= 4. Proof: Notice that 4 ! = 24 > 16 = 2^{4}. 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^{n} for all n >= 4.
For instance, 8 is even because 8 / 4 = 2. In other words, its even because its evenly divisible by something.
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.
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
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.
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
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
…
Ex 1: 1784 = (1 * 1000) + (7 * 100) + (8 * 10) + 4
Ex 2: Does 4 divide 342?
No, because 4 does not divide 42.
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
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.
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.
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.”
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.
P –> The hypothesis
Q –> The conclusion
If P then Q
If n is even, then n^{2} is even
Hypothesis: n is even
Conclusion: n^{2} 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
~(P => Q) ≡ ~(~P v Q)
~(~P v Q) ≡ p ^ ~Q
Examples:
Negate the following.
If x > y, then x^{2} > y^{2}
x > y and x^{2} ≤ y^{2}
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.
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.
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.
Computer scientists: ℕ = {0, 1, 2, …}
ℤ = {…, 3, 2, 1, 0, 1, 2, 3, …}
ℝ = {1, 12.38, 0.8625, 3/4, √2, 198}
ℚ = { a/b  a, b ∈ ℤ, b != 0} 
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): 1. Assume n2 is odd. 2. Suppose, to the contrary, that n is even. 3. Then n=2k for some integer k. 4. So n2−(2k)2=4k2−2(2k2). 5. Since 2k2 is an integer, n2 is even, contradicting that n2 is odd. 6. 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). 1. Let A, B, and C be sets. First we show that (A−B)∪(A−C)⊆A−(B∩C) 1. Let x∈(A−B)∪(A−C). 2. So x∈A−B or x∈A−C. Case 1: x∈A−B 1. Then x∈A and x∉B. 2. So x∈A and since x∉B, we know x∉B∩C. 3. So x∈A−(B∩C). Case 2: x∈A−C 1. Then x∈A and x∉C. 2. So x∈A and since x∉C, we know x∉B∩C. 3. So x∈A−(B∩C). 4. Thus x∈A−(B∩C), implying (A−B)∪(A−C)⊆A−(B∩C). Next we show A−(B C)⊆(A−B)∪(A−C). 1. Let x∈A−(B∩C). 2. Then x∈A and x∉B∩C. 3. So x∈!(B∩C), which implies x∈!B∪!C. 4. So x∉B or x∉C. Case 1: x∉B 1. Since x∈X and x∉B, we know x∈A−B. 2. Therefore x∈(A−B)∪(A−C). Case 2: x∉C 1. Since x∈A and x∉C, we know x∈A−C. 2. Therefore x∈(A−B)∪(A−C) For all integers a, b, and c, if ac and bc, then abc. = False. Let a=2, b=4, and c=12. 1. Then 212 and 412, but 2∗4=8/12. For all integers a, b, c, and d, if ab and cd, then acbd. = True. bd=ax∗cy=ac∗xy 1. Assume ab and cd. 2. Then b=ax and c=dy for some integers x and y. 3. So bd=ax∗cy=ac(xy) 4. Since xy is an integer, acbd.
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.
1pf  1800pf  Yellow Ceramic Disk or Blue or Yellow Monolithics 
.001; .01; .022; .047; 0.1; 0.47; 1uF (C96 on K2)  Red Monolithics 
Temperature stable caps are marked "NP0", "C0G" or have a black top. 
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.
VALUE  MARKING  VALUE  MARKING  VALUE  MARKING  
1pf; 3pf; 5pf  1; 3; 5 
2.7, 3 or 3.3 pF can be interchanged with each other.
4.7 or 5 pF can be interchanged with each other. 

10 pf  10 or 100  0.001 uF  102  0.10 uF  104  
12 pf  12 or 120  0.0012uF (1200pf)  122  0.12 uF  124  
15 pf  15 or 150  0.0015uF  152  0.15 uf  154  
18 pf  18 or 180  0.0018 uF (1800pf)  182  0.18 uF  184  
22 pf  22 or 220  0.0022uF  222  0.22 uF  224  
27 pf  27 or 270  0.0027uF  272  0.27 uF  274  
33 pf  33 or 330  0.0033 uF  332  0.33 uF  334  
39 pf  39 or 390  0.0039uF  392  0.39 uF  394  
47 pf  47 or 470  0.0047uF  472  0.47 uF  474  
58 pf  58 or 580  0.0056uF  562  0.56 uF  564  
68 pf  68 or 680  0.0068uF  682  0.68 uF  684  
82 pf  82 or 820  0.0082uF  822  0.82 uF  824  
100 pf  101  0.01 uF  103  1uF  105 or 1uf  
120 pf  121  0.012 uF  123  
150 pf  151  0.015 uF  153  
180 pf  181  0.018 uF  183  
220 pf  221  0.022 uF  223  
270 pf  271  0.027 uF  273  
330 pf  331  0.033 uF  333  
390 pf  391  0.039 uF  393  
470 pf  471  0.047 uF  473  
560 pf  561  0.056 uF  563  
680 pf  681  0.068 uF  683  
820 pf  821  0.082 uF  823 
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
Color 
First band (A) 
Second band (B) 
Third band (C) 
Fourth band (D) 

Black 
0 
0 
1 

Brown 
1 
1 
10 
1.00% 
Red 
2 
2 
100 
2.00% 
Orange 
3 
3 
1000 
3.00% 
Yellow 
4 
4 
10000 
4.00% 
Green 
5 
5 
100000 
0.50% 
Blue 
6 
6 
1000000 
0.25% 
Violet 
7 
7 
10000000 
0.10% 
Gray 
8 
8 
100000000 

White 
9 
9 
1000000000 

Gold 



5.00% 
Silver 



10.00% 
(no color) 



20.00% 
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, 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.
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?
Equality ←→ Freedom
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
The Messier objects are celestial 110 objects plotted by comethunter 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 was one of the first people to have developed an idea about atoms.
Born in Texas and raised in Kansas, Dwight D. Eisenhower was one of America’s greatest military commanders and the thirtyfourth 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 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 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.
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:
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 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:
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 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.
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 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 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 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.
[HEAD]–> [ ][ ]–> [ ][/]
[HEAD]–> [ ][ ]–> [ ][ ]–> [Back to HEAD]
[HEAD]<–>[ ][ ]<–>[ ][/]
[HEAD]<–>[ ][ ]<–>[ ][ ]<–>[Back to HEAD]
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
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 packageprivte.
** 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.