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;:::/: