# What is Recurrence relations: Definition and 50 Discussions

In mathematics, a recurrence relation is an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given; each further term of the sequence or array is defined as a function of the preceding terms.
The term difference equation sometimes (and for the purposes of this article) refers to a specific type of recurrence relation. However, "difference equation" is frequently used to refer to any recurrence relation.

View More On Wikipedia.org

18. ### Learning Recurrence Relations: Challenges & Solutions

Homework Statement : [/B] I am just learning recurrence relations, and they are proving challenging.Homework Equations -- [/B]Let's have xn = 3xn-1 + 6xn-2. I wanted to look at it with two scenarios. The first is x0 = 1 and x1 = 3. The second is x1=3 and x2 = 4 The Attempt at a Solution Is...
19. ### Question on solving linear recurrence relations

Why does the characteristic equation of a linear recurrence relation always look like an = series of constants multiplied by a number raised to n
20. ### Recurrence relations with rabbits pairs

A single pair (male and female) of rabbits is born at the beginning of the year. Assume the following: 1) Each pair is not fertile for their first month bet thereafter give birth to four new male/female pairs at the end of every month 2) no rabbits die a) let r_{n} be the number of pairs of...
21. ### Nonhomogeneous recurrence relations

Homework Statement Solve the recurrence relation an = 3an−1 −2an−2 +3, a0 = a1 = 1.Homework Equations an = general solution + particular solutionThe Attempt at a Solution I started with finding the general solution, which was easy. it ended up being A12n + A0 now I am having trouble solving...
22. ### MacroEcon, Stock Prices, Recurrence Relations (and Linear Algebra?)

Homework Statement This is a question from an upper level econ course that is giving me quite a bit of trouble. Fluency in linear algebra is assumed for the course. I'm taking a linear algebra course for the first time this semester so I'm still scrambling to learn the basics. If anyone has a...
23. ### MHB Solving Recurrence Relations: Are My Results Right?

Helloo! I have to solve the following recurrence relations: (a) T(n)=sqrt(2)*T(n/2)+lgn (b) T(n)=3*T(n/4)+nlgn (c) T(n) 3*T(n/3)+n/2 (d) T(n)=5*T(n/2)+Θ(n) (e) T(n)=9*T(n/3)+O(n^2) Could you tell me if my results are right? Using the master theorem I found: (a)T(n)=Θ(sqrt(n)) (b)T(n)=Θ(nlgn)...
24. ### MHB Bryan's question at Yahoo Answers regarding linear recurrence relations

Here is the question: Here is a link to the question: Discrete Mathematics Question? - Yahoo! Answers I have posted a link there to this topic so the OP may find my response.
25. ### Recurrence relations for Associated Legendre Polynomials

Homework Statement I'm working on problem 6.11 in Bransden and Joachain's QM. I have to prove 4 different recurrence relations for the associate legendre polynomials. I have managed to do the first two, but can't get anywhere for the last 2 Homework Equations Generating Function: T(\omega...
26. ### Recurrence relations discrete math problem

Homework Statement Find the general solution to the following recurrence relations (defined n≥2). c) an=6an-1-9an-2+8n+4 Homework Equations The Attempt at a Solution an=6an-1-9an-2+8n+4 8n+4= an -6an-1+9an-2 R2-6R+9=0 R=3,3 So hn=A(3)n+B(3)n Assume pn=Cn+Cn2 → This is where I got...
27. ### Recurrence relations - intuition

Hi My calculus textbook is completely crap at explaining recurrence relations. I know the theorems needed to solve difference equations analytically, but I do not understand why they are true. What websites and/or books can I read to get a better intuitive understanding of recurrence...
28. ### Solving Recurrence Relation: a_n+3a_{n-1}-10a_{n-2}=2^n

Homework Statement a_n+3a_{n-1}-10a_{n-2}=2^n The Attempt at a Solution I missed the lectures that addressed how to solve these kinds of problems, and while studying my recommended textbook it only went as far as solving recurrence relations that are equal to 0 as opposed to 2n. I...
29. ### Probability question involving recurrence relations

Homework Statement [PLAIN]http://img812.imageshack.us/img812/5261/unleduqi.png Homework Equations The Attempt at a Solution Can anyone help with part (a)ii, is pk=(1/2)^k? I can't see how to find qk
30. ### Novice in Recurrence Relations

I am totally new to this area, and have some major trouble understanding how recurrence relations were derived from the problems, what to do and what's not. Really appreciate any guidance!For example: Give a Ternary String (containing only 0s, 1s, or 2s), we have to find out the recurrence...
31. ### Trouble with Recurrence Relations?

1. I am trying to practice solving recurrence relations but get stuck when it comes to generalizing the last part of them and would be grateful if someone could offer some help. I'm not very good with series which is why I may be having some problems with them. Here are a few examples if its...
32. ### Tiling a 2x7 Grid with 1x1 and 1x2 Tiles: Finding the Number of Tilings

