The Art and Craft of Problem Solving

6.4 RECURRENCE 219

Solution: Define the generating function

f( x) =CO+CIX+C 2 X^2 + ....

Squaring, we have

f(x)^2 = CoCo + (CICO+COCJ)x+ (C 2 CO+CICI +COC 2 )� +'" =CI +C 2 X+C 3 �+""

This implies that

Xf(X)^2 = f(x) -Co = f(x) - 1.

Solving for f(x) by the quadratic formula yields

f(x) =

(^1) ±
VI=4X.
2x
A bit of thinking about the behavior as x approaches 0 should convince you that the
correct sign to pick is negative, i.e.
f(x) -
(^1) -

• VI=4X
  2x

.

Now all that remains is to find a formula for Cn by expanding f(x) as a power

series. We need the generalized binomial theorem (see Problem 9.4. 12 on page 353 ),

which states that

Thus,

(I )a

� (a)(a-I) .. ·(a-n+l) n

+y = 1 + , y.

n_1 n.

JI-4x=I+}: (�)(�

• I) ... (�-n+I)
  (- 4 xt

n?:^1 n!

= 1 + }: (_I)n

• dl)(1)(3)(5;-," (2n- 3)
  (-^4 )n.x"

n?: 1 2 n.

=^1 _ (

2x) � (^1 )(^3 )(^5 )··· (2n - 3)2n-1 (n -I)!

.x"

• I

n nfl (n-I)!(n-I)!

= 1 - (

2x) � (^1 )(^3 )(^5 ) ... (2n-3)(^2 )(^4 ) (^6 ) ... (2n-2)

.x"

_ 1

n nfl (n - (^1) )!(n -I)!
= 1 _ (
2 X) }: (2n
�
(^2) )
xn

• l
  .

n n?: 1 n 1

Finally, we have

f(x) =

(^1) - VI=4X =
! }: (2n -^2 ).x"-^1 ,

2x n n?: 1 n- I

and the coefficient of.x" is

1 ( (^2) (n+l)- 2 )

n+l (n+I)- 1

.