the Binomial theorem

The binomial theorem, for n a natural number,

(a + b)^n = a^n + n a^(n-1) b + n (n-1) a^(n-2) b^2 / 2 + ... + (n! / ((n - i)! i!) a^(n - i) b^i + ... + b^n.

may be proven by Mathematical Induction.

If we set a equal to one and replace b by x, we obtain the power series

(1 + x) ^ n = 1 + n x + n (n - 1) x^2 / 2 + n (n - 1) (n - 2) x^3 / 6 + ... (n! / ((n - i)! i!) x^i + ... + x^n.

By additional Mathematical Induction, it may be shown that this binomial expansion holds for any rational n; however, the series becomes infinite, with a radius of convergence abs(x) < 1. Because of the uniqueness of derivatives, this series is the Taylor series.

For example, take n = 1 / 2 to obtain the Taylor series for a square root

sqrt(1 + x) = (1 + x) ^ (1 / 2) = 1 + (1 / 2) x - (1 / 8) x ^ 2 + (1 / 16) x ^ 3 + ... + ((- 1) ^ i (i - 3 / 2)! / ((- 3 / 2)! i!)) x ^ i + ....

The general term has been written in terms of the factorial of a half-integer. It may be evaluated by means of the gamma function. This series converges for any abs(x) < 1, it does so practically fast only when abs(x) < = 1 / 2. Also, it may be expeditious to split the real and imaginary components.

The ratio of the i-th term to the (i-1)-th term is - (i - 3 / 2) x / i. There in neither the gamma nor the factorial function in this ratio.

Permutations and Combinations

The binomial coefficients are the combinations of n things, taken m at a time

C(n,m) = n! / ((n - m)! m!).

The permutations of n things, taken m at a time, is just m! times the corresponding combinations:

P(n, m) = C(n, m) m! = n! / ((n - m)! m!) m! = n! / (n -m)!

In each of the foregoing, the domain is n in [0, oo) andm in [0, n]. For any i outside of this closed interval, we arbitrarily set the C and P equal to zero.
This equation may be solved for the ratio of the permutations to the combinations as

P(n, m) / C(n, m) = m!,

which is useful for converting the permutations (sometimes easier to calculate) to the corresponding combinations -- just divide by m!.
Combinations are for "without replacement". If we do "with replacement"; then the formula becomes (There is no accepted symbol for this expression.)

n^m.

Pascal Triangle

The Pascal triangle is a table, which happens to be in the shape of a triangle, of the coefficient of the binomial expansion of (x + y)^n, where n is a natural number. These coefficients are the combination C of n things, taken m at a time, namely

C(n, m) = n! / ((n - m)! m!).

The number n of the rows is counted from the top (apex), downward. Thus n is an integer in [1, oo).
The number m of the elements is counted from the left to the right, within a row. Thus m is an integer in [0, n].
The Pascal triangle is constructed by writing a one at each end of each line.
Then, the each element in the body is the sum of the two adjacent elements above it.
It looks something like this:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
and so on.

There are three proofs required.
One. Theorem: The elements of the Pascal triangle, indeed, are the C(n, m).
Two. Theorem: The coefficients of the binomial expansion of (x + y)^n, indeed, are given by the rows of the Pascal triangle.
Three. Theorem: The coefficients of the binomial expansion of (x + y)^n, indeed, are the C(n, m). The proof follows obviously from the preceding two theorems.
The proofs of the first two of these theorems requires Mathematical Induction, facilitated by the following theorems.

Theorem: C(n, m) = C(n, n - m).
Proof: C(n, m) = n! / (m! (n - m)!) = n! / ((n - m)! (n - (n - m))!) = C(n, n - m).
Theorem: C(n, m) = C(n - 1, m - 1) + C(n - 1, m).
Obviously, the domain of n has to be increased by one on the left-side, to become n in [1, oo).
Proof: C(n - 1, m - 1) + C(n - 1, m) =
= (n - 1)! / ((m - 1) ((n - 1) - (m - 1))!) + (n - 1)! / (m! ((n - 1) - m)!)) =
= (n - 1)! (1 / ((m - 1)! (n - m)!) + 1 / (m! ((n - m) - 1)!)) =
= (n - 1)! ((m + (n - m)) / (m! (n - m)!) =
= n! / (m! (n - m)!) = C(n, m).
Theorem: (m + 1) C(n + 1, m + 1) = (n + 1) C(n, m).
Proof: (m + 1) C(n + 1, m + 1) = (m + 1) * (n + 1)! / ((m + 1)! ((n + 1) - (m + 1))!) =
= (m + 1) (n + 1)! / ((m + 1)! (n - m)!) =
= (n + 1) * n! / (m! (n - m)!) = (n + 1) C(n, m).

Mathematical Induction

The Mathematical Induction axiom (of the Peano axiomatization of the natural numbers) states that any subset of the natural numbers has a least element.

The statement of a theorem is defined as a implies b is equivalent to not a or b. Lemma: Double negative. not not a is equivalent to a. Of course, or is commutative. Proof by contra positive employs the theorem of mathematical logic which states that a implies b is equivalent to not b implies not a. Proof: Each is equivalent to not a or b. QED.