Chapter 15 Generating Functions642
Reasoning as we did for the Fibonacci recurrence, we have
T.x/ D t 0 C t 1 x C C tnxnC
2xT.x/ D 2t 0 x 2tn 1 xnC
1=.1 x/ D 1 1x 1xnC
T.x/.1 2x/ 1=.1 x/ D t 0 1 C 0x C C 0xnC
D 1;
so
T.x/.1 2x/D
1
1 x