Questions tagged [recurrence-relations]
Questions regarding functions defined recursively, such as the Fibonacci sequence.
9,353 questions
5
votes
1
answer
149
views
Can $p(\lambda)=\lambda^3 -2\lambda^2+\lambda$ be the characteristic polynomial of a linear difference equation?
Question:
Let $$p(\lambda) =\lambda^3 -2\lambda^2+\lambda. $$ Can $p(\lambda)$ be the characteristic polynomial of a linear difference equation? Justify.
My answer:
Yes, because there exists a ...
- 3,235
6
votes
5
answers
314
views
Proving that $x := x - yt$; $y := y + xt$ traces an ellipse
I was investigating the iterated function formed by the following JavaScript code, trying to find an invariant that can prove that the system doesn't slowly diverge:
...
- 191
0
votes
0
answers
43
views
Perturbation of linear recurrence
Suppose I have the recurrence relation
$$ f(r) = \alpha + \beta \sum_{s=1}^{r-1}f(s), \qquad r \geq 2$$
for some $\alpha, \beta > 0$ and initial condition $f(1) = \gamma > 0$. This gives a ...
0
votes
1
answer
72
views
Behaviour of sequence defined by recurrence
I am a bit rusty on the topic, and I have been presented the following exercise I am not really sure how to deal with. We have the sequence
$$ \begin{cases} x_0 \geq 0 \\ x_{n+1} = 2|x_n -1| \end{...
- 3,766
0
votes
2
answers
76
views
A permutation $p_{1}, p_{2}, p_{3}, \dots p_{n}$ For each $i = 1, 2, 3, \dots, n-1$, $\exists j > i$ such that $\lvert p_{j} - p_{i} \rvert = 1$.
A permutation $p_{1}, p_{2}, p_{3}, \dots p_{n}$
For each $i = 1, 2, 3, \dots, n-1$, there exists a $j > i$ such that $\lvert p_{j} - p_{i} \rvert = 1$.
For example, the orderly permutation of $n = ...
- 11
2
votes
0
answers
96
views
Coupon collector in batches, no duplicates in a batch
There was recently a question that was marked as duplicate of this question and then deleted. But the way I understood it was that the selection of the batch was done without replacement. Anyhow I'll ...
- 12.7k
3
votes
1
answer
89
views
$\partial_x f_n(x)=f_{n-1}(x)$ What conditions are needed to guarantee a unique solution?
Consider the functional-recurrence equation
\begin{align}\tag{1}\label{1}
\partial_x f_n(x)=f_{n-1}(x),
\end{align}
what conditions must we impose to guarantee a unique solution?
There are several ...
- 2,546
1
vote
0
answers
37
views
Restricted Factorizations Counting identities
Reading literature related to the problem of multiplicative partitions A001055 OEIS sequence (also named "factorizatio numerorum", "Oppenheim problem", "factorizations ...
- 709
1
vote
0
answers
173
views
Is this recurrence for $\pi$ with order $2m+1$ already known? [closed]
Recurrence formula for $\pi$ with convergence order $2m+1$:
$$
x_{n+1} = x_n + \sum_{k=1}^{m} \left[ (-1)^{m+k} \cdot \frac{1}{k} \prod_{\substack{j=1 \\ j \ne k}}^{m} \frac{j^{2}}{k^{2} - j^{2}} \...
- 2,603
0
votes
0
answers
47
views
Proportionality of solution of a system of equation
In the book of sakurai
Modern Quantum Mechanics they have this $$
\begin{aligned}
& \sqrt{(j \mp m)(j \pm m+1)}\left\langle j_1 j_2 ; m_1 m_2 \mid j_1 j_2 ; j, m \pm 1\right\rangle \\
& =\sqrt{...
- 339
0
votes
1
answer
100
views
If 2 recursion relations have the same coefficients, are the solutions proportional?
In the book of sakurai
Modern Quantum Mechanics they have this $$
\begin{aligned}
& \sqrt{(j \mp m)(j \pm m+1)}\left\langle j_1 j_2 ; m_1 m_2 \mid j_1 j_2 ; j, m \pm 1\right\rangle \\
& =\sqrt{...
- 339
6
votes
2
answers
475
views
How do I solve this recurrence relation with a squared coefficient?
I started with the following recurrence relation
$$ s \left( n \right) = s \left( n-1 \right)^{2} - 1, \qquad s \left( 0 \right) = 2$$
and got to
$$\sum_{n=0}^{\infty}s\left(n+1\right)x^{n}=\sum_{n=0}^...
user1707124
0
votes
0
answers
55
views
Closed form of Homogeneous Linear Recurrence Relations
I know that given a linear homogeneous recurrence relation of order k:
$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$$
We can get the characteristic equation:
$$r^n = c_1 r^{n-1} + c_2 r^{n-...
- 59
1
vote
2
answers
89
views
Reference request : using an analogy with differential equations to study recursive sequences
I'm looking for references for using analogies with differential equations to study recursive sequences.
For example $u_{n+1} = \sin(u_n)$. It's not difficult to show that if $u_0$ is between 0 and $\...
- 1,479
1
vote
0
answers
86
views
How to calculate the iterations of Fibonacci Sequence under square roots
Compute the value of
$$\sqrt{1 + F_2\sqrt{1 + F_4\sqrt{1 + F_6\sqrt{1 + F_{2n}\ldots}}}}$$
where $F_n$ denotes the $n$-th Fibonacci number with $F_0 = 0$, $F_1 = 1$.
This is a problem from a sheet ...
- 51