Mathematical Methods for Physics and Engineering : A Comprehensive Guide

PRELIMINARY ALGEBRA

The first is a further application of the method of induction. Consider the

proposal that, for anyn≥1andk≥0,

∑n−^1

s=0

k+sC

k=

n+kC

k+1. (1.53)

Notice that heren, the number of terms in the sum, is the parameter that varies,

kis a fixed parameter, whilstsis a summation index and does not appear on the

RHS of the equation.

Now we suppose that the statement (1.53) about the value of the sum of the

binomial coefficientskCk,k+1Ck,...,k+n−^1 Ckis true forn=N.Wenextwritedown

a series with an extra term and determine the implications of the supposition for

the new series:

N∑+1− 1

s=0

k+sC

k=

N∑− 1

s=0

k+sC

k+

k+NC

k

=N+kCk+1+N+kCk

=N+k+1Ck+1.

But this is just proposal (1.53) withnnow set equal toN+ 1. To obtain the last

line, we have used (1.52), withnset equal toN+k.

It only remains to consider the casen= 1, when the summation only contains

one term and (1.53) reduces to

kC

k=

1+kC

k+1.

This is trivially valid for anyksince both sides are equal to unity, thus completing

the proof of (1.53) for all positive integersn.

The second result, which gives a formula for combining terms from two sets

of binomial coefficients in a particular way (a kind of ‘convolution’, for readers

who are already familiar with this term), is derived by applying the binomial

expansion directly to the identity

(x+y)p(x+y)q≡(x+y)p+q.

Written in terms of binomial expansions, this reads

∑p

s=0

pC

sx

p−sys

∑q

t=0

qC

tx

q−tyt=

∑p+q

r=0

p+qC

rx

p+q−ryr.

We now equate coefficients ofxp+q−ryron the two sides of the equation, noting

that on the LHS all combinations ofsandtsuch thats+t=rcontribute. This

gives as an identity that

∑r

t=0

pC

r−t

qC

t=

p+qC

r=

∑r

t=0

pC

t

qC

r−t. (1.54)