Our server costs ~$56 per month to run. Please consider donating or becoming a Patron to help keep the site running. Help us gain new members by following us on Twitter and liking our page on Facebook!
October 8, 2016 at 10:15 am (This post was last modified: October 8, 2016 at 10:16 am by robvalue.)
I don't know Maths is fun! I've always said so
Cool stuff about the binomial! I think I remember working out a similar proof when I was bored at college, many years ago. I can't remember if it was exactly the same.
Feel free to send me a private message.
Please visit my website here! It's got lots of information about atheism/theism and support for new atheists.
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).
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.
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.
January 28, 2017 at 10:24 am (This post was last modified: January 28, 2017 at 10:26 am by Kernel Sohcahtoa.)
Hello AF members. When I first made this thread, I had intended it to be one of those threads where people could post endlessly even if there were a long intermission between posts such as this post. Hence, I want to apologize to the staff if I'm breaking the rules by posting this.
With that said, I didn't recall seeing many induction proofs here, so I thought I'd post one for any member who is curious about induction, especially for the younger members (high school) who are getting interested in mathematics. Here it is:
Prove that 1^2+2^2+…+ (n-1)^2 < n^3/3 < 1^2+2^2+…+ n^2 is true for all positive integers n.
Hint: use mathematical induction.
Background on Mathematical Induction
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.
Proof
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.
February 1, 2017 at 8:42 pm (This post was last modified: February 1, 2017 at 10:31 pm by Kernel Sohcahtoa.)
Consider the function θ: P(ℤ) → P(ℤ) defined as θ(X)=X^c (note ℤ is the set of all integers). We can also rephrase this as the function θ from the power set of ℤ to the power set of ℤ is defined as the function θ whose input set X produces an output set equal to the complement of X (or X^c). Now determine if θ is injective, surjective, and bijective. This problem was retrieved via Hammack, Richard. (2013) Book of Proof, 2nd ed. Virginia commonwealth University: published by Richard Hammack, pg 205.
Definitions and Terms
Injective, surjective, and bijective functions.
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
The complement
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.
The law of double complements
(x^c)^c=x
The Power Set
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).
Proof (My attempt)
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.
February 1, 2017 at 10:10 pm (This post was last modified: February 1, 2017 at 10:15 pm by J a c k.)
Heh. I love listening (reading in this case) to smart people talk about smart stuff. Math, techy stuff, physics, you name it. If there was a room full of people having this conversation, I'd probably be sitting in a corner watching intensely and almost excitedly. Carry on.
"Hipster is what happens when young hot people do what old ladies do." -Exian
February 1, 2017 at 10:45 pm (This post was last modified: February 1, 2017 at 10:45 pm by Kernel Sohcahtoa.)
(February 1, 2017 at 10:10 pm)Mamacita Wrote: Heh. I love listening (reading in this case) to smart people talk about smart stuff. Math, techy stuff, physics, you name it. If there was a room full of people having this conversation, I'd probably be sitting in a corner watching intensely and almost excitedly. Carry on.
You're very kind. IMO, you are an intelligent poster of this forum and there are probably many topics that you know about which would cause me to be in awe of you.
With that said, IMO, at best, I have gained an appreciation for mathematics and think it is cool; however, I've got a lot to learn and there are many concepts beyond me, which I will need to master and cultivate before I can be worthy of any sort of merit or whatever. Thanks and Live long and prosper.
Maths is fun! I've always said so 
. Thanks and Live long and prosper.
