---

 

For this proof, we will take the left hand side (LHS) and transform it into the right hand side (RHS) via a series of equalities.

Now, you will see some transformations of factorials (factorials have the ! sign) in this proof.  Most notably, we will be making use of the fact that n!=n*(n-1)! (Lipschutz, Discrete Mathematics, 1992, pg 244).  To understand our fact in bold, suppose we have 4!.  Now, 4! is equal to 4*3*2*1=24.  Now, observe that if we factor out the four, we get 4*(4-1)! or 4*3! or 4*(3*2*1) or 4*6=24 (note 3!=3*2*1=6). Thus, in both instances we got the same result. Also, on a side note, remember that 1! and 0! both equal one.

Now, remember anything of the form C(this,that) can be represented as: (this)!/[(that)!*(this - that)!].  Also note that C(n,k)= n!/[k!*(n-k)!]. (Hammack, Book of Proof, 2013, pg 76).
 

---

---

1)Thus, C(n-1,k-1) + C(n-1,k) =(n-1)!/[(k-1)!*((n-1) - (k-1))!] + (n-1)!/[k!*(n-1-k)!]

2)=(n-1)!/[(k-1)!*(n-k)!] + (n-1)!/[k!*(n-k-1)!] 

Via the commutative law of addition, we can rewrite n-1-k as n-k-1, as it represents the same sum: n+(-k) + (-1) = n+(-1)+(-k).  Now, in order to get a common denominator in both terms, we will need to multiply the first fraction by k/k and the second fraction by (n-k)/(n-k).  This will make sense, in a bit.

3)=k*(n-1)!/[k*(k-1)!*(n-k)!] + (n-k)*(n-1)!/[k!*(n-k)*(n-k-1)!]. 

Now use the fact that n!=n*(n-1)! and apply it to the portions in bold. Also, notice in the second fraction, that via the commutative law of multiplication, we can multiply the three terms in the denominator in any order and get the same product, so writing the denominator as  k!*(n-k)*(n-k-1)! makes it easier to spot the rule.

4)= k*(n-1)!/[k!*(n-k)!] + (n-k)*(n-1)!/[k!*(n-k)!].  Notice that we now have a common denominator.
5)=k*(n-1)! + (n-k)*(n-1)!/[k!*(n-k)!] Now factor (n-1)! out of the numerator
6)=(n-1)!*(k+n-k)/[k!*(n-k)!] simplify the numerator
7)= n*(n-1)!/[k!*(n-k)!] use our fact in bold
8)=n!/[k!*(n-k)!]
9)=C(n,k)

Hence, we have transformed the LHS into the RHS, so the proof is complete.

---

---

Suppose we wanted to prove that a particular statement was true for all positive integers.  Manually going through each integer would take forever and there are probably better things you could do with your time.  As a result, mathematical induction is a tool that allows one to prove such a statement via the following process.  First we need to plug any integer into the equation (usually the integer 1) in order to verify that it is true (this is the basis step).  The next step is the inductive step.  First we make an inductive hypothesis by assuming that the particular statement is true for some integer, say k.  Next, we must show that our inductive hypothesis implies that k+1 is also true for this same statement.

Now, induction makes more sense if we think of all of the integers as dominoes, which are set up in such a way that if you knocked any one down, then all of them would go down.  Hence, by assuming that the statement is true for k and verifying that it is true for k+1, this shows that k knocks down k+1, and as a result, all of the positive integers n must also get knocked down.

---

---

We will use mathematical induction to prove this statement

Basis step.  Let n=1.  Then (1-1)^2 < 1^3/3 < 1^2 or 0 < 1/3 < 1 which is true.

Inductive Step. 


Inductive Hypothesis.  Let’s assume that 1^2+2^2+…+ (k-1)^2 < k^3/3 < 1^2+2^2+…+ k^2 is true for a positive integer k.  As a result, we must show that this implies 1^2+2^2+…+ (k+1-1)^2 < ( k+1)^3/3 < 1^2+2^2+…+ (k+1)^2 or 1^2+2^2+…+ k^2 < ( k+1)^3/3 < 1^2+2^2+…+ (k+1)^2.  Once we demonstrate this then the proof will be complete.

