Show that [xnyn] 1 (1 − 3x)(1 − y − 3x + 3x2)= 9n

Problem 11757

(American Mathematical Monthly, Vol.121, February 2014) Proposed by I. Gessel (USA).

Let[x^ay^b]f (x, y) denote the coefficient of x^ay^b in the Taylor series expansion off . Show that [xⁿyⁿ] 1

(1 − 3x)(1 − y − 3x + 3x²)= 9ⁿ.

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

Note that

[yⁿ] 1

(1 − 3x)(1 − y − 3x + 3x²)= 1

(1 − 3x)(1 − 3x(1 − x))ⁿ⁺¹

=

∞

X

j=0

(3x)^j

∞

X

k=0

n + k k



(3x(1 − x))^k

=

∞

X

j=0

(3x)^j

∞

X

k=0

n + k k

 (3x)^k

k

X

i=0

k i

 (−x)ⁱ

=

∞

X

j=0

(3x)^j

∞

X

m=0

x^m

m

X

k=0

n + k k

 k m − k



3^k(−1)^m−k.

Hence

[xⁿyⁿ] 1

(1 − 3x)(1 − y − 3x + 3x²) = 3ⁿ

n

X

m=0 m

X

k=0

n + k k

 k m − k

 

−1 3

m−k

= 3ⁿ

n

X

m=0 m

X

k=0

n + m − k m − k

m − k k

 

−1 3

k

= 3ⁿ

n

X

k=0



−1 3

k n

X

m=k

n + m − k m − k

m − k k



= 3ⁿ

n

X

k=0



−1 3

k

n + k k

 n

X

m=k

n + m − k n + k



= 3ⁿ

⌊n/2⌋

X

k=0



−1 3

k

n + k k

2n + 1 − k n + k + 1

 .

Thus, it suffices to show that

S(n) :=

⌊n/2⌋

X

k=0

F (n, k) = 1 where F (n, k) := (−1)^k 3^n+k

n + k k

2n + 1 − k n + k + 1

 .

Following the Wilf-Zeilberger method, let

G(n, k) := k(k − 2(n + 1))

(n + 1)(n + 1 − 2k)·F (n, k) then

F (n + 1, k) − F (n, k) = G(n, k + 1) − G(n, k) for 0 ≤ k < (n − 1)/2.

Hence, if n is even then

S(n + 1) − S(n) =

n/2

X

k=0

(F (n + 1, k) − F (n, k)) = G(n, n/2 + 1) − G(n, 0) = 0,

and, if n is odd,

S(n + 1) − S(n) = F (n + 1, (n + 1)/2) + F (n + 1, (n − 1)/2) − F (n, (n − 1)/2)

+

(n−3)/2

X

k=0

(F (n + 1, k) − F (n, k))

= F (n + 1, (n + 1)/2) + F (n + 1, (n − 1)/2) − F (n, (n − 1)/2) + G(n, (n − 1)/2) − G(n, 0) = 0.

Since S(0) = 1, the identity follows by induction on n.