# Sequences and 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.

#### Solution Preview

1. NO.

We write down the first several items of Fibonacci sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

When n=5, A(5)=4*2^3+1=32+1=33 which is not in the above sequence.

So A(n) is not a subsequence of Fibonacci sequence.

2. NO.

Because C(6)=10 does not belong to Fibonacci sequence. Please see the attachment.

3. Proof:

At the end of 0 month, there is no rabbits. So R(0)=0.

At the end of 1 month, there is one pair of rabbits, say P1. So R(1)=1.

At the end of 2 months, P1 do not breed and there is still ...

#### Solution Summary

This is a series of problems regarding sequences and recursive definition.