bisection method 45

3xa2+ a3are used in elementary

ALGEBRA

. These are

both special cases of the general binomial theorem that

asserts, for any positive integer n, we have:

Here each number is a

COMBINATORIAL

COEFFICIENT

, also called a binomial coefficient.

The binomial theorem is proved by examining the

process of

EXPANDING BRACKETS

, thinking of the quan-

tity (x+ a)nas a product of nfactors: (x+ a)(x+ a)…

(x+ a). To expand the brackets, one must select an entry

from each set of parentheses (“x” or “a”), multiply

together all the selected elements, and add together all

possible results. For example, there is one way to obtain

the term xn: select xfrom every set of parentheses.

There are nways to create a term of the form xn–1a:

select afrom just one set of parentheses, and xfrom the

remaining sets. In general there are ways to select k

as and n– k xs. Thus, in the expansion, there will be

terms of the form xn–kak.

The combinatorial coefficients are the entries of

PASCAL

’

S TRIANGLE

. The binomial theorem applied to

(1 + 1)nexplains why the elements of each row of Pas-

cal’s triangle sum to a power of two:

Applying the theorem to (1 – 1)nexplains why the

alternating sum of the entries is zero:

Applying the theorem to (10 + 1)nexplains why the

first few rows of Pascal’s triangle resemble the powers

of 11:

112= (10 + 1)2= 100 + 2 ×10 + 1

113= (10 + 1)3= 1,000 + 3 ×100 + 3 ×10 + 1

114= (10 + 1)4= 10,000 + 4 ×1,000 + 6 ×100 + 4

×10 + 1

(The correspondence would remain valid if we did not

carry digits when computing higher powers of 11.)

The binomial theorem can be used to approximate

high powers of decimals. For example, to estimate

(2.01)10 we observe:

2.0110 = (2 + 0.01)10

= 210 + 10 ×29×0.01 + 28+ 45 ×28×0.012+ …

≈1024 + 10 ×512 ×0.01 + 45 ×256 ×0.00001

= 1024 + 51.2 + 1.152

≈1076

In 1665 S

IR

I

SAAC

N

EWTON

, coinventor of

CALCU

-

LUS

, discovered that it is possible to expand quantities

of the form (x+ a)rwhere ris not equal to a whole

number. This leads to the generalized binomial theorem:

If ris an arbitrary real number, and |x|< |a|,

then:

The formula is established by computing the T

AYLOR

SERIES

of f(x) = (x+ a)rat x= 0. In 1826 Norwegian

mathematician N

IELS

A

BEL

proved that the series con-

verges for the range indicated. Notice that if ris a posi-

tive integer, then the theorem reduces to the ordinary

binomial theorem. (In particular, from the n+ 1’th

place onward, all terms in the infinite sum are zero.)

The combinatorial coefficients arising in the

binomial theorem are sometimes called binomial coeffi-

cients. The generalized combinatorial coefficients appear

in expansions of quantities of the type (x+ y+ z)nand

(x+ y+ z+ w)n, for example.

See also

COMBINATION

.

bisection method (dichotomous line search, binary line

search) Often one is required to find a solution to an