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
Recent contents Top users
  1. dim_d00m

    A Recurrence relations for series solution of differential equation

    I am currently looking at section IIA of the following paper: https://arxiv.org/pdf/gr-qc/0511111.pdf. Eq. (2.5) proposes an ansatz to solve the spheroidal wave equation (2.1). This equation is $$ \dfrac{d}{dx} \left((1-x^2) \dfrac{d}{dx}S_{lm} \right) + \left(c^2x^2 + A_{lm} -...
  2. F

    A Problem calculating arbitrary Polynomial Chaos polynomials using SAMBA

    Hello everyone. I have recently read the following article (which title is SAMBA: Sparse Approximation of Moment-Based Arbitrary Polynomial Chaos) since I have some data in the form of a histogram without knowing the probability distribution function of said data. I have been able to calculate...
  3. J

    Legendre polynomial - recurrence relations

    Note: $P_n (x)$ is legendre polynomial $$P_{n+1}(x) = (2n+1)P_n(x) + P'_{n-1}(x) $$ $$\implies P_{n+1}(x) = (2n+1)P_n(x) + \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} (2(n-1-2k)+1)P_{n-1-2k}(x))$$ How can I continue to use induction to prove this? Help appreciated.
  4. Eclair_de_XII

    How many ways are there to to climb n steps (recurrence relations)?

    (a) Okay, so if Tom climbs the first step, then he has ##n-1## steps to climb. So the number of ways to climb ##n## steps given he has initially climbed one, is ##s_n=s_{n-1}##. (b) Similarly, ##s_n=s_{n-2}##.
  5. V

    MHB Limits of Recurrence Relations with $0<b<a$

    Let $0<b<a$ and $(x_{n})_{n\in \mathbb{N}}$ with $x_{0}=1, \ x_{1}=a+b$ $$x_{n+2}=(a+b)\cdot x_{n+1}-ab\cdot x_{n}$$ a) If $0<b<a$ and $L=\lim_{n\rightarrow \infty }\frac{x_{n+1}}{x_{n}}$ then $L= ?$ b) If $0<b<a<1$ and $L=\lim_{n\rightarrow \infty }\sum_{k=0}^{n}x_{k}$ then $L= ?$ I don't know...
  6. M

    Prime Factors Bounds in a Recurrence

    Let $$g(n)$$ be the numerators of the elements of the recursion $$i(n)=i(n-1)+\frac{1}{i(n-1)}$$ when they are expressed in simplest form, with $$i(0)=1$$. Let $$p$$ be the smallest prime factor of $$g(m)$$. Show that $$p>4m-4$$.Homework Equations Euler's Theorem? The Attempt at a Solution OEIS...
  7. Destroxia

    I DSP: Recurrence Relations in a Linear Algebra Equation

    Hello, I've been working through some Digital Signal Processing stuff by myself online, and I saw a system that I wanted to write down as a Linear Algebra Equation. It's a simple delay feedback loop, looks like this: The (+) is an adder that adds 2 signals together, so the signal from x[n]...
  8. S

    I The general notion of a recurrence relation

    On the one hand, the intuitive notion of a recurrence relation is clear from examples. On the other hand, what is the precise way to define it? The first interesting technicality is why should we call it a "relation" ? Is it, in general, a "relation" and not the more specific case of a...
  9. H

    A Interdependent Recursive Equations

    Hi, I have a system that I am trying so solve in terms of m, and have two recursive equations: The problem for me is that each recursion is dependent on the value from the other! I know that they are both solvable, however I have no idea what approach I could take to express each only in...
  10. W

    I A nonlinear recurrence relation

    Hi Physics Forums, I am stuck on the following nonlinear recurrence relation $$a_{n+1}a_n^2 = a_0,$$ for ##n\geq0##. Any ideas on how to defeat this innocent looking monster? I have re-edited the recurrence relation
  11. B

    MHB Recurrence Relations - Determining a solution of the recurrence relation

    Hello - I am having a tough time understanding the problems in the attached picture (Problem 13). My issue is understanding how I plug in the proposed solutions, specifically those that include n. I am able to solve A and B but unable to solve the rest. For instance, how do I plug in C or...
  12. T

    A How Do You Solve Harper's Equation in Quantum Mechanics?

    For a single particle in a 2D square lattice in the presence of an Abelian magnetic field Schroedinger's equation transforms into Harper's equation g(m+1) + g(m-1) = [E - 2 cos(2\pi m \alpha- \nu)]g(m) where \psi(x,y)=\psi(ma,na) = e^{i\nu n} g(m) \\ \alpha= \frac{e a^2 B}{h c} I am familiar...
  13. K

    MHB Determining a determinant using recurrence relations

    I'm a little stuck here. I should determine the following determinant. I first tried to simplify it a little by using elemntary transformations. And then I did Laplace expansion on the last row. $\begin{vmatrix}2 & 2 & \cdots & 2 & 2 & 1 \\ 2 & 2 & \cdots & 2 & 2 & 2 \\ 2 & 2 & \cdots & 3 & 2 &...
  14. S

    A Algorithms for solving recurrence relations?

    Is there good survey of known algorithms for solving recurrence relations ? By "solving" a recurrence relation such as a_n = \sum_{i=1}^{k} { c_k a_{n-k}} , I mean to express a_n as a function of n . In the case that the c_i are constants the algorithm based on the "characteristic...
  15. 22990atinesh

    Solving recurrence by changing variables

    Consider the below recurrence ##T(n) = 2 T(\sqrt(n)) + \log n## substituting ##\log n = m \implies n = 2^m## ##T(2^m) = 2 T(2^{\frac{m}{2}}) + m## substituting ##S(k) = T(2^m)## I'm getting below equation ##S(k) = 2 S(\frac{k}{2}) + m## How can I change 'm' to 'k' in above equation.
  16. H

    Seek power series solutions of the given differential equation

    I know there are a number of ways to do this problem, to increment the series etc. but, would someone please be able to explain how they get the answers for this problem simply and easily ? Thanks! A screen shot is attached
  17. D

    Recurrence relations define solutions to Bessel equation

    I'm trying to show that a function defined with the following recurence relations $$\frac{dZ_m(x)}{dx}=\frac{1}{2}(Z_{m-1}-Z_{m+1})$$ and $$\frac{2m}{x}Z_m=Z_{m+1}+Z_{m-1}$$ satisfies the Bessel differential equation $$\frac{d^2}{dx^2}Z_m+\frac{1}{x}\frac{d}{dx}Z_m+(1-\frac{m^2}{x^2})Z_m=0$$...
  18. S

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

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

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

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

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

    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. 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.
  25. 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...
  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. 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...
  28. 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...
  29. 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
  30. 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...
  31. 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...
  32. 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...
  33. 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...
  34. 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...
  35. 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!
  36. 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"...
  37. 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...
  38. 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...
  39. 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)...
  40. 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...
  41. 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...
  42. 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...
  43. 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...
  44. 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...
  45. 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 =...
  46. 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.
  47. 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...
  48. 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...
  49. N

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

    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...
Back
Top