Observe that 1^2+2^2+…+ (k+1-1)^2 = 1^2+2^2+…+ k^2.  Now, since 1^2+2^2+…+ (k-1)^2 < k^3/3, then it must be the case that 1^2+2^2+…+ k^2 < ( k+1)^3/3.  Furthermore, since k^3/3 < 1^2+2^2+…+ k^2, then it must be that (k+1)^3/3 < 1^2+2^2+…+ (k+1)^2. 

Now, we can also say that 1^2+2^2+…+ (k+1-1)^2 = 1^2+2^2+…+ k^2 ≥  k^3/3 < (k+1)^3/3  ≥ 1^2+2^2+…+ k^2  < 1^2+2^2+…+ (k+1)^2.
Hence, 1^2+2^2+…+ k^2 < ( k+1)^3/3 < 1^2+2^2+…+ (k+1)^2. 
Consequently, 1^2+2^2+…+ (n-1)^2 < n^3/3 < 1^2+2^2+…+ n^2 is true for all positive integers n.

---

---

Suppose we have a function f: A→B.  

To show that f is injective, we must show that if x does not equal y for any x,y in A,  then this implies that f(x) does not equal f(y) in B.  An easier way to show if f is injective is if we take the contrapositive of the approach stated above, which is if f(x)=f(y) then x=y.  Thus, we can show that f is injective if we can demonstrate that f(x)=f(y) implies that x=y.

To show that f is surjective. We need to find an a in A or a ∈ A for which f(a)=b∈B.  In other words, for every b output that is in the range of B, we must be able to link them to some a input in A which yields f(a)=b. 

To show if a function is bijective, we will need to show that f is both injective and surjective.  For example, the function f: ℤ→ℤ defined as  f(x)=x is a bijective function, as every x value will have exactly one y value in the range (injective), which means that every y value in the range can be mapped to some x value in the domain (surjective); whereas the function f: ℕ→ℤ defined as f(x)=x would be injective and not surjective.*  Clearly, every x value in the domain will have exactly one y value in the range, so f is injective.  However, Let -2∈ ℤ.  Then there is no x∈ ℕ which produces -2∈ℤ. Hence, f is not surjective.


*note ℕ is the set of all natural numbers or the set of all positive integers

---

---

Suppose we have some set S that is a subset of some universal set U.  Then the complement of S or S^c is the set containing all of the elements that are not in S or U − S.

---

---

(x^c)^c=x

---

---

Suppose that we have some set S.  The power set of S or P(S) is the set that contains all of the subsets of S.  For example, let S={a,b}.  Since S contains two elements (or, it’s cardinality or order is 2) then we can determine the number of elements in the power set from the following equation: the order of P(S) equals 2^n, where n represents the order of the set S.  Thus, in our example, the number of elements in P(S) is 2^2=4.  These elements would be ∅ (the empty set), {a}, {b}, {a,b}.*  Hence, P(S)={ ∅, {a}, {b}, {a,b}}.

*please note that a (or b for that matter) is an element of S but it is not an element of P(S).  Remember that P(S) is the set containing all of the subsets of S; thus, the elements of P(S) are the various subsets in S.  As a result, {a} or the set containing a, would be an element in P(S).

---

---

i)  Let X and Y be two subsets of ℤ or X,Y ⊆ ℤ.  Then X and Y are two elements in P(ℤ) or X,Y ∈ P(ℤ).   Now, if θ(X)= θ(Y), then this means that X^c=Y^c.  Now, from the law of double complements, we can take the complement of both sides of the equation which yields (X^c)^c=(Y^c)^c or X=Y.  So, θ is injective. 


ii)  Let X⊆ ℤ.  Then X ∈ P(ℤ).  Now suppose a is an element in X.  Now, this means that the set containing a or {a} is in P(X).  Since P(X) is the set of all subsets in X, then P(X) is a subset of P(ℤ) or the set containing all of the subsets in ℤ; thus, {a} is also an element in P(ℤ).  Now, since θ(X)=X^c, this means that inputting X ∈ P(ℤ) into θ  will produce an output set equal to X^c∈ P(ℤ) containing all of those elements that are not in X or ℤ−X.  Consequently, θ would not be able to produce {a}.  However, we have established that {a}∈ P(ℤ).  Therefore, there is no X for which θ(X)={a}. Hence, θ is not surjective. 


iii) From parts one and two, we can conclude that θ is injective but not surjective, which means that θ is not a bijective function.

---