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

    Solving a Recurrence Relation with Multiple Roots

    Homework Statement Solve the recurrence relation an = 5an−1 − 3an−2 − 9an−3 for n ≥ 3 with initial values a0 = 0, a1 = 11, and a2 = 34. Homework Equations its given lol The Attempt at a Solution I found that the characteristic equation for this rr is x3 - 5x2 + 3x + 9 and found...
  2. P

    Recurrence relation in matrix multiplication

    Homework Statement T(n)=b n<=2 8T(n/2)+e(n^(2)) n>2 Homework Equations The Attempt at a Solution O((n^log)2^(7))
  3. D

    Recurrence relation of tangent

    Is it possible to find a recurrence relation of tan(nx) where n is a positive integer and x is a real variable? My friend said that it is possible. I don't see how to do it. Does anyone have a way to do it?
  4. N

    Solving Recurrence Relation: a_n=\frac{a_{n-5}}{n(n-1)}

    Homework Statement Got this recurrence relation when trying to solve for a series solution to a differential equation: a_n=\frac{a_{n-5}}{n(n-1)} , a_0,a_1=constant , a_2,a_3,a_4=0 Homework Equations The Attempt at a Solution My attempt at a solution involved first writing out all...
  5. N

    How to Prove Recurrence Relations by Induction?

    Prove the following recurrence by induction T(n) = 2T(n/2) + n lg n = Θ ( n lg^2 n ), T(1) = 1 This to me looks scary and I was wondering if anybody had a heads up on how to solve for this
  6. B

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

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

    Probability with Recurrence Relation

    Homework Statement Box A contains three white balls and one red ball while box B contains four white balls. One ball is randomly drawn from each box and the two balls are then randomly put back into the boxes so that each box still contains four balls. This process is performed n times. Let...
  9. A

    2-index recurrence relations

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

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

    Quadratic Recurrence and the Mandelbrot Set

    I am currently studying the Mandelbrot set, and have a question about one of the statements on http://mathworld.wolfram.com/QuadraticMap.html" . It says the recurrence for the Mandelbrot set "is not in general solvable in closed form." What does this mean?
  12. T

    Sequences and series help / recurrence relation

    Homework Statement A sequence of terms U_{k} is defined by K \geq by the recurrence relation U_{k+2} = U_{k+1} - pU_{k} where P is a constant Given that U_{1} =2 and U_{2} = 4 a) find an expression in terms of p for U_{3} b) hence find an expression in terms of p for...
  13. G

    Finding the recurrence from an algorithm

    I need some help. I am having a hard time find the recurrence when given an algorithm in c++. The algorithm is a Max search: Its where the program goes through the array from first element to last, or last to first (depends on how you program it) to look for the largest value. In this case it...
  14. G

    Binary Search Comparison Recurrence Relation: Solve and Prove Solution"

    Homework Statement Solve and prove your solution for the following recurrence relation for the number of comparisons in Binary Search: C(21 - 1)=1 C(2i - 1) = 2 + C(2(i+1) - 1) The Attempt at a Solution The setup for this would be: C(n)={ 1, n=1 and 2 + C(2(i+1) - 1), otherwise From this...
  15. I

    Find general solution from recurrence relation, done most of work

    Homework Statement 2xy" + y' + xy =0 xo=0 find the indicial equation, recurrence relation and series solution. Homework Equations The Attempt at a Solution I've done most of the work but i don't know how to use a recurrence relation to obtain a y1 and y2 series solution...
  16. T

    Find a recurrence relation

    Homework Statement Find the recurrence relation to 1,1,2,5,12,47,...The Attempt at a Solution Made all sorts of attempts. I'm not experienced with these things. Was there a site that works these things out for you?
  17. T

    Find a Recurrence Relation: Step-by-Step Guide

    How do you find a recurrence relation from a given problem?
  18. E

    Non Homogeneous Recurrence Relation

    1. solve the following recurrence relation for an 2. (n+2)an+1= 2(n+1)an+2^{n}, n>=0, a0=1 I shifted the index, multiplied through by the 2^{n} term and then subtracted the resulting equation from the original equation to get rid of the 2^{n} term... 3. I have gotten to this point...
  19. W

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

    Solving Recurrence Formula Homework w/ Integration by Parts

    Homework Statement I(subscript n)=integral (from pi/2 to 0) [sin(x)]^n * [cos(x)]^2. Show that I (subscript n) = [(n-1)/(n+2)] I(subscript (n-2)) I think ur meant to use integration by parts on it somewhere but i don't know wat to use it on.
  21. Y

    Substitution for impulse in recurrence equation

    Hi, I was wondering what substitution to try when finding a particular solution for a recurrence equation with a linear combination of impulses on the right side of the equation. I think an example will clarify this. Given the recurrence equation y[k+2]-4y[k]=\delta [k] + 2\delta [k+1]...
  22. Y

    Solving a Recurrence Equation: What Did I Do Wrong?

    Hi, I'm trying to solve this recurrence equation. Homework Statement Solve y[k+2]+y[k]=sin(k). The answer is already given, it's y[k]=c_1sin(\frac{\pi}{2}k) + c_2cos(\frac{\pi}{2}k) + \frac{sin(k)+sin(k-2)}{2(1+cos(2))} Homework Equations The Attempt at a Solution First I solve...
  23. G

    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 =...
  24. A

    Fibonacci Cubed Recurrence Relation

    Homework Statement Find and prove the recurrence relation for the Fibonacci cubed sequence. Homework Equations By observation (blankly staring at the sequence for an hour) I've decided that the recurrence relation is G_{n} = 3G_{n-1} + 6G_{n-2} - 3G_{n-3} - G_{n-4} (where G is Fibonacci...
  25. F

    Can g(x) Represent Sum(a(i)^2*x^i) {for i=1:Inf} in Any Functional Form?

    Homework Statement Solve the following for a_n in terms of x: a_{n+1} = \sqrt{x + a_n} Homework Equations The Attempt at a Solution Besides getting rid of the radical, I have no idea how to solve this.
  26. A

    How to Prove Fibonacci Squared Recurrence Relation

    Homework Statement We were asked in a class discussion if we could try to figure out the recurrence relation of the Fibonacci squared sequence. I correctly figured that the equation was F^{2}_{n}=2F^{2}_{n-1} + 2F^{2}_{n-2} - F^{2}_{n-3} with F^{2}_{1} = 0 and F^{2}_{2} = 1 and F^{2}_{3}...
  27. F

    Linear second-order recurrence sequences

    Hello, I hope I have posted this in the correct place, if not, sorry. Okay, I have just started working through the material, but I am having some problems working out one of the examples, which is given below: Un+2 = 12Un+1 - 20Un (n = 0,1,2...) We are given U0 = 1, U1 = 2 and...
  28. K

    Solve Recurrence Relation: a_{n+2}+3a_{n+1}+2a_n=3

    [SOLVED] Recurrence Relation Homework Statement Solve the recurrence relation a_{n+2}+3a_{n+1}+2a_n=3 Homework Equations add the homogeneous solution to the particular solution The Attempt at a Solution Characteristic: s^2+3s+2=0 \Rightarrow x=-2,-1 Homogeneous...
  29. E

    Unraveling 1999 Putnam A3: Understanding the Recurrence Relation

    Homework Statement In the first solution to 1999 A3 at the this website: http://www.unl.edu/amc/a-activities/a7-problems/putnam/-pdf/1999s.pdf You do not need to read the problem. I do not see hot they go the recurrence relation in the first sentence. Specifically I do not follow reason why...
  30. D

    Another on recurrence sequences

    How would you go on proving the following conjecture? Given S_0 = 0, \quad S_1 = 1, \quad S_n = a S_{n-1} + b S_{n-2} Prove that { S_n }^2 - S_{n-1} S_{n+1} = (-b)^{n-1} \quad (n = 1, 2, 3, ...)
  31. D

    Solving Recurrence Relation: a_n = \sqrt{2+a_{n-1}}, a_0 = \sqrt{3}

    Hey, I came across this recurrence relation and was wondering if there was a closed-form solution for it. a_n = \sqrt{2 + a_{n-1}}, a_0 = \sqrt{3} Assuming n \in \mathbb{N}, of course. I know that's it's possible to solve homogenous and inhomogenous recurrence relations using certain...
  32. O

    Can infinite recurrence be mathematically proven?

    Hi, I would like to tell the room I’m a novice. I know very little math, mostly Algebra. So asking these questions in themselves are over my head. But I have a question that I wonder can be shown mathematically. I want to know if there can be an infinite recurrence. (For all I know it could...
  33. quasar987

    Fundamental group of RP^n by recurrence?

    Fundamental group of RP^n by recurrence!? Homework Statement That's it. Find the fundamental group of RP^n by recurrence. The Attempt at a Solution It's just obvious to me that it's Z/2 no matter n but what is this recurrence argument that I'm supposed to use?
  34. H

    Solving Recurrence Relation w/ Initial Conditions for n-digit Sequences

    hello any one can help me with this question thanx (a) Find a recurrence relation for the number of n-digit sequences over the alphabet {0, 1, 2, 3, 4} with at least one 1 and the first 1 occurring before the first 0 (possibly no 0’s). (b) What are the initial conditions? (c)...
  35. H

    Solve the recurrence relation a_n = a_n-1 + 20a_n-2

    hello please check my answer and let me know if there are any errors and if there are better ways to solve ... Solve the recurrence relation an = an−1 + 20an−2 with a0 = −1 and a1 = 13. Step – I : Find Characteristic equation and solve for its roots: an = an−1 +...
  36. C

    Big-O and recurrence equations.

    Can anyone point me to resources showing me how to prove recurance equations like: I(n) \le c if n = 0 d+I(n-1) if n >= 1 i.e. I(n) \le c + dn Also for proving things like: 30000n^2 + n \log n is O(n^3) using the basic definition of big-O notation (f(n) \le k \cdot g(n) for some...
  37. B

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

    Solving a Tower Building Recurrence Relationship

    Hello everyone. I"m having troubles figuring out this recurrance relationship. The problem is the following: A set of bloks contains blocks of heights 1, 2, and 4 inches. Imaigne constructing towers by piling blocks of dferent heights directly on top of one another. (A tower of height 6...
  39. N

    Proof of Poincare Recurrence Theorem

    Does anyone know of an accessible reference that sketches a proof of Poincare's recurrence theorem? (This is not a homework question.) I'm coming up short in my searches -- either the proof is too sketchy, or it is inaccessible to me (little background in maths, but enough to talk about...
  40. S

    [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...
  41. M

    Find the solution to the following lhcc recurrence, confused

    ello ello! I ran into this problem and i went in circles trying to figure it out. Anyone have any suggestions? Here is what i have: Find the solution to the following lhcc recurrence: http://cwcsrv11.cwc.psu.edu/webwork2_files/tmp/equations/3c/1e4624e0fc726276872050e3ffe28d1.png with...
  42. N

    Poincare Recurrence and the Infinite N Limit

    (One version of) Poincare's Recurrence Theorem states that for any conservative system whose possible states S form a compact set in phase space, that system will "almost always" return arbitrarily close to its initial state, provided we wait long enough. ('Almost always' means 'all but a set...
  43. B

    Summation Equation, Trying to solve this recurrence forumla.

    Hello. I've searched around a bit for a math forum where I could get help with this and this seems like the one I found where I could get some help with this. I was posed the following problem. Now I must admit it is over my head (as is most of the math on this forum) I was hoping that...
  44. H

    Solving Recurrence Relation: t(m,n) Formula

    How do we actually solve the Recurrence relation...is there any procedure... Suppose i want to solve: t(m,n) = n.t(m-1,n) + t(m-1,n-1) where t(1,*) = t(*,1) = 1. How to do it?
  45. E

    Divide and conquer recurrence relation

    I am at a loss on how to get the correct answer to this question. How many comparisons are needed for a binary search in a set of 64 elements? I know the formula f(n) = f(n/2) + 2 I know the correct answer which is 14. No matter what I do I cannot come up with this answer...
  46. S

    Solving Recurrence Equation: Understanding the Roots & Coefficients

    Here is the famous thing, sum of k from 1 to n is n*(n+1)/2. I'm trying to show this by recurrence equation. Then an is the sum, I have this equation: an=a(n-1)+n. It's not a*(n-1), just like this kind equations n indicates the number of the term. The charcteristic equation is r^2-r-n=0...
  47. B

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

    How to set up probability of numeric recurrence in lottery

    Hi, It has been a long time, and I do not remember how to set up a probability calculation with the following variables - take a lottery that draws 12 numbers, values 0-9 only, from a hopper that replaces the number after it is drawn, i.e. probability of each number appearing remains...
  49. kakarukeys

    Question on Poincare Recurrence Theorem

    Poincare Recurrence Theorem states that: "If a flow preserves volume and has only bounded orbits then for each open set there exist orbits that intersect the set infinitely often." But it does not imply (does it?) that "In hamiltonian system with bounded phase space, all trajectories will...
  50. P

    Solving Linear Recurrence: ax_k+1 + bx_k + c

    Consider the recurrence x_k+2 = ax_k+1 + bx_k + c where c may not be zero. If a + b is not equal to 1 show that p can be found such that, if we set y_k = x_k + p, then y_k+2 = ay_k+1 + by_k. [Hence, the sequence x_k can be found provided y_k can be found] First of all, sorry about the...
Back
Top