Difference Equations and Recursive Relations

Jacob Bernoulli's "Bernoulli numbers" can be expressed with a recursive relation. Since the Bernoulli numbers are useful in determining the MacLaurin expansion of ae^ax/(e^a - 1), one can show that the Bernoulli numbers have the property that Sⁿ_k=0 [(aⁿ⁺¹_k)(B_k)] = 0, where B_k is the k^th Bernoulli number and aⁿ⁺¹_k is the binomial coefficient described below. From this relation it is clear that (aⁿ⁺¹_n)(B_n) + S^n-1_k=0 [(aⁿ⁺¹_k)(B_k)] = 0. Simple algebra with the identity aⁿ⁺¹_n = n + 1 shows that B_n = -(n + 1)^-1 * S^n-1_k=0 [(aⁿ⁺¹_k)(B_k)]. Therefore, if one starts with B₀ = 1, B_n for n > 0 is a linear combination of all preceding Bernoulli numbers.

One can show that B₁ = -1/2 is the only nonzero Bernoulli number with an odd subscript. Also, there is a list of some of the nonzero Bernoulli numbers on the web, but there is considerable disagreement in the indexing sets used to describe the series of Bernoulli numbers. The site with the list of Bernoulli numbers starts with B₂ but labels it B₁. Subsequent Bernoulli numbers are B_2n according to the indexing definition in the list here (about halfway down the page).
(Back to top)
 

Abraham de Moivre had some arithmetic progression.
(Back to top)
 

Sir Isaac Newton contributed the general binomial formula and a method to approximate the zeroes of a once differentiable function.
In 1676 he described some examples of expansions of (a+ab)^x (where x is negative or fractional) in letters to the secretary of the Royal Society to be translated into Latin and forwarded to Leibniz. Newton's formula for the general binomial formula was given as (a+b)^m/n = a^m/n + (ab)[m/n] + (bb)[(m-n)/(2n)] + (gb)[(m-2n)/(3n)] + (db)[(m-3n)/(4n)] + ... In this expression, each greek letter stands for the entire preceeding term in the expansion (that is, a^m/n = a, (ab)[m/n] = b, and so on). Thus, every expansion of a binomial to a fractional or negative integer power is the sum of an infinite series. Here the terms of the infinite series have a recursive relationship from one to the next.

Newton's method for approximating the real roots of a differentiable function uses the tangent line approximation. Consider a differentiable function g(x). Using the tangent line approximation, for a small Dx, g(x+Dx) @ g(x) + g'(x)Dx. If we have an x_n close to some real r such that g(r) = 0, then x_n+1 = x_n - g(x_n) / g'(x_n) is an even better approximation of r. In fact, {x_n} converges to r roughly as the square of n. Unfortunately, Newton's method works only when |x₀ - r| is small. If |x₀ - r| is too large, then {x_n} actually diverges (in this discussion the terms 'sufficiently small' and 'too big' depend heavily on g(x) itself).
(Back to top)
 

Blaise Pascal did considerable work with the binomial coefficients, which are frequently arranged in a format known as Pascal's Triangle. A binomial coefficient aⁿ_k is the coefficient of the a^kb^n-k term in the expansion of (a+b)ⁿ (where n is a nonnegative integer and k is a nonnegative integer less than or equal to n). Pascal was not the first to arrange the binomial coefficients in the triangle below, nor was he the first to notice that the table could be infinitely extended using the recursive relation aⁿ_k = a^n-1_k-1 + a^n-1_k, which was the first partial difference equation ever discovered. What he did was the most detailed study of the relationships between the binomial coefficients. He prove nineteen properties of the binomial coefficients, for instance. Among these were the symmetry of the triangle (that is, aⁿ_k = aⁿ_n-k) and aⁿ_k = Sⁿ_i=k a^i-1_k-1. He also first published the direct formula for aⁿ_k, which is given by in modern notation.
 
 

Pascal's Triangle up to n = 10

1	1	1	1	1	1	1	1	1	1	1
1	2	3	4	5	6	7	8	9	10
1	3	6	10	15	21	28	36	45
1	4	10	20	35	56	84	120
1	5	15	35	70	126	210
1	6	21	56	126	252
1	7	28	84	210
1	8	36	120
1	9	45
1	10
1

(Back to top)
 
 

May the Force be with you.