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

    Recurrence relation oddball one

    Homework Statement T(n) = 2T(n-1) T(1)=1 The Attempt at a Solution I am trying to show the iterations. T(n) = 2T(n-1) T(n) = 22T(n-2) T(n) = 222T(n-3) Is this the right track? Where the result would be 22222...1eventually? The problem just feels awkward D: If my answer is right is there...
  2. N

    Prove that recurrence relation is odd

    Homework Statement Hello! I just want to be sure if I did solve the task correctly. The task is: Prove that bn is odd for integers n>=1 b1=1 b2=3 bk=bk-2+2bk-1 for k>=3 Homework Equations The Attempt at a Solution Induction basis: b1=1 true 1 is odd b2=3 true 2...
  3. P

    Solve 8c Stamp Problem with Recurrence Relation

    Use a recurrence relation to find the number of ways that stamps that have a value of 1 cent , 2 cents and a 3 cents can add up to eight cents. How exactly do you go about solving a problem like this without writing a program to find all the possibilities? The answer given is 81, but I...
  4. A

    What is the limit of the sequence gn and its relation to \sqrt5?

    Hi all Suppose that a_1=\sqrt5, 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 http://oeis.org/search?q=3%2C7%2C47%2C2207&sort=&language=english&go=Search". Besides, the sequence gn seems as a good rational...
  5. S

    Solving this type of recurrence equation

    Hi, The problem is to solve (1-g_{i+1})P_{i+1}-P_{i}+g_{i-1}P_{i-1}=0 for P_{i} with boundary condition P_{i}=P_{i+L}, g_{i}=g_{i+L} Can anyone provide any guide of solving this type of recurence equation? Thank you!
  6. A

    Recurrence relation for an integral equation

    Hi guys, would appreciate any help with this problem. It's from a graduate school entrance examination which I am practicing. problem statement When n is a natural number, the indefinite integral I_n is defined as I_n=\int\frac{1}{(x^2+a^2)^n}dx Here, a is a constant real number, and...
  7. O

    Q. Solving a Quadratic Recurrence Relation: Finding Coefficients a, b, and c

    Homework Statement Dang it! More recurrence relation problems, but this time it’s due to a quadratic equation. Q. In the sequence u1, u2, u3,…,un, u1 = 0, u2 = 3, u3 = 12 and un = a + bn + cn2 Find the values of a, b and c. Homework Equations Provided at back of book…...
  8. O

    SAT/ GCSE-Level Recurrence Relation Problem

    Homework Statement Hi! This is my first time on the site. I look forward to working with everyone…but hopefully not too much, assuming I‘m learning things correctly. :P My question pertains to Recurrence Relations, so here it goes… Foreword: The textbook I’m using actually supplies...
  9. L

    How do you solve a nonlinear recurrence relation?

    While solving a problem involving equilibrium positions of charges on a line, I came up with a recurrence relation which is nonlinear, and moreover implicitly defined. Here it is: x_{0}=0 and \sum^{n-1}_{i=0} \frac{1}{(x_{n}-x_{i})^{2}} = 1. I should also mention that 0 \leq x_{n}< x_{n+1} for...
  10. P

    Linear recurrence with polynomial coefficients

    Hi all, I came across a linear recurrence with polynomial coefficients and realized that I don't have a clue as to how to solve it. The usual methods like generating functions or guessing seem not to work in that case. Here is the equation: i (i - 1) (i - 2) b[i] = 1/3 (i + 1) i (1 -...
  11. S

    Proof of recurrence relation of partitions

    Homework Statement Let T_{n} denote the number of different partitions of {1,2,...,n}. Thus, T_{1} = 1 (the only partition being {1}) and T_{2} = 2 (the only partitions being {1,2} and {1},{2}). show that T_{n+1} = 1 + \sum^{n}_{k=1} (^{n}_{k}) T_{k}. Homework Equations Let S be a given...
  12. Mentallic

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

    Recurrence Relation for Iterative Solution of Ax=b

    _nx represents the nth iteration. Homework Statement Show that {_{n+2}}x = _nx + M^{-1}(b-A{_nx}) Homework Equations {_{n+1}}x = _nx + M_1^{-1}(b-A{_nx}) {_{n+2}}x = {_{n+1}}x + M_2^{-1}(b-A{_{n+1}x}) M = M_1(M_1+M_2-A)^{-1}M_2 The Attempt at a Solution I tried was...
  14. B

    Recurrence formula in Pell's equation

    Hello, I am trying to solve a Pell's equation X2 + 2Y2 =1 I understand that the (3,2) is a fundamental solution to the equation. However, I am having difficulty to obtain the recurrence formula in order to generate further solutions. Can anybody help?
  15. J

    Sequences that satisfay the same recurrence relation

    Homework Statement Let a0, a1, a2..., be defined by the formula an = 3n + 1, for all integers n >= 0. Show that this sequence satisfies the recurrence relation ak = ak-1 + 3, for all integers k >=1. Homework Equations for all integers n >= 0, an = 3n + 1 for all integers k...
  16. S

    Recurrence Relation for Alpha beta filter

    The alpha beta filter equation is given by this Xni = AXn + BXn-1 Xn-1 is subscript i want to figure the solution to this recurrence relation, but is it a recurrence relation? i am wondering weather alpha beta filters grow faster than exponential smoothing filters.- i said it is a 1st order...
  17. L

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

    Cannot find the pattern in recurrence relation

    Homework Statement I am doing a power series solution for: (x^2-1)y" + 8xy' + 12y = 0 I rewrote it in terms of power series and transformed everything into one series and finally ended up with the following recurrence relation: an+2= ((n+3)(n+4)an)/((n+2)(n+1)) I plugged in values for n...
  19. J

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

    Hermite Polynomial Recurrence Question

    Homework Statement I need to find an expression for: y^{2}H(y) I know how to find: yH(y) with: yH(y)=\frac{1}{2}H_{n+1}(y)+nH_{n-1}(y) I looked through the miscellaneous relations but nothing stuck out to me. Can someone give me some guidance on how to go about finding a relation...
  21. M

    Derive Hermite Polynomial Generating Function from Recurrence Relation

    I am not sure how to format in LaTeX; I apologize for that. The Hermite polynomials Hn(x) (physicist's version) satisfy the recurrence relation, H_{n+1}(x) - 2xHn(x) + 2nH_{n-1}(x) = 0; H0(x) = 1 and H1(x) = 2x: Use this to derive the generating function for the Hermite polynomials...
  22. S

    Solve Recurrence Relation with Lambert W-function

    Dear forum people, for a nonlinear software I am writing I am having a hard time to transform a recurrence relation to an explicit function. Maybe someone can help me along the right lines... The recurrence relation is of the form (an exponential type function) y[n+1] = y[n] + k *...
  23. jegues

    Power Series Recurrence Relation Problem

    Homework Statement See figure attached, we are asked to use power series to solve the differential equation. Homework Equations The Attempt at a Solution I'm confused as to how to deal with the -1 in the indices of one of my summations. I could add the term on the outside and...
  24. BWV

    Help me understand Entropy & P's recurrence theorem

    reading the very interesting discussion on the long thread on the 2nd law, had a couple of much more basic questions regarding entropy & the Poincaré Recurrence Theorem A) is the reduction of entropy implied by the theorem a real, unresolved paradox in physics? B) if you take a...
  25. D

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

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

    2D variable coefficient recurrence relation

    Consider a 2D variable coefficient linear recurrence relation. An example might be: b_{n,j+1} (j+1)(2n-1)(2n-2) = (2n-2+j)(2n-1+j)b_{n-1,j} which has the solution b_{n,j} = \frac{(2n-1+j)!}{(2n-1)!j!} Is there any algorithm that can be used to derive this result? I have a recurrence...
  28. D

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

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

    Which recurrence relation is greater?

    Homework Statement An+2=6An+1+6An A1=A2=1 Bn+2=5Bn+1+9Bn B1=B2=10100 a) is it true that Bn>An for every integer n > 0? b) is it true that Bn>An for infinetly many integers n>0? The Attempt at a Solution It just seems like these are increasing functions since they both start with...
  31. S

    Find a recurrence relation from a sequence of integers

    If you are given a sequence of integers such as: An=xn+yn where x and y are integers. and n=0,1,2,3... how would one find the recurrence relation? I tried writing An+1 in terms of An but it doesn't come out neatly because it doesn't translate so well. And there are terms raised to the n+1...
  32. S

    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!
  33. S

    Solve Recurrence Relation: A0,A1,A2 Given

    Homework Statement An=3An-2-2An-3 When A0=3 A1=1 A2=8 I tried to solve it normally like a normal recurrence relation however since it is not A sub n-1, it turns into a polynomial where the variable is raised to the third power which I couldn't factor and the whole thing turned into a mess.
  34. G

    Derangement Recurrence Relation Proof Doesn't Seem To Make Sense

    So I was reading up about the derangement recurrence relation proven in a combinatorical way. The proof I was looking at is at this webpage. The combinatorical proof is at the bottom of the page below the algebraic proofs. [PLAIN]"ttp://planetmath.org/?op=getobj&from=objects&id=11991"[/URL]...
  35. T

    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"...
  36. FeDeX_LaTeX

    Solving Non-Linear Recurrence Relation?

    Hello; I do not have any experience in solving non-linear recurrence relations, so I was just wondering how one solves them. For example, consider the sequence: 1, 2, 6, 15, 31, 56 In general, F_{n+1} = F_{n} + n^{2} Do I still substitute F_{n} = k^{n}? Thanks.
  37. J

    Find a recurrence relation for this problem

    Homework Statement Suppose that a mathematical expression can only be formed by the following symbols: 0, 1, 2, …, 9, ×, +, /. Some examples are “0 + 9”; “2 + 2 × 8”; “1 / 5 + 6”. Let an be the the number of such mathematical expression of length n (e.g. “0 + 9” is considered of length 3)...
  38. J

    Question about logic and recurrence relation

    Homework Statement find a logical expression using only ∧ and ¬ operators which is logically equivalent to (p ∨ q) The Attempt at a Solution losing direction what should I first consider? There is another question about recurrent relation. Suppose that a mathematical expression can...
  39. Char. Limit

    Proving Recurrence Relation for f(x)

    Homework Statement Let's say I had this recurrence relation: log\left(f\left(x+2\right)\right) = log\left(f\left(x+1\right)\right) + log\left(f\left(x\right)\right) How do I prove, then, that... f\left(x\right) = e^{c_1 L_x + c_2 F_x} ? Homework Equations There probably are...
  40. S

    Any suggestions on how to improve the solution to this recurrence relation?

    [PLAIN]http://dl.dropbox.com/u/471735/Recurrence.png
  41. H

    How to solve recurrence relation with one real root and two complex roots ?

    How to solve recurrence relation with one real root and two complex roots ? The Example is ; Solve the recurrence relation a n-1 + a n-3 = 0 where n ≥ 3 and a 1 = 1 a 2 = 1 a 3 = 2 a n = nth order a n-1 = (n-1)th order. a n-3 = (n-3)th order. I've started the solving ; a n = r^n so...
  42. S

    Can Recurrence Relations with Complex Inequalities Be Simplified?

    Any suggestions on how to approach solving: \Psi(m,n) \leq \Psi\left(\left \lfloor\frac{m}{2}\right\rfloor,n_1\right) + \Psi\left(\left \lceil\frac{m}{2}\right\rceil,n_2\right) + 16n^*+11m \lceil\text{log }m\rceil where n = n_1 + n_2 + n^*
  43. T

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

    Solving Recurrence Relation Homework

    Homework Statement The sequence f_n is defined by f_0=1, f_1=2 and f_n=-2f_{n-1}+15f_{n-2} when n \geq 2. Let F(x)= \sum_{n \geq 2}f_nx^n be the generating function for the sequence f_0,f_1,...,f_n,... Find polynomials P(x) and Q(x) such that F(x)=\frac{P(x)}{Q(x)} The Attempt at a...
  45. P

    Recurrence Relation to Non-recursive Formula

    Homework Statement The sequence f_n is defined by f_0=f_1=2 and f_n = (\frac{f_{n-1}+2f_{n-2}}{6}), when n\geq2. Find a non-recursive formula for f_n The Attempt at a Solution Well I have solved for the closed formula of the generating function which I will call g(x) so...
  46. Z

    Time Complexity Formula for Solving Recurrence Systems

    Homework Statement Solve the recurrence system below and dtermine a formula for the time complexity function T(n). T(0) = 4. T(n) = 5 + T(n - 1) (n > 0) The Attempt at a Solution T(3) = 5 + T(2). T(2) = 5 + T(1). T(1) = 5 + T(0). T(3) + T(2) + T(1) = 3 * 5 + T(2) + T(1) + T(0)...
  47. J

    How to solve recurrence relation ?

    How to solve recurrence relation ? The Example is ; Solve the recurrence relation a n + 2a n-1 + 2a n-2 = 0 where n ≥ 2 and a 0 = 1 a 1 = 3 a n = nth order a n-1 = (n-1)th order. a n-2 = (n-2)th order. I've started the solving ; a n = r^n so the equation will be ; r^n + 2r^(n-1)...
  48. I

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

    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)...
  50. B

    Recurrence relation problems

    14. Suppose there are n=2^k teams in an elimination tournament, where there are n/2 games in the first round, with the n/2=2^(k-1) winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament. So the recurrence relation would be...
Back
Top