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.
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...
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} -...
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...
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...
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...
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...
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.
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...
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...
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."...
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...
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...
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...
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]...
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...
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...
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...
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
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...
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...
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
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...
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...
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...
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 -...
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}...
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 &...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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
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...
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...
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...
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...
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$$...
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...
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.
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...