754 Combinatorics and Probability
for someAandB. It follows thatyn=Aan+Bbn, and becausey 0 =1 andy 1 =a+b,
A=aa−bandB=−ab−b. The general term of the sequence is therefore
1
a−b
(an+^1 −bn+^1 ).868.The first identity is obtained by differentiating(x+ 1 )n=
∑n
k= 1(n
k)
xk, then setting
x=1. The answer isn 2 n−^1. The second identity is obtained by integrating the same
equality and then settingx=1, in which case the answer is^2
n+ 1
n+ 1.
869.The identity in part (a) is the Vandermonde formula. It is proved using the generating
function of the binomial coefficients, by equating the coefficients ofxkon the two sides
of the equality(x+ 1 )m+n=(x+ 1 )m(x+ 1 )n.
The identity in part (b) is called the Chu–Vandermonde formula. This time the
generating function in question is(Q+P)n, whereQandPare the noncommuting
variables that describe the time evolution of the position and the momentum of a quantum
particle. They are noncommuting variables satisfyingPQ=qQP, the exponential form
of the Heisenberg uncertainty principle. The Chu–Vandermonde formula is obtained by
identifying the coefficients ofQkPm+n−kon the two sides of the equality
(Q+P)m+n=(Q+P)m(Q+P)n.Observe that the powers ofqarise when we switchP’s andQ’s as follows:
(
m
j
)
qQjPm−j(
n
k−j)
qQk−jPn−k+j=(
m
j)
q(
n
k−j)
qQjPm−jQk−jPn−k+j=q(m−j )(k−j)(
m
j)
q(
n
k−j)
qQkPm+n−k.870.The sum is equal to the coefficient ofxnin the expansion of
xn( 1 −x)n+xn−^1 ( 1 −x)n+···+xn−m( 1 −x)n.This expression is equal to
xn−m·
1 −xm+^1
1 −x( 1 −x)n,which can be written as(xn−m−xn+^1 )( 1 −x)n−^1. Hence the sum is equal to(− 1 )m
(n− 1
m)
ifm<n, and to 0 ifm=n.
871.The sum from the statement is equal to the coefficient ofxkin the expansion of
( 1 +x)n+( 1 +x)n+^1 +···+( 1 +x)n+m. This expression can be written in compact
form as