What is Recurrence: Definition and 256 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
Recent contents Top users
  1. evinda

    MHB Can a recurrence relation predict property fluctuations in a gambling game?

    Hello!Could you help me at the exercie below? Consider a gamble,with the same possibility to win or to lose.If we win,we double our property,but if we lose we halve our property.Let's consider that we begin with an amount c.Which will be the mean value of our property,if we play n...
  2. Nono713

    MHB Non-recursive formula for the $n$th term of a linear homogeneous recurrence

    Just an easy one to start off with, find a non-recursive formula for the $n$th term of the following linear homogeneous recurrence: $$a_0 = 2, ~ ~ a_1 = -2, ~ ~ a_n = -2 a_{n - 1} + 2 a_{n - 2} ~ ~ \text{for} ~ n \geq 2$$ Hint:
  3. A

    MHB Condition for recurrence and transience of MC

    Consider the following model. X_{n+1} given X_n, X_{n-1},...,X_0 has a Poisson distribution with mean \lambda=a+bX_n where a>0,b\geq{0}. Show that X=(X_n)_{n\in\mathrm{N_0}} is an irreducible M.C & it is recurrent if 0\leq b <1. In addition, it is transient if b\geq 1. How do we approach this...
  4. Darth Frodo

    Recurrence Relation Problem

    Homework Statement a_{n} = a_{n-1} + n a_{0} = 0 The Attempt at a Solution h_{n} = h_{n-1} t^{2} - t = 0 t=0 t=1 h_{n} = B p_{n} = bn + c p_{n} = p_{n-1} + n bn + c = b(n-1) + n bn + c = (b+1)n -b I'm sure I've gone wrong somewhere, I just can't figure out where!
  5. MarkFL

    MHB Stephen's question at Yahoo Answers regarding an inhomogeneous linear recurrence

    Here is the question: Here is a link to the question: Find The Closed Form? - Yahoo! Answers I have posted a link there to this topic so the OP can find my response.
  6. A

    What is the recurrence relation for strictly increasing sequences from 1 to n?

    Homework Statement Find a recurrence relation for the number of stricly increasing sequences of positive integers that have 1 as their first term and n as their last term, where n is a positive integer. that is, sequences a1, a2, ..., ak, where a1 = 1, ak = n, and aj < aj+1 for j = 1, 2...
  7. MarkFL

    MHB SSome Help's question at Yahoo Answers regarding a linear recurrence equation

    Here is the question: Here is a link to the question: Discrete Math Help questions? - Yahoo! Answers I have posted a link there to this topic so the OP can find my response.
  8. M

    Linear recurrence = closed form?

    Hi I've got a recurrence relation: x_n = a*x_(n-1) + b; I think I'm going mad trying to figure out a closed form, eg. x(n) = ? the nth iteration Is there a trick or something I'm missing? Thanks
  9. A

    MHB Solve Recurrence Equation w/2 Base Cases Same Result

    This question is related to the question that I have asked here, although the equation is ever so slightly different: http://www.mathhelpboards.com/f15/solving-specific-variable-when-solving-recurrence-equation-3804/ I have a recurrence equation of the form $$ T(n) = 0, n = 0, n = 1\\ T(n) =...
  10. A

    MHB Solving for specific variable when solving a recurrence equation

    I have the following recurrence equation, where C is just some constant: $$ T(n) = 0, n = 1\\ T(n) = T(\frac{n-1}{2}) + 2C, n > 1 $$ Using a top-down approach to unrolling the equation to find the pattern, I get: $$ T(n) = T(\frac{n-k}{2^{k}}) + 2kC $$ Now I want to solve for k and associate...
  11. C

    Poincaré recurrence and maximum entropy

    Fluctuation theorem says that there will be fluctuations in microscopic scale that results local decreases in entropy even in isolated systems. According to the Poincaré recurrence theorem, after sufficiently long time, any finite system can turn into a state which is very close to its initial...
  12. MarkFL

    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.
  13. Fernando Revilla

    MHB Mark's question at Yahoo Answers (Linear recurrence relation)

    Here is the question Here is a link to the question: 2nd order homogeneous linear recurrence? - Yahoo! Answers I have posted a link there to this topic so the OP can find my response.
  14. MarkFL

    MHB I'm Confused's question on Yahoo Answers involving a recurrence relation

    I posted a link to this topic, so the OP could find my response. Here is a link to the original question: Recursive formula help on real world situations? - Yahoo! Answers Let $A(t)$ represent the amount, in mg, of antibiotic in Jonah's bloodstream at time $t$, measured in hours. With a...
  15. B

    Show that this sequence satisfies the recurrence relation

    Homework Statement Let d0, d1, d2,... be defined by the formula dn = 3n - 2n for all integers n ≥ 0. Show that this sequence satisfies the recurrence relation. dk = 5dk-1 - 6dk-2.Homework Equations The Attempt at a Solution I found that dk = 3k - 2k dk-1 = 3k-1 - 2k-1 dk-2 = 3k-2 - 2k-2...
  16. L

    Developing Recurrence Formula (Closed)

    Homework Statement Given binary string of length n. substrings of 1's should be even. (given 0 is a delimeter) eg) 10111 is broken down into 1 and 111 (all odd) so, for example string with H(n = 4) 0000 1100 0110 0011 1111 there are 5 of them. H(n = 3) 000 110 011 there are 3 of...
  17. C

    MHB Finding a Ratio for Linear Recurrence Sequences

    I have a linear recurrence sequence and am having a problem understanding what to do when the ratio does not seem to be the same between each of the terms, so Terms; 4, 1.4, 2.44, 2.024... (n = 1,2,3...) How do I find a the ratio of these terms, and if there is none, please advise how I...
  18. C

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

    Finding a recurrence Relation

    Find a simple closed formula for the ordinary generating function of the sequence given by {a_{n}]}n>=0 when a_{n} is given by a_{n} = 6 * 5^n - 5 * 3^n. My question is how do you find the recurrence relation a_{n} = 6 * 5^n - 5 * 3^n. I don't know were to start.
  20. D

    Recurrence Relation - limit of a sequence

    Hello, It is my understanding that if we have a sequence defined as follows:an+1=(ψ)an + (λ)Then if ψ≥1 or ψ≤-1, the sequence diverges. If -1<ψ<1, the sequence converges to: λ/(1-ψ)I was working problems in a book and one of the problems said that the following sequence converges...
  21. J

    Poincare Recurrence and the Klein-Gordon Equation

    There exists Green's Functions such that the solutions appear to be retro-causal. The Klein-Gordon equation allows for antiparticles to propagate backwards in time. Does this mean the future can influence the past and present? Then again The Poincare Recurrence Theorem states that over a...
  22. X

    Recurring Equations: Solving for T(n) with Mathematical Induction

    Homework Statement Solve the recurrence: T(n) = T(n/7) + T(4n/5) + n for n > 35 with base case T(n) = constant for n ≤ 35.Homework Equations The Attempt at a Solution Is this mathematical induction? No idea how to do this one.
  23. A

    MHB Proving solution to recurrence equation using induction

    Hello, I have the following recurrence equation $$T(n)=aT(n-1)+bn$$ Using substitution, I have solved it to the following form $$T(n)=a^{n-1}+b \sum_{i=2}^{n}ia^{n-i}$$ Now I am trying to prove my solution is correct using induction, but I'm a bit lost. Any advice on how to conduct this...
  24. C

    Find a recurrence word problem.

    find a recurrence,,, word problem. Homework Statement A rectangular board 2cm wide and ncm long is to be covered with smaller tiles of size 2cmx2cm and 1cmx2cm. There is an unlimited supply of both types of tile. For each n=1,2,... let an be the number of ways that a board of length n...
  25. A

    Recurrence relation for the Legendre functions

    My book wants to find solutions to Legendre's equation: (1-x2)y'' - 2xy' 0 l(l+1)y = 0 (1) By assuming a solution of the form: y = Ʃanxn , the sum going from 0->∞ (2) Now by plugging (2) into (1) one finds: Ʃ[n(n-1)anxn-2-n(n-1)anxn - 2nanxn + l(l+1)anxn = 0...
  26. C

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

    Proving Recurrence Relation by Induction

    x_{xn-1}= 5_{xn-1} - 6_{xn-2};for \ n≥2 \\ x_{1}=1 \\ x_{0}=0 prove by induction that: \begin{bmatrix} x_{n}\\ x_{n-1} \end{bmatrix} = \begin{bmatrix} 5 &-6 \\ 1 & 0 \end{bmatrix}^{n-1}\begin{bmatrix} 1\\0 \end{bmatrix}
  28. Q

    Integrating Recurrence Formula for x_n = n^{-1} - 7x_{n-1}

    Hi guys. I'm having a bit of trouble with what I thought was a simple math question. Homework Statement x_{n} = \int_0^1 \frac{t^n}{t+7}dt Show that x_0=ln(8/7) and x_n = n^{-1} - 7x_{n-1} 2. The attempt at a solution Showing x0 = ln(8/7) is a vanilla textbook log question. I'm having...
  29. S

    Solve the recurrence: t(n) = t(n/2) + n + 2 (Solution included).

    Homework Statement The problem along with its solution is attached as Problem.jpg. Homework Equations Recurrence relation. The Attempt at a Solution I am confused as to what the solution is stating. I get up to and including (3) but I am stuck at (4). After (4), I get that k = log2(n)...
  30. P

    Discrete: Recurrence relation for sum of integer using only 2's and 3's.

    Homework Statement Find a recurrence relation for Tn, the number of ways to write an integer n as the sum of terms, each of which is 2 or 3, and the order matters. [So 2+3 and 3+2 are different sums for 5.]Homework Equations (if I had one, this would be easier) The Attempt at a Solution So I...
  31. D

    Offset between non-homogeneous and homogeneous recurrence sequences

    I have a question; help is welcome. Let sn be a linear, non-homogeneous recurrence sequence, and let hn be a corresponding homogeneous sequence (with initial values to be determined). As it turns out, the offset between the two (sn - hn) is given by the steady state value of sn, if the...
  32. C

    Poincaré recurrence applicability condition?

    This is how Wikipedia summarizes the Poincaré Recurrence Theorem: This is wrong, isn't it? Don't you need to ensure the phase space is bounded, and isn't conservation of energy an insufficient justification for that? Like, imagine throwing two baseballs away from each other into infinite...
  33. A

    Convergence of a recurrence equation: x(k+1) = 0.5x(k) + u(k)

    Homework Statement Hello. I am trying to prove a result that I have been making use of, but never really proved. Consider the recurrence equation x(k+1) = 0.5 x(k) + u(k), where u(k) is a bounded sequence. For this problem, assume that u(k) goes to zero. I want to prove that x(k) goes to...
  34. A

    Combinatorial Proof of a Recurrence Relation

    So my professor gave us this recurrence relation to prove combinatorially for extra credit, but I was unable to figure it out. h(n) = 5h(n-1) - 6h(n-2) + 1 This was my solution, but I couldn't figure out how to factor in the +1: Let hn be the number of ways to arrange 0,1,2,3,4 on a 1xn...
  35. L

    Combinatorics - Recurrence Relation Question

    Homework Statement For n ≥ 1, let g(n) be the number of ways to write n as the sum of the integers in a sequence of any length, where each integer in the sequence is at least 2. For n≥3, show that g(n) = g(n-1) + g(n-2).2. The attempt at a solution I've gone through values of g(n) for...
  36. Z

    How to get the closed form of this recurrence?

    Homework Statement Hello, This expression was derived from a polygon word problem and I need to find a closed form for it with repeated substitution (I think). T(k, n) = T(k, n-1) + (k-2)(n-1) + 1 Homework Equations The Attempt at a Solution Get a pattern like: = T(k, n-2) + (k - 2)(2n -...
  37. S

    Find a recurrence formula for the power series solution around t = 0

    Homework Statement Find a recurrence formula for the power series solution around t = 0 for the differential equation: d^2 y/dt^2 + (t - 1) dy/dt + (2t - 3)y = 0 Homework Equations y = Σn=0 to inf (a_n * t^n) and formula to differentiate polynomials. The Attempt at a Solution I...
  38. I

    Finding the limit of a recurrence equation.

    I have been working on a problem proposed in a math journal, and there is only one thing I need to figure out. Here it is: Let (a_n) be a sequence defined by a_1 = a and a_{n+1} = 2^n-\sqrt{2^n(2^n-a_n)} for all 0 \leq a \leq 2 and n \geq 1. Find \lim_{n \rightarrow \infty} 2^n a_n in terms...
  39. J

    MHB Confusion with variables when solving a recurrence equation

    If I have a recurrence equation of the following form: $$T(n) = T(km) = a, m = 1$$ $$T(n) = T(km) = T(k) + T(k(m-1)) + cn, m > 1$$ Where a is simply a constant, and k is an integer constant > 0. Now I begin substituting to find the pattern: $$T(k) = a$$ $$T(2k) = a + [a] + c2k$$ $$T(2k) = 2a...
  40. D

    MHB How can I solve a recurrence equation of the form T(n) = aT(n-1) + bn?

    I have a recurrence equation of the form T(n) = aT(n - 1) + bn where T(1) = 1. In trying to solve this equation, I have tried a top-down and bottom-up approach of "unrolling the equation" but found that I am still having trouble and am unable to solve. Any advice would be appreciated.
  41. C

    MHB What is the error in this linear recurrence sequence?

    I have a linear recurrence sequence, 3, -1.5, 0.75, -375 x = a a = 3 x2, = -1.5, x3, = 0.75, x4 = -375... x2 = rx1+d x3 = rx2+d -1.5 = 3r + d 0.75 = -1.5 + d -1.5 - 0.75 = (3r + d) - (-1.5 + d) r = - 0.5 Sub in equation (2) d = -1.5 - 3r = -1.5 - 3(-0.5) d = 0 x4 = -0.5 x 0.75 + 0 =...
  42. S

    Please show me how to simplify this recurrence relation

    I'm doing a much larger problem and I am stuck going from: T(n) = 14 + T (n − 2) + 10(n + (n − 1)) to T(n) = (n − 1)7 + T(1) + 10(Σi=2 to n of i) and I would very much appreciate it if someone could show me the detailed steps. (I've been told something about expanding the recursive...
  43. C

    Need help in solving a recurrence relation

    Hey! I was trying to find the expected time an algorithm takes to solve a certain problem, and I ended up in a very nasty recurrence relation of this form: a_{k,k} =...
  44. P

    Solving a Linear Homogeneous Recurrence Relation

    1. Solve the following recurrence relation. an - 5an-1 + 6an-2 = 0, n ≥ 2, a0 = 1, a1 = 3 3. My attempt I changed it to 0 = tn - 5tn-1 + 6tn-2 Don't know where to go from there.
  45. K

    Proving a recurrence relation by induction

    Solved!
  46. M

    What is the limit of the recurrence relation for g_n?

    Hi all Suppose that , a_{n+1}=a_n^2-2 and g_n=\frac{a_1a_2...a_n}{a_{n+1}}. Evaluate \lim_{n\rightarrow \infty } g_n. I have seen some information in this link. Besides, the sequence gn seems as a good rational approximation for \sqrt5. I know that the answer is 1, But I can't find any...
  47. K

    Solving Recurrence Equations for Algorithm Analysis

    Homework Statement I need to solve a recurrence equation in order to perform algorithm analysis. I got the recurrence from the algorithm I developed. It's been years since I did my undergrad degree and my maths is rusty. Homework Equations T(n)= 1+ \sum_{i=1}^n2(n-i+T(i)) The Attempt...
  48. N

    Second Order Homogeneous Recurrence Relation

    Hello! I was reading the proof (I think it constitutes a proof) for second order homogeneous recursive relations from the book Discrete Mathematics with Applications by S. Epp, and it seems, to me at least, to be excessive; which suggests that I don’t understand the proof. It goes...
  49. Avatrin

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

    How does the n drop down in this recurrence relation problem?

    [PLAIN]http://img442.imageshack.us/img442/4514/ballsp.jpg The base case is 2^{K} = n (which turns into log_{2}n = k So I have a question on this recurrence relation problem. (I'm trying to get to make the top equation look like the bottom equation.) I know that the summation ends up becoming...
Back
Top