Advanced book on Mathematics Olympiad

Combinatorics and Probability 753

=

∑n+^1

k= 0

((

n

k

)

+

(

n

k− 1

))

[x]k[y]n−k+ 1 =

∑n+^1

k= 0

(

n+ 1

k

)

[x]k[y]n+ 1 −k.

The induction is complete.

Second solution: The identity can also be proved by computing(dtd)ntx+yin two different
ways. First,
(
d
dt

)n

tx+y=(x+y)(x+y− 1 )···(x+y−n+ 1 )tx+y−n=[x+y]ntx+y−n.

Second, by the Leibniz rule,

(

d

dt

)n

(tx·ty)=

∑n

k= 0

(

n

k

)((

d

dt

)k

tx

)((

d

dt

)n−k

ty

)

=

∑n

k= 0

(

n

k

)

[x]k[y]n−ktx+y−n.

The conclusion follows.

866.The binomial formula(Q+P)n =

∑n

k= 0

(n

k

)

qQ

kPn−kis of no use because the

variablesQandPdo not commute, so we cannot setP=−Q. The solution relies on
theq-Pascal triangle. But theq-Pascal triangle is written as
(
n
k

)

q

=qk

(

n− 1

k

)

q

+

(

n− 1

k− 1

)

q

.

With the standard convention that

(n

k

)

q=0ifk<0ork>n, we have

∑

k

(− 1 )kq

k(k 2 − 1 )

(

n

k

)

q

=

∑

k

(− 1 )kq

k(k 2 − 1 )

(

qk

(

n− 1

k

)

q

+

(

n− 1

k− 1

)

q

)

=

∑

k

(− 1 )kq

k(k+ 1 )

2

(

n− 1

k

)

q

−

∑

k

(− 1 )k−^1 q

k(k− 1 )

2

(

n− 1

k− 1

)

q

.

Now just shift the index in the second sumk→k+1 to obtain the difference of two
equal sums. The identity follows.

867.LetG(x)=

∑

nynx

nbe the generating function of the sequence. It satisfies the

functional equation

( 1 −ax)G(x)= 1 +bx+bx^2 +··· =

1

1 −bx

.

We find that

G(x)=

1

( 1 −ax)( 1 −bx)

=

A

1 −ax

+

B

1 −bx

=

∑

n

(Aan+Bbn)xn,