I thought it would be useful to review some basic equations. These are presented as a series of lemmas.
Lemma 1: (a + b)2 = a2 + 2ab + b2
(a + b)2 = (a + b)(a + b) = a(a + b) + b(a + b) = a2 + ab + ab + b2 = a2 + 2ab + b2.
QED
Lemma 2: (a + b)(a - b) = a2 - b2
(a + b)(a - b) = a(a - b) + b(a - b) = a2 - ab + ab - b2 = a2 - b2
Corollary 2.1: a4 - b4 = (a - b)(a + b)(a2 + b2)
By Lemma 2, a4 - b4 = (a2 - b2)(a2 + b2)
Applying Lemma 2 again, gives us:
a4 - b4 = (a - b)(a + b)(a2 + b2)
Lemma 3: a3 + b3 = (a + b)(a2 - ab + b2)
(a + b)(a2 - ab + b2 ) = a(a2 - ab + b2) + b(a2 - ab + b2) =
a3 - a2b + ab2 + a2b -ab2 + b3 = a3 + b3
Corollary 3.1: a3 - b3 = (a - b)(a2 + ab + b2)
Let b' = -b so that a3 - b3 = a3 + (b')3
By Lemma 3: a3 + (b')3 = (a + b')(a2 - ab' + (b')2) = (a - b)(a2 + ab + b2)
QED
Lemma 4: a5 + b5 = (a + b)(a4 - a3b +a2b2 - ab3 + b4)
(a + b)(a4 - a3b +a2b2 - ab3 + b4) =
=a(a4 - a3b +a2b2 - ab3 + b4) + b(a4 - a3b +a2b2 - ab3 + b4) =
=a5 - a4b + a3b2 - a2b3 + ab4 + a4b - a3b2 + a2b3 - ab4 + b5 =
=a5 + b5
QED
Lemma 4: n ≥ 5 → an + bn = (a + b)(a(n-1) - a(n-2)b + ... - ab(n-2) + b(n-1))
(a + b)(a(n-1) - a(n-2)b + ... -ab(n-2) + b(n-1)) =
a(a(n-1) - a(n-2)b + a(n-3)b2... -ab(n-2) + b(n-1)) +
b(b(n-1)+a(n-1) - a(n-2)b + ...+a2b(n-3) -ab(n-2)) =
an - a(n-1)b + a(n-2)b2 + ... -a2b(n-2) + ab(n-1) +
bn + a(n-1)b - a(n-2)b2 + ... + a2b(n-2) - ab(n-1) =
an + bn
QED
Lemma 5: a - b divides an - bn
Proof:
(1) Let n = be the highest number where this is true.
(2) We know that n is at least 2 since a2 - b2 = (a - b)(a + b)
(3) To complete this proof, we need to show that a - b divides an+1 - bn+1
(4) We know that (a-b)(an) = an+1 - anb and we know that (a-b)(bn) = abn - bn+1
(5) So that an+1 - bn+1 - (a - b)(an) - (a-b)(bn) = anb - abn = ab(an-1 - bn-1)
(6) So that:
an+1 - bb+1 = (a-b)(an + bn) - ab(an-1 - bn-1)
(7) Since n ≥ 2, we know that a-b divides an-1 - bn-1.
QED
Tuesday, August 30, 2005
Factorials
A factorial is an equation that is abbreviated by a number followed by an ! such as:
2!
The idea behind a factorial is very simple. It is a shorthand for a series of multiplications where each multiple is one less than the previous value.
For example:
1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
Factorials are often used in problems of permutations.
Let's start with a situation where we won't need factorials. Assuming that we have 5 roles and 5 people and each person can take any role and can take as many roles as they want. How many different permutations are there?
There are 5 ways to divide up the first role, 5 ways to divide up the second role, and so on. The answer turns out to be: 5 * 5 * 5 *5 *5 = 55 [If you need a review of exponents, review here]
What if we say that each person can only take one role. In other words, we are taking 5 people and dividing them up into 5 roles. In this case, the following happens:
There are 5 ways to divide up the first role, but only 4 ways to divide up the second role, and then 3 ways to divide up the third role, etc. The answer turns out to be 5 * 4 * 3 * 2 * 1 = 5!.
We can generalize this point and make it into an exact equation. For any set of n elements,
there are exactly n! ways of ordering it. This is easy to show.
Lemma 1: For a set of n elements, there are n! ways of ordering all n elements.
For the first element, we have n possible choices.
For the second element, we have n-1 possible choices.
And so on until we get the last element and we have only 1 choice.
So, the total number of thoices is n * (n-1) * (n-2) * ... * 1 which equals n!
QED
Lemma 2: For a set of n elements, there are n!/(n-m)! ways to to order m elements.
(1) There are two cases that need to be considered.
Case I: m = n
Case II: m is less than n
(2) For m = n, we know that there are n! ways to order the elements (Lemma 1)
n!/(n-n)! = n!/(0!) = n!/1 = n!. (Note: 0! is defined to equal 1)
This proves Case I.
(3) For m is less than n, we start by dividing all combinations by the first m elements.
(4) When we do this, we find that for each m sequence of elements, there are (n-m)! ways to select the remaining elements after we have selected the first m elements. (Lemma 1)
(5) Now, if each of these groups have (n-m)! elements, then we can get the total number of groups by diving n! by this value, that is: n!/(n-m)!.
QED
Lemma 3: For a set of n elements, there are n!/[m!(n-m)!] ways to select an unordered set.
(1) We can prove this using the same two cases:
Case I: m = n
Case II: m is less than n
(2) For Case I, there is only 1 way to select n items from a set of n elements.
n!/[n!(n-n)!] = n!/[n!0!] = n!/n! = 1.
(3) For case II, we take our n!/(n-m)! sets and organize them into groups where they have the same set of elements. For example, if we had 3 elements, would group {1,2,3} in the same group as {2,1,3} and {3,1,2} and {3,2,1}.
(4) For each group of m elements, there are m! ways to order them (Lemma 1)
(5) This means that the total number of groups in (3) is [n!/(n-m)!]/m! which is mathematically the same as: n!/[m!(n-m)!].
QED
Factorials are also used in the very important Binomial Theorem which I will talk about in a future blog.
2!
The idea behind a factorial is very simple. It is a shorthand for a series of multiplications where each multiple is one less than the previous value.
For example:
1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
Factorials are often used in problems of permutations.
Let's start with a situation where we won't need factorials. Assuming that we have 5 roles and 5 people and each person can take any role and can take as many roles as they want. How many different permutations are there?
There are 5 ways to divide up the first role, 5 ways to divide up the second role, and so on. The answer turns out to be: 5 * 5 * 5 *5 *5 = 55 [If you need a review of exponents, review here]
What if we say that each person can only take one role. In other words, we are taking 5 people and dividing them up into 5 roles. In this case, the following happens:
There are 5 ways to divide up the first role, but only 4 ways to divide up the second role, and then 3 ways to divide up the third role, etc. The answer turns out to be 5 * 4 * 3 * 2 * 1 = 5!.
We can generalize this point and make it into an exact equation. For any set of n elements,
there are exactly n! ways of ordering it. This is easy to show.
Lemma 1: For a set of n elements, there are n! ways of ordering all n elements.
For the first element, we have n possible choices.
For the second element, we have n-1 possible choices.
And so on until we get the last element and we have only 1 choice.
So, the total number of thoices is n * (n-1) * (n-2) * ... * 1 which equals n!
QED
Lemma 2: For a set of n elements, there are n!/(n-m)! ways to to order m elements.
(1) There are two cases that need to be considered.
Case I: m = n
Case II: m is less than n
(2) For m = n, we know that there are n! ways to order the elements (Lemma 1)
n!/(n-n)! = n!/(0!) = n!/1 = n!. (Note: 0! is defined to equal 1)
This proves Case I.
(3) For m is less than n, we start by dividing all combinations by the first m elements.
(4) When we do this, we find that for each m sequence of elements, there are (n-m)! ways to select the remaining elements after we have selected the first m elements. (Lemma 1)
(5) Now, if each of these groups have (n-m)! elements, then we can get the total number of groups by diving n! by this value, that is: n!/(n-m)!.
QED
Lemma 3: For a set of n elements, there are n!/[m!(n-m)!] ways to select an unordered set.
(1) We can prove this using the same two cases:
Case I: m = n
Case II: m is less than n
(2) For Case I, there is only 1 way to select n items from a set of n elements.
n!/[n!(n-n)!] = n!/[n!0!] = n!/n! = 1.
(3) For case II, we take our n!/(n-m)! sets and organize them into groups where they have the same set of elements. For example, if we had 3 elements, would group {1,2,3} in the same group as {2,1,3} and {3,1,2} and {3,2,1}.
(4) For each group of m elements, there are m! ways to order them (Lemma 1)
(5) This means that the total number of groups in (3) is [n!/(n-m)!]/m! which is mathematically the same as: n!/[m!(n-m)!].
QED
Factorials are also used in the very important Binomial Theorem which I will talk about in a future blog.
Subscribe to:
Posts
(
Atom
)