|
⇤ ← Revision 1 as of 2026-08-30 01:22:44
Size: 1835
Comment: Initial commit
|
← Revision 2 as of 2026-09-01 02:13:07 ⇥
Size: 2677
Comment: Notes
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 39: | Line 39: |
| === Power Set === This theorem provides a clever proof that, for a [[Analysis/Set|set]] of ''n'' elements, the [[Analysis/PowerSet|power set]] has ''2^n^'' elements. Clearly there is only one way to select zero elements from ''n''. Then there are ''n'' ways to select one element from ''n''. This can be continued up to selecting ''n'' elements from ''n'' (clearly one again) and the total number of elements in the power set is the sum across all these selections. This can be represented by the series: {{attachment:powersum.svg}} The only difference between this expression and the binomial theorem is the lack of any ''a^n-k^b^k^'' term. The only reason these could be excluded entirely is if ''a = b = 1'', in which case the binomial theorem becomes: {{attachment:powerbin1.svg}} {{attachment:powerbin2.svg}} |
Binomial Theorem
The binomial theorem is a method for expanding binomial expression.
Description
Consider the binomial expression (a + b)n. It expands to a sum of terms that are all of the form an-kbk. (Or equivalently, akbn-k.) There are always n+1 different forms of terms in the expression.
The number of terms that are of the form an-kbk for a specific value of k is given by a combination. For example, consider (a + b)2; the number of terms that are of the form a0b2 = b2 is 1.
The number of terms that are of the form a2b0 = a2 is also 1.
(It should be apparent that an-kbk and akbn-k are still equivalent.)
More generally, for a specific value of k, the number of terms in the expansion of (a + b)n that are of the form an-kbk is given by:
(And the equivalence of an-kbk and akbn-k is now proven generally by Pascal's rule.)
The original binomial expression (a + b)n can therefore be solved as a sum over all values of k from zero to n.
The number of terms of a specific form is a binomial coefficient.
Power Set
This theorem provides a clever proof that, for a set of n elements, the power set has 2n elements.
Clearly there is only one way to select zero elements from n. Then there are n ways to select one element from n. This can be continued up to selecting n elements from n (clearly one again) and the total number of elements in the power set is the sum across all these selections.
This can be represented by the series:
The only difference between this expression and the binomial theorem is the lack of any an-kbk term. The only reason these could be excluded entirely is if a = b = 1, in which case the binomial theorem becomes:
Pascal's Triangle
Pascal's triangle is formed by rows of binomial coefficients; the nth row (starting at 0) is composed of the binomial coefficients for the binomial expression.
Consider:
(a+b)0 = (1)
(a+b)1 = (1)a + (1)b
(a+b)2 = (1)a2 + (2)ab + (1)b2
(a+b)3 = (1)a3 + (3)a2b + (3)ab2 + (1)b3
And compare this to:
