Guichard-Combinatorics-Graph-Theory · Problem 3.4.9

Generating Functions

Mathematics — Probability · recurrence-relations-fibonacci

Problem

In Fibonacci's original problem, a farmer started with one (newborn) pair of rabbits at month 0. After each pair of rabbits was one month old, they produced another pair each month in perpetuity. Thus, after 1 month, he had the original pair, after two months 2 pairs, three months, 3 pairs, four months, 5 pairs, etc. The number of pairs of rabbits satisfies hn=hn−1+hn−2h_n = h_{n-1} + h_{n-2}, h0=h1=1h_0 = h_1 = 1. (Note that this is slightly different than our definition, in which h0=0h_0 = 0.) Suppose instead that each mature pair gives birth to two pairs of rabbits. The sequence for the number of pairs of rabbits now starts out h0=1h_0 = 1, h1=1h_1 = 1, h2=3h_2 = 3, h3=5h_3 = 5, h4=11h_4 = 11. Set up and solve a recurrence relation for the number of pairs of rabbits. Show also that the sequence satisfies hn=2hn−1+(−1)nh_n = 2h_{n-1} + (-1)^n.

Related theory

Browse the problem library