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

6. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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 -...

45. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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...