Explore BrainMass
Share

# Recurrence Relation

A recurrence relation is an equation that recursively defines a sequence, once one more initial terms are given. Each further term of the sequence is defined as a function of the preceding terms. The term difference equation is sometimes referred to as a specific type of recurrence relation. However, difference equation is frequently used to refer to any recurrence relation.

An example of a recurrence relation is the logistic map:

Xn+1 = rxn(1-xn)

With a given constant r, given the initial term x0 each subsequent term is determined by this relation. Some simply defined recurrence relations can have very complex behaviours and they are a part of the field of mathematics known as nonlinear analysis. Solving the recurrence relation means obtaining a closed-form solution: a non-linear recursive function of n.

Recurrence relation has many different applications. These can include biological applications, digital signal processing and economics. In biology, some of the best-known difference equations have their origins in the attempt to model population dynamics. The logistical map is used either directly to model population growth, or as a starting point for more detailed models. In digital signal processing, recurrence relations can model feedback in a system, where outputs at one time become inputs for future time. They thus arise in infinite impulse response digital filters. Recurrence relations, especially linear recurrence relations, are used extensively in both theoretical and empirical economics.

### How to cover 9 x 10 chessboard with Tetris pieces

1. Prove or disprove: is it possible to tile a 9 x 10 chessboard with Tetris pieces? 2. Is it possible to perfectly tile a 4 x 7 chessboard with the 7 Tetris pieces?

### Combinatorics, recurrence relation, generating functions

1. Let R(s,t) denote the smallest positive integer p such that the complete graph on p vertices, whose edges are colored red or blue, there always exists either a complete subgraph on s vertices which is entirely blue, or a complete subgraph on t vertices which is entirely red. Show that R(3,4) = 9. 2. Given a positive intege

### Relations and Graph Theory

1. List all the functions from the three element set {1, 2, 3} to the set {a, b}. Which functions, if any, are one-to-one? Which functions, if any, are onto? 2. How many base 10 numbers have 3 digits? How many three-digits numbers have no two consecutive digits equal? How many have at least one pair of consecutive digits equal?

### Predicate logic

PREDICATE LOGIC Note: For your convenience the truth tables are included. You may not need to use all of the columns in the skeleton tables. 1. Use modus ponens or modus tollens to fill in the blanks in the arguments so as to produce a valid inference. If this polygon is a triangle, then the sum of its interior an

### Truth Tables Equivalent Statements

LOGIC 1. Indicate and justify which of the following sentences are statements. a) She is mathematics major. b) 128 = 26 c) x = 26 2. Write the statement bellow in symbolic form using the symbols ~, , and  and the indicated letters to represent component statements. (m = "Juan is a math major", c = "J

### Combinations and Permutations

COUNTING PERMUTATION COMBINATIONS 1. In a monthly test, the teacher decides that there will be three questions, one from each chapter I, II and III of the book. If there are 12 questions in chapter I, 10 in chapter II and 6 in chapter III. In how many ways can three questions be selected? Justify your answer. 2. Find the tot

### One-To-One Functions

FUNCTIONS 1. Find all functions from X = {a, b, c} to Y = {u, v}. 2. Let F and G be functions from the set of all real numbers to itself. Define new functions F - G: R R and G - F: R R as follows: (F - G)(x) = F(x) - G(x) for all x  R, (G - F)(x) = G(x) - F(x) for all x  R. Does F - G = G - F? Explain. 3. Le

### Set Relations Binary Relations

Relations 1. Let C = {2, 3, 4, 5} and D = {3, 4} and define a binary relation S from C to D as follows: for all (x, y)  C  D, (x, y)  S  x  y. a) Write S as a set of ordered pairs. b) Is 2 S 4? Is 4 S 3? Is (4, 4)  S? Is (3, 2)  S? 2. Let A = {3, 4, 5} and B = {4, 5, 6} and let S be the "divides" rel

### Set Theory questions