\textup{A 2 x 7 rectangle has tiling with 1 x 1 and 1 x 2 tiles (singletons and doubletons).} \textup{How many such tilings of a 2 x 7 grid are there?} \textup{Let }a_{n}\textup{ be the number of tilings of a 2 x n grid using 1 x 1 and 1 x 2 tiles so that the} \textup{two rightmost squares...
33. ### Recurrence relations in asymptotic regime

Homework Statement I'm solving the quantum harmonic oscillator. And I'm solving Schrodinger equation. So I came up to one part where I have to use power series method of solving DE (that or Frobenius would probably work just fine). Now I have the recurrence relation...
34. ### Diagonalising Matrices / Recurrence Relations

Homework Statement [PLAIN]http://img530.imageshack.us/img530/6672/linn.jpg The Attempt at a Solution For parts (a) and (b) I've found the eigenvalues to be -\frac{1}{3} and -1 with corresponding eigenvectors \begin{bmatrix} -1 \\ 3 \end{bmatrix} and \begin{bmatrix} -1 \\ 1...
35. ### How do you solve third order recurrence relations?

I know how to solve second order ones, but how would you solve third order ones? Because the characteristic polynomial would have a third degree so how can one find the roots? I have looked everywhere online to find out but I can't find anything. Please Please tell me!
36. ### Spring-Mass-Damper by Recurrence Relations

Homework Statement Solve the Mass-Spring-Damper Differential equation mx''+bx'+kx=exp(-t)cos(t) (Where x'' is d2x/dt2 etc, don't know how to do the dots above :confused:) I understand how to solve this problem, but the thing that confuses me is that the right is in terms of "t"...
37. ### Expected values and recurrence relations

I'm really puzzled about this one. Say you have a discrete, nonnegative random variable N where the probability pn = P{N=n} satisfies the recurrence relation p_{n+2} + r p_{n+1} + s p_n = 0 for n = 0, 1, 2, ...; p0 and p1 are given. How do you find the expectation E[N] without solving...
38. ### Formal power series and non/homogeneous recurrence relations

Homework Statement Homework Equations We're using generating functions, and recurrence relations of homogeneous and non-homogeneous types The mark allocation is 2, 3, 3 and 2 The Attempt at a Solution I think I've done the first part correctly. The closed form is in terms...
39. ### Generating functions and Recurrence relations using the Fibonacci sequence

We're using generating functions, and recurrence relations of homogeneous and non-homogeneous types The mark allocation is 2, 3, 3 and 2 The Attempt at a Solution I think I've done the first part correctly. The closed form is in terms of z, right? I get: F(z) = z / (1 - z - z2)...
40. ### Solving Recurrence Relation for Letter Sequences with A, B, C

Hello: I am asked to find a recurrence relation for the number of n letter sequences composed of A, B, C where every A that is not in the last position is followed by a B. So, would this be: A| (we have A(n-2) sequences) + 0 if A is in the last position B| we have A(n-1) C| we have...
41. ### Power series recurrence relations

Homework Statement In the following series': http://image.cramster.com/answer-board/image/cramster-equation-2009410014306337491927047975008434.gif According to my book, we only have a common range of summation here for n >= 2. Therefore we need to treat n = 0 and n = 1 separately...
42. ### Can 2-Index Recurrence Relations with Constant Coefficients Be Solved Generally?

Is there a general method for solving 2-index recurrence relations with constant coefficients? Here is one I would like to solve a_{m,n} = \frac{xa_{m-1,n} + ya_{m,n-1} + 1}{x+y} for m,n > 0 with initial conditions a_{m,0} = m/x and a_{0,n} = n/y. Hoping for an analogy with...
43. ### Recurrence Relations, finding f(n)

Homework Statement Find f(n) when n = 2^k, where f satisfies the recurrence realtion f(n) = f(n/2) +1 with f(1) = 1 Homework Equations f(n) = a*f(n/b) + c when n = b^k, where k is a positive integer, f(n) = C1n^(log a base b) + C2 C1 = f(1) +c/( a-1) and C2 = -c/ (a-1) keep in mind...
44. ### Mathematica Solve recurrence relations using Mathematica

Hello, I was hoping someone could help point me in the right direction. I am trying to figure out how to solve recurrence relations using Mathematica (6). I have tried to search the web for information on how to use the recurrence relation solving package but I must be doing something wrong...
45. ### Solution by Iteration: Nonrecursive Formula for a_n = 2(n+1)^n

[SOLVED] Recurrence Relations Homework Statement I need to express this recursive statement as a nonrecursive formula, using the technique of itteration. a_n = (n+1)a_{n-1} a_0 = 2 The Attempt at a Solution a_n = (n+1)a_{n-1} a_n = (n+1)(n+1)a_{n-2} = (n+1)^{2}a_{n-2} a_n =...
46. ### Help with linear homogeneous recurrence relations

Homework Statement Here's my problem - Give the order of linear homogeneous recurrence relations with constant coefficients for: An = 2na(n-1) The Attempt at a Solution I have no idea on how to start this problem - Any help would be greatly appreciated.
47. ### [Discrete Math] Recurrence Relations

Question: "Find a recurrence relation and initial conditions for the sequence {a sub n} if a sub n is the number of bit strings of length n that contain three consecutive 0's." So here's what I have so far... n > 3 n = 4, 1000, 0001 n = 5, 10000, 00001, 00010, 01000, 10001 n = 6...
48. ### Solving a DE with a Series Index Shifts & Recurrence Relations

Ok I'm giving these another go. I found the following DE from a reduction of order problem and figured that it would be an alright question if I turned it into one requiring a series solution. However I'm stuck. I think it's just a matter of index shifts to get an appropriate recurrence relation...
49. ### Recurrence relations and sequences

Hi... 1. so can i say that a recurrence relation is a description of the operation(s) involved in a sequence...?... 2. is the formula for an arithmetic sequence, a recurrence relation...?... and is the formula for a geometric sequence, a recurrence relation...?...
50. ### 2. Order Linear Inhomogenous Recurrence Relations with Constant Coefficients

I need to show that the solution of a_n = c_1a_{n-1} + c_2a_{n-2} + f(n) (1) is of the form U_n = V_n + g(n) (2) where V_n is the solution of a 2. order linear homogenous recurrence relation with constant coefficients. Could I use the argument that if (2) is a solution...