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.
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} -...
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...
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.
(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}##.
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]...
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
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...
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...
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 &...
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 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
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$$...
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...
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...
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...
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...
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)...
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.
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...
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...
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...
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...
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
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...
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...
\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...
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...
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...
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!
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"...
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...
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...
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)...
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...
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...
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...
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...
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...
[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 =...
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.
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...
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...
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...?...
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...