Purchase Solution

Sequences and recursive definitions

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution

Solution Summary

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

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 ...

Purchase this Solution


Free BrainMass Quizzes
Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Probability Quiz

Some questions on probability