1. Let T = {m   m = 1 + (-1)i, for some integer i}. Describe T. 2. Let A = {m   m = 2i - 1, for some integer i}, B = {n   n = 3j + 2, for some integer j}, C = {p   p = 2r + 1, for some integer r}, and D = {q   q = 3s - 1, for some integer s}. a) Describe the 4 sets (by enumerat

### Rate of Return Probability Question

Assessing return and risk Tento Manufacturing must choose between two asset purchases. The annual rate of return and the related probabilities are given in the following table. Summarize the firm's analysis to this point. Project 257 Project 432 Rate of return Probabilit

### Capital Asset Pricing Model; Risk Return Analysis

Tony is wondering how much risk he must accept in order to generate a reasonable return on his portfolio. The risk-free return currently is 5 percent. The return on the market portfolio is 16 percent. Use the Capital Asset Pricing Model to calculate the beta coefficient associated with each of the following portfolio returns.

### Using the Recurrence Relation in algebra

Bob deposits quarters and dollar bills into a vending machine to buy snacks. Find a recurrence relation for the number of ways he can deposit 25*n cents into the machine if the order matters. State the recurrence relation and the initial conditions. Then use your recurrence relation to find the number of ways Bob can deposit \$3.

### Recursive and Recurrence

1. Find the sequence for the recursive formula: S_n = -s_n-1 + 9, s_0 = -3 (see the attachment for the full question) 2. True of False a_n = 2 is a solution to the recurrence relation a_n = 2a_n-1 - a_n-2 with initial conditions a_0 = 2 and a_1 = 2. a. True b. False 3. Find a solution to the recurrence relation: a_

### Recursion and Iteration

Can someone please help with my practice questions? I would like details and explanations using words to show how you got the answer. The questions cover the concepts of linear recurrence, iterations, and power functions.

### Recurrence Relations Example Problem

Find the solution to an = 2an-1 + an-2 -2an-3 for n= 3,4,5,..., with a0 = 3, a1=6, and a2=0. Find the solution to an= 5an-2 - 4an-4 with a0 = 3, a1 = 2, a2 = 6, and a3 = 8. (I have attached the full problem below.)

### Recurrence Relations: Fibonacci Numbers

Show that the Fibonacci numbers satisfy the recurrence relation f_n = 5f_n-4 + 3f_n-5 for n = 5, 6, 7,..., together with the initial f_0 = 0, f_1 = 1, f_2 = 1, f_3 = 2, and f_4 = 3. See the attachment for the full question.

### Discrete Math-Induction

A flagpole is n feet tall. On this flag pole we display flags of the following types: red flags that are 1 foot tall, blue flags that are 2 feet tall and green flags that are 2 feet tall. The sum of the heights is exactly n feet. Prove that there are exactly [(2/3)*(2^n)] + [(1/3)*(-1)^n] ways to display the flags.

### First five positive deficient square pentagonal numbers

The m-th number is the number Pm = 1/2 m (3m - 1 ). A pentagonal number is a deficient square if Pm = n^2 - 1 for some integer n. Find the first five positive deficient square pentagonal numbers. The answer should demonstrate in a table with 3 columns how to get the corresponding m, n and Pm for each of the 5 numbers.

### The Newton-Raphson Method: Consider the Function

See the attached file. The Newton-Raphson Method 1. Consider the function . i) Show, graphically or otherwise, that the equation has a root in the interval (1,2). Show that . ii) Use the secant method, with the function f(x) and starting values, 1 and 2, to find an estimate of correct to three decimal places.

### Algebra: Simultaneous Recurrence Relations

Solve the simultaneous recurrence relations given below. a(n) = 3a(n-1) + 2b(n-1) b(n) = a(n-1) + 2b(n-1) a(0) = 1 b(0) = 2

### Recurrence relations - initial conditions

A) Find a recurrence relation for the number of bit strings of length n that contain three consecutive 0s. b) What are the initial conditions? c) How many bit strings of length seven contain three consecutive 0s?

### Recurrence relations, compound interest, polynomials

Please help with the following discrete math involving recurrence relations, compound interest, polynomials, number of combinations and iteration. 14. Individual membership fees at the evergreen tennis club were \$50 in 1970 and have increased by \$2 per year since then. Write a recurrence relation and initial conditions for

### Recurrence relations and generating functions

Let h(sub n) denote the number of ways to perfectly cover a 1 by n board with monominoes and dominoes in such a way that no two dominoes are consecutive. Find, but do not solve, a recurrence relation and initial conditions satisfied by h(sub n) answer: h(subn)= h(subn-1)+h(subn-3), (n>=3) with h(sub0)=1 h(sub1)=1 h(sub2)=

### Recurrence Relation Example

Consider a 1-by-n chessboard. Suppose we color each square of the chessboard with one of the two colors - red and blue. Let h(n) be the number of coloring in which no two squares that are colored red are adjacent. Find a recurrence relation that h(n) satisfies.

### Matrix Relation

5. Let A = { 1, 2, 3, 4 } , and let R be the relation defined on A defined by: R = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,3), (3,4), (1,3), (2,4)} A. Draw the digraph of this relation. B. Which of the properties: reflexive, antisymmetric and transitive are true for the given relation? Begin your discussion by defini

### Iterations and Recurrence Relations

Zebra mussels are fresh water mollusks that attack underwater structures. Suppose that the volume of mussels in a confined area grows at a rate of 0.2% per day (1) If there are now 10 cubic feet of mussels in a lock on the Illinois River at Peoria, Illinois, develop a recurrence relation and initial conditions that represent

### Recurrence relation proof

See attached The functions Tn(x), for n=0, 1, 2...satisfy the recurrence relation....

### Recurrence Relations

Please see the attached file for the fully formatted problems.

### Relations and Partitions

College level proof before real analysis. Please see the attached file.

### List the Ordered Pairs in a Relation on A

College level proof before real analysis. Please give formal proof. Please explain each step of your solution. If you have any suggestion or question to me, please let me know. See the attached file.