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

    I Entropy reversal in an infinite static universe?

    As far as I know, entropy could be reversed by the Poincaré recurrence theorem if it had a finite horizon given by some amount of vacuum energy causing an accelerating expansion. However, I found this lecture by Leonard Susskind () where he tells a way through which the vacuum could decay into...
  2. 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} -...
  3. MevsEinstein

    B Recurrence relation in a recurrence relation?

    There's a famous functional equation that was asked in the 2019 IMO. It looks like this: find all f: Z -> Z where f(2a)+2f(b)=f(f(a+b)). I thought of solving it using a recurrence relation where a_n=f(nx). But when I substituted values in the functional equation (after setting a and b equal...
  4. D

    I Liouville's Theorem and Poincare Recurrence Theorem

    Hi. I am working through some notes on the above 2 theorems. Liouville's Theorem states that the volume of a region of phase space is constant along Hamiltonian flows so i assume this means dV/dt = 0 In the notes on the Poincare Recurrence Theorem it states that if V(t) is the volume of phase...
  5. TheGreatDeadOne

    I Using recurrence formula to solve Legendre polynomial integral

    I am trying to prove the following expression below: $$ \int _{0}^{1}p_{l}(x)dx=\frac{p_{l-1}(0)}{l+1} \quad \text{for }l \geq 1 $$ The first thing I did was use the following relation: $$lp_l(x)+p'_{l-1}-xp_l(x)=0$$ Substituting in integral I get: $$\frac{1}{l}\left[ \int_0^1 xp'_l(x)dx...
  6. M

    MHB Dynamic programming: which recurrence relation do we use?

    Hey! :unsure: At the cash register of a store we want to give change of worth $V$ cents of euro. Create and analyze a greedy algorithm that gives the change using the minimum number of coins. Assume that the available coins are the euro subdivisions, i.e. $\{1, 2, 5, 10, 20, 50\}$ and that we...
  7. 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.
  8. evinda

    MHB Find the general formula of the recurrence relation

    Hello! (Wave) Suppose that we have the recurrence relation $a_k=3^k-a_{k-1}, a_0=1$. By replacing the terms of the sequence we get that it is equal to $a_k=3^k-3^{k+1}+3^{k+2}-a_{k-3}$. How do we get that it is equal to $a_k=3^{k}-3^{k-1}+3^{k-2}- \dots+ (-1)^k$ ? :unsure: Also, why is the...
  9. JD_PM

    Understanding Poincare's recurrence theorem

    The Poincare's recurrence theorem : This theorem implies the following: Suppose a container is divided in two by a wall. Half of it contains particles and the other none. If you were to remove the wall and wait a very very long time, the particles would eventually be found in the same half...
  10. R

    What is the recurrence relation for climbing stairs with 1 or 2 steps at a time?

    Homework Statement I'm suppose to find the # of ways to climb n stairs if a person can take 1 stair or 2 stairs at a time. The question is: " Find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one stair or two stairs at a time."...
  11. Mr Davis 97

    Proving that a recurrence holds for all n

    Homework Statement Let ##H=\{2,3,4, \dots , n\}##. Find a recurrence relation that involves the following number: ##\displaystyle \sum_{G\subseteq H}\frac{1}{\prod_{x\in G}}##, where ##G\not = \{\}## Homework EquationsThe Attempt at a Solution If ##H=\{2\}##, let ##S_2## be the sum. If...
  12. 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...
  13. 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...
  14. 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]...
  15. Robin04

    First-order homogeneous recurrence relation with variable coefficient

    Homework Statement I need to find the explicit formula for the following recursive sequence: ##v_n=\frac{2}{1+q^n}v_{n-1}## where ##0<q<1## is a constant Homework Equations I found the following method to solve it...
  16. 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...
  17. 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...
  18. 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
  19. Mr Davis 97

    Showing a limit of the recurrence relation

    Homework Statement Let ##x_1=1## and ##\displaystyle x_{n+1} = 3 x_n^2## for ##n \ge 1##. a) Show if ##a = \lim x_n##, then ##a = 1/3## or ##a = 0##. b) Does ##\lim x_n## actually exist? Homework EquationsThe Attempt at a Solution I have proven before that, in general, ##\lim s_{n+1} = \lim...
  20. 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...
  21. M

    How can the recurrence formula for a sequence be found?

    Homework Statement Find a recurrence formula for the sequence (ai) = 1, sqrt3, sqrt(1+sqrt3), sqrt(1+sqrt(1+sqrt2)) in terms of i and ai Homework EquationsThe Attempt at a Solution no idea where to start, this is a bonus question, and I have learned how to solve these type of problems
  22. S

    Recurrence relation for harmonic oscillator wave functions

    1. Homework Statement I've been using a recurrence relation from "Adv. in Physics"1966 Nr.57 Vol 15 . The relation is : where Rnl are radial harmonic oscillator wave functions of form: The problem is that I can't prove the relation above with the form of Rnl given by the author(above). I've...
  23. I

    A Recurrence Formula for 3,5,13,27,55,...

    What is the recurrence formula for the sequence [3,5,13,27,55,...] Thank you for any help.
  24. M

    Where is the recurrence stable in the (n,x) plane for increasing n?

    Homework Statement In the ##(n,x)## plane, where is the recurrence stable for increasing ##n##? $$E_{n+1}(x) = \frac{1}{n}\left( \exp(-x)-xE_n(x)\right):E_n\equiv \int_1^\infty \frac{\exp(-xt)}{t^n}\,dt$$ and ##n\in \mathbb{N},\:x\geq0##. Homework Equations Nothing comes to mind. The Attempt...
  25. P

    MHB Solve Recurrence Equation for Domino Chart of 1xn

    Hey everyone, it's me again with yet another recurrence equation I've been stuck with: Using recurrence relations (recurrence equations... is it the same thing?), solve the following: There is a chart with dimensions 1xn. We have dominoes in two different colors which we should use to fill up...
  26. P

    Mathematica Numerically solve recurrence relation

    I am trying to numerically solve the recurrence relation for: $$ T[n]=\frac{sm}{2\hbar^2i k_n}(T[n-1]+T[n+1]) \\ k_n=(\frac{2m(E-\hbar \omega n)}{\hbar^2})^{1/2}$$ My code is: RecurrenceTable[{Tn[ n] == (s* m/(2*\[HBar]^2* I*(2*m*(En -...
  27. P

    Mathematica Solving recurrence equations in QM tunneling example

    I am ultimately trying to get Mathematica to solve some equations which are related to a tunnelling problem with an oscillating delta potential. I have the coefficients for absorption and emission: $$ T_n = \frac{sm}{i\hbar^2} (T_{n-1} + T_{n+1})$$ $$T_q = \frac{sm}{2ik_q \hbar^2} (T_{q-1}...
  28. 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 &...
  29. Mr Davis 97

    Recurrence Relation for Two Consecutive 0s in Ternary Strings

    Homework Statement Find a recurrence relation for the number of ternary strings of length n that contain two consecutive 0s. Homework EquationsThe Attempt at a Solution Let ##a_n## count the number of ternary stings of length n that contain two consecutive 0s. Then, we can split the total...
  30. Mr Davis 97

    Initial conditions for recurrence relation

    Homework Statement If ##a_n## counts the number of ways to climb a flight of n stairs if one can take 1, 2, or 3 steps at a time, then ##a_n = a_{n-1} + a_{n-2} + a_{n-3}##. What are the three initial conditions? Homework EquationsThe Attempt at a Solution I would say that ##a_0 = 1## since...
  31. Mr Davis 97

    I Proving that a solution to a recurrence relation is true

    I am a little confused about how we prove that a solution for a recurrence relation is correct. For example, say that I have the recurrence relation ##H_n = 2H_{n-1} +1##. Using an iterative process, we guess that the solution is ##2^n - 1##. Now, to prove that this is correct, it seems that it...
  32. P

    Recurrence relation for Bessel Functions

    Homework Statement I want to prove this relation ##J_{n-1}(x) + J_{n+1}(x)=\frac{2n}{x}J_{n}(x))## from the generating function. The same question was asked in this page with solution. http://www.edaboard.com/thread47250.html My problem is the part with comparing the coefficient. I don't...
  33. 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...
  34. hilbert2

    About Entropy and Poincare Recurrence

    I was reading about entropy, Poincare recurrence theorem and the arrow of time yesterday and I got some ideas/questions I'd like to share here... Let's think a about a system that is a classical ideal gas made of point particles, confined in a cubic box. Suppose that at time ##t=0## all the...
  35. L

    I Closure Phase - Interferometry - Recurrence Relation

    Hello, I'm trying to calculate a recurrence relation of the phases of 3 telescopes in a closure phase. Usually in a stellar interferometer we have 3 telescopes, located in a triangle, measuring intensity of light in 3 points on a far field plane. I found an article, describing how the phase is...
  36. I

    MHB Proving Recurrence Relations and Set Elements: T Function and Natural Numbers

    We define a function T : \Bbb{N} -> \Bbb{N}, such that T(2k+1) = 2k+2 and T(2k) =k. Also, T^2(n)=T(T(n)), and generally: T^k(n)={T}^{k-1}(T(n)). a) Prove that for every n\in\Bbb{N}, there exists a positive integer k, such that T^k(n)=1 b) We say {c}_{k} is the number of elements in the set...
  37. C

    How to find upper bound for recurrence relation

    Homework Statement Find a tight upper bound for the recurrence relation using a recursion tree argument Homework Equations T(n)=T(n/2)+T(n/3)+c The Attempt at a Solution I don't know how to do this problem because the tree doesn't have symmetry. One side of the tree can keep going because of...
  38. B

    Characteristic equation for recurrence equation

    An ODE of second order with constants coefficients, linear and homogeneous: Af''(x) + Bf'(x) +Cf(x) = 0 has how caractherisc equation this equation here: Ax^2 + Bx +C = 0 and has how solution this equation here: f(x) = a \exp(u x) + b \exp(v x) where u and v are the solutions (roots) of the...
  39. B

    Solution for f(n) in recurrence equation

    Exist solution for SAR(n+1) in this equation: https://en.wikipedia.org/wiki/Parabolic_SAR ? I want to eliminate SAR(n), but I never saw this kind of equation before...
  40. L

    Are Fictional Eclipses Limited by Scientific Cycles?

    Dear all, I have been reading through this article about how often different types of eclipse (eclipse cycles) can occur. I'm presuming that all fictional eclipses have to be variations of these? Even with a fictional planet/moon/solar system? But what if the desired recurrence of an eclipse...
  41. B

    Solving a Recurrence Relation Using Induction: Step-by-Step Guide

    Below I have uploaded the page I am having trouble with. Here it says that it is using induction on n but I don't understand how it uses the formula for when n=j to derive the formula for when n=j+1
  42. 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.
  43. T

    Finding a recurrence relation

    Homework Statement a) Find a rec. rel. for an, the number of sequences of length n formed by u's, v's, and w's with the subsequence vv not allowed. b) Repeat part a) but now with the requirement that there is no subsequence uwv. The Attempt at a Solution a) the first letter in the sequence can...
  44. M

    MHB Solution of the recurrence relation

    Hey! :o How can we solve the following recurrence relation? $$f_n=\left (\frac{2}{a^2}+b\right )f_{n-1}-\frac{1}{a^4}f_{n-2} \\ f_0=1, f_{-1}=0$$ I calculated some values to see if there is a general pattern, but it doesn't seems so... $$f_1=\left (\frac{2}{a^2}+b\right ) \\ f_2 =\left...
  45. T

    Where Does 10^{n-1} Come From in the Recurrence Relation Example?

    Homework Statement This isn't actually a homework question.Actually, it's an example from Rosen's Discrete Math and Its Applications that I'm having difficulty with: "A computer system considers a string of decimal digits a valid codeword if it contains an even number of 0 digits. For...
  46. V

    MHB Finding particular solution to recurrence relation

    Hi, I have a question about how to find the particular solutions when trying to solve recurrence relations. For example, trying to solve an+2 = -4an + 8n2n , I begin with finding the roots in the characteristic polynomial associated with the homogeneous equation, so r1 = 2i and r2 = -2i...
  47. 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$$...
  48. S

    MHB Solving Recurrence Relations using Fibonacci Sequence

    Recall that the Fibonacci sequence is defined by the initial conditions F0 = 0 and F1 = 1, and the recurrence relation Fn = Fn−1 + Fn−2 for n > 2. (a) Let F(z) = F0 + F1z + F2z 2 + F3z 3 + · · · be the generating function of the Fibonacci numbers. Derive a closed formula for F(z). (b) Consider...
  49. S

    MHB Discrete Math: Linear Inhomogeneous Recurrence

    How do I solve this 1. (a) Solve the recurrence relation an =6an−2 +8an−3 +3an−4 +64·3^n−4, n􏰀>=4 where a0 =0,a1 =1,a2 =4 and a3 =33. (b) Write down a closed form of the generating function of the sequence an.
  50. M

    Differential Equation - Series - Recurrence Relation

    1. (16+x2)-xy'+32y=0 Seek a power series solution for the given differential equation about the given point x0 find the recurrence relation. So I used y=∑Anxn , found y' and y'' then I substituted it into the original equation, distributed, made all x to the n power equal to xn, made the...