Recursive Definitions

I want to get a better understanding of how these problems are done.  

For Exercises #1-3, decide whether the sequences described are subsequences of the Fibonacci sequence, that is, their members are some or all of the members, in the right order, of the Fibonacci sequence.

1.  The sequence A(n), where A(n) = (n-1)2^n-2 + 1, n ≥ 1.  The first four values are 1, 2, 5, 13, which so far form a subsequence of the Fibonacci sequence.

2.  The sequence C(n), where C(n) is the number of ways in which n coins can be arranged in horizontal rows with all the coins in each row touching and every coin above the bottom row touching two coins in the row below it, n ≥ 1.  The first five values are 1, 1, 2, 3, 5, which so far form a subsequence of the Fibonacci sequence.

3.  The original problem posed by Fibonacci concerned pairs of rabbits.  Two rabbits do not breed until they are two months old.  After that, each pair of rabbits produces a new pair each month.  No rabbits ever die.  Let R(n) denote the number of rabbit pairs at the end of n months if you start with a single rabbit pair.  Show that R(n) is the Fibonacci sequence.

For Exercises #4-5, prove the given property of the Fibonacci numbers using the second principle of induction.

4.   A sequence is recursively defined by
T(5) = 6
T(6) = 10
T(n) = 2T(n-2) +2 for n ≥ 7

Prove that T(n) ≥ 2n for n ≥ 7.

5.  A sequence is recursively defined by
T(0) = 1
T(1) = 2
T(n) = 2T(n-1) +T(n-2) for n ≥ 2

Prove that T(n) ≤  (5/2)^n for n ≥ 0.

Attached file(s):

Recursive Probs.doc  View File