Mathematics for Computer Science

Chapter 15 Generating Functions660

(a)Give a linear a recurrence forrn.

(b)Express the generating functionR.x/WWD

P 1

0 rnx

nas a quotient of polyno-

mials or products of polynomials. You donothave to find a closed form forrn.

Problem 15.22.
Define theTriple FibonaccinumbersT 0 ;T 1 ;:::recursively by the rules

T 0 DT 1 WWD3;

TnWWDTn 1 CTn 2 (forn 2 ): (15.29)

(a)Prove that all Triple Fibonacci numbers are divisible by 3.

(b)Prove that the GCD of every pair of consecutive Triple Fibonacci numbers is
3.

(c)Express the generating functionT.x/for the Triple Fibonacci as a quotient of
polynomials. (You donothave to find a formula forŒxnçT.x/.)

Problem 15.23.
Define theDouble FibonaccinumbersD 0 ;D 1 ;:::recursively by the rules

D 0 DD 1 WWD1;

DnWWD2Dn 1 CDn 2 (forn 2 ): (15.30)

(a)Prove that all Double Fibonacci numbers are odd.

(b)Prove that every two consecutive Double Fibonacci numbers are relatively
prime.

(c)Express the generating functionD.x/for the Double Fibonacci as a quotient
of polynomials. (You donothave to find a formula forŒxnçD.x/.)

Problems for Section 15.5

Practice Problems

Problem 15.24.
In the context of formal series, a numberrmay be used to indicate the sequence

.r;0;0;:::;0;:::/: