Questions tagged [recurrence-relations]
Questions regarding functions defined recursively, such as the Fibonacci sequence.
6,774
questions
0
votes
2answers
39 views
How to find a non-recursive formula for a recursively defined sequence
Given:
$\mu(0)=0$
$\mu(i)= 2\mu(i-1) + 2^{i-1} \ \ \ \ \ \ \forall i \in N $
I would like to know if there is any way of obtaining the non recursive formula for $\mu (i)$:
$\mu(i) = i2^{i-1}$
...
0
votes
2answers
31 views
calculating total number of allowable paths
I seem to be struggling with the following type of path questions
Consider paths starting at $(0, 0)$ with allowable steps
(i) from $(x,y)$ to $(x+1,y+2)$,
(ii) from $(x,y)$ to $(x+2,y+1)$,
(iii)...
-5
votes
0answers
55 views
Rumor has it in Canada that needs to be solved… [closed]
A rumour is being spread by students in Canada. At the start of day $1$, a set of $10$ people know the rumour. Let $S_0$ be this set of people, and for $n \geq 1$, let $S_n$ denote the set of people ...
0
votes
2answers
22 views
finding formula for generating function for recurrence relation
I need to solve the recurrence relation
$$A_n=2A_{n-1}+A_{n-2}$$
with $A(t)=\sum_{n=0}^\infty A_n t^n$ and initial conditions $A_0 = 1$ and $A_1=2$.
I am trying to find the generating function ...
1
vote
0answers
18 views
Solving recurence equations - reference request
I have to solve several recurrence equations originating from physical problems, and I am looking for some references where techniques for different types of equations are collected.
Most of my ...
0
votes
3answers
22 views
Trial solution for in-homogenous differential equation with complex numbers
I am trying to solve following:
Given is the differential equation $y^{(4)} + 4y'' + 16y = b(x)$ with the solutions $z_{1,2}=±2i$.
Now I have to find trial solutions for the particular solutions, ...
2
votes
2answers
34 views
Closed form of a specific recurrence relation
I have the following equation which I am trying to find the closed form for:
$$ x_{n+1} = \frac{1}{2}-\frac{x_{n}}{2}$$
So far rearranging and substituting has yielded the following equations:
$$...
2
votes
1answer
25 views
Recurrence relation of Sn that depends on Sn-1
OK, so I have run into this weird question about recurrence relations that I cannot complete by myself (first year comp. sci. student and first discrete math class, studying by myself). To help you ...
1
vote
3answers
122 views
Recurrence relation with python. [closed]
How to find the terminating value of the continued fractions
$$
S=3-\cfrac2{3-\cfrac2{3-\cfrac2{\ddots}}}
$$
by writing a recurrence relation in Python? (Start from any guess value other than 1.)
1
vote
1answer
53 views
Prove a number doesn't belong to a sequence
You are given the sequence defined by the following recurrence relation:
$$a_n = \cases{a_0 = 1\\a_1 = 3\\a_{n+1} = 5a_n + a_{n-1}, \forall n \geq 1}$$
You are then asked to prove that $123456789 \...
0
votes
0answers
21 views
Steady state of a non-trivial Markov chain.
This is a generalization of the question Solving another non-trivial recurrence relation. Let $\lambda^C \ge 0$, $\lambda^M \ge 0$ and $\Lambda \ge 0$ and $q\in (0,1)$..Without loss of generality we ...
-2
votes
0answers
14 views
Relation Recurrence
Problem:
d.
Solution
Where are they getting the constant factor 2 from?
Solution
0
votes
2answers
15 views
Finding a particular solution of a recurrence relation
Consider the following recurrence relation
$$X_{n+1} - \rho X_n = W_{n+1}, \ \ \ \ \ \ \ \ \ \ \ n\geq 0$$
with initial condition $X_0 = Y$ and $\rho \in (0,1)$. I would like to find a particular ...
1
vote
2answers
28 views
Prove that $X_n=(-5)^nX_0+a_n$ where $a_n=-5a_{n-1}+\frac{1}{n}, a_0=0$
Let $X_n=-5X_{n-1}+\frac{1}{n}$ for some initial value $X_0$. Prove that $X_n=(-5)^nX_0+a_n$ where $a_n=-5a_{n-1}+\frac{1}{n}, a_0=0$. Determine the condition of the calculation task $ X_{20} $ due to ...
3
votes
1answer
28 views
Prove $a_t \leq \frac{c}{t}$
We have the recursive equation $$a_t^2 = (1 - a_t)a_{t-1}^2$$ $$a_0 = 1$$
Prove that there exists constant $c$ such that $a_t \leq \frac{c}{t}$, and find the smallest such $c$.
I was able to get ...
0
votes
0answers
19 views
Given this recursive sequence, how do I find the general term? [closed]
The sequence is:
$$a_1 = 3$$
$$a_{n+1} = \frac{1}{2}(3a_n^2 +1) - a_n, \;n \geq 1$$
How do you find the general term of this sequence?
1
vote
2answers
29 views
How to transform a m-th order difference equation into a first order system of difference equations?
I have a problem that asks for following:
Consider the in-homogenous linear difference equation $y_t-4y_t+2y_{t-3}=4^t$. Write the LDE as a system of first-order LDEs.
The solution is given: define $...
-3
votes
0answers
39 views
Detailed steps for Zeilberger's creative telescoping for hypergeometric sums?, exactly after specifying $r(n)$ and$p(n)$ using Gosper's algorithm.
I would like to begin by apologizing because I am short of application on how to apply the algorithm on finite sums.
my questions are maybe like the following:
1. how to check that our sum is ...
0
votes
1answer
31 views
Finding an explicit formula for the following exponential generating function [duplicate]
So I have the following formula for the coefficient of the recursion and I am trying to find an explicit formula for $a_n$ the nth coefficient:
$$ a_n = (n+1)a_{n-1} + 3^n $$
$$ a_0 = 1; \space\...
-1
votes
0answers
26 views
Prove that in a recurrence relation a_n+2 = a_n+1 + a_n , m | n if and only if a_m | a_n [closed]
I came up with this problem in a Problem Set on Recurrence Relations :
Prove that in a recurrence relation a_n+2 = a_n+1 + a-n , m |n if and only if a_m | a_n
I can understand this is a fibonacci ...
0
votes
1answer
18 views
Validity of Proof that Recursive Function is Increasing
I have a recursive function defined as follows,
$$a_{1}=1,a_{k+1}=\sqrt{2a_{k}+3} \: \forall k\in \mathbb{N}$$
I think I found a very quick way to demonstrate that the function is increasing, but ...
4
votes
1answer
70 views
Convergence of a recurrent sequence
Sorry if this was already proved (that sequence converges to $\pi$) but I cannot find that proof. So recurrent sequence is :
$$a_{n+1}=a_{n}+\sin(a_n)$$
and it seems if $0 < a_0 < 2\pi$ it ...
-4
votes
0answers
33 views
For constants $a$ and $b$, the general solution of the recurrence relation $a_n = 4a_{n-1}+12a_{n-2}$ is…? [closed]
For constants $a$ and $b$, the general solution of the recurrence relation
$$a_n = 4a_{n-1}+12a_{n-2}$$ is...?
0
votes
1answer
15 views
Reference stability/convergence of nonlinear recurrence relations using analytical methods
Example of a problem
Let’s say we have the recurrence relation :
$$
x_{n+1}=\frac{2}{3}(2x_n -x_n^2).
$$
We can easily find its fixed points, namely $x=0$ and $x=1/2$. I have found numerically that ...
1
vote
1answer
11 views
Limit of Recursive Function (Methodology)
Goal:
Find
$$\lim_{n \rightarrow \infty} d_{n+1}^2$$
where
$$d_{n+1}^2 = d_n^2 + r^2 - 2 \cdot r \cdot d_n \cdot \cos \theta$$
for constant $r$ and $\theta < \frac{\pi}{2}$.
Attempt:
\begin{...
0
votes
0answers
33 views
Recurrence relation proof
Let $\alpha$ be a positive integer. Let $b_n$, $n=1, 2, 3 \ldots$ be the sequence given by the recurrence relation $b_{n+2}=2\alpha^2b_{n+1}-\alpha^4 b_{n}$, $n=1, 2, 3 \ldots$ with initial ...
4
votes
2answers
63 views
solution to recurrence relation $ a_{n+2}=-2 a_{n+1}+8 a_n+4n^2$
Find the solution for the below recurrence relation with initial conditions $a_1=10$, $a_2=31$
$$
a_{n+2}=-2 a_{n+1}+8 a_n+4n^2\,.
$$
Let us first consider the corresponding homogeneous recurrence ...
0
votes
0answers
12 views
Question about Expected Values for a probabilistic recurrence relation
Let $Q(x)$ be such that
$$Q(x) = \begin{cases}
Q(x - 1) + 1 & \text{w.p.} \ \ 0.5 \\
0.5Q(x - 1) & \text{w.p.} \ \ 0.5 \\
\end{cases}$$
with $Q(1) = 1$.
What is the expected value of $Q(n)$ ...
0
votes
1answer
20 views
Searching for a linear operator specified as a recurrent relation
I am learning about operators and some other stuff in linear algebra, and I have never encountered a problem that involves a linear operator which is defined recursively, that is:
$$A: V \to V$$
$$A ...
0
votes
1answer
34 views
Markov chain recurrence solving
I am given a transition matrix for the markov chain
on the space state $X=\{1,2\}$
$P=\begin{pmatrix}
1-a & a\\
b & 1-b
\end{pmatrix}$
We are asked to find $P^n$ as a hint I am told to notice ...
0
votes
0answers
29 views
Can a closed form for the following recurrence relation be found?
I stumbled across a problem that involves the following recurrence relation (also with different values for the $\frac{2}{3}$):
$$
p(x+1) = p(x) + \frac{2} {3p(x)}\\
\text {or in alternate form}\\
p(...
0
votes
1answer
27 views
Generating Function of Integer Partitions
Let $p_{k}(n)$ be a number of partitions of $n$ that into parts not greater than $k$.
$p_{k}(n)=p_{k-1}(n)+p_{k}(n-k)$
i will prove this partition recurrence bu using Generating Functions of ...
0
votes
2answers
26 views
How to solve linear recurrence relation based on conditions?
Given
$F(n)=a\cdot F(n-1)-b$ ,$n$ even
$F(n)=a\cdot F(n-1)+b$ ,$n$ odd
$F(0),a,b$ are constants.
How to calculate $n$-th term in $log(n)$ time?
I learnt matrix exponentiation technique.
But ...
0
votes
0answers
36 views
Prove $\left(m-2\right){2m-3\brace m-1}>m{2m-3\brace m}$
How it can be shown that:
$$\left(m-2\right){2m-3\brace m-1}>m{2m-3\brace m}$$
For $ m>2$.
Where ${n\brace m}$ denotes Stirling numbers of the second kind.
Using the recurrence ${n\brace m}={...
0
votes
1answer
28 views
Confusion about one of the conditions for the Akra-Bazzi method solving recurrences
In this paper by Akra & Bazzi, we consider linear divide-and-conquer recurrences of the form:
$$u_n = \begin{cases} u_0 & n = 0 \\ \sum_{i=1}^{k} a_{i} u_{\lfloor \frac{n}{b_{i}} \rfloor} + ...
1
vote
1answer
38 views
Derivative of exponential with function argument
I am trying to derive an expression for the derivative of an exponential. Here is the task phrased as a problem
For the function $g(x) = \exp(f(x))$ where $f(x)$ is real valued and continuously ...
35
votes
0answers
2k views
Is OEIS A248049 an integer sequence?
The OEIS sequence A248049 defined by
$$ a_n \!=\! (a_{n-1}\!+\!a_{n-2})(a_{n-2}\!+\!a_{n-3})/a_{n-4} \;\text{ with }\; a_0\!=\!2, a_1\!=\!a_2\!=\!a_3\!=\!1.$$
is apparently an integer sequence but I ...
1
vote
1answer
27 views
Solution to Second Order Difference Equation for PDEs
I am using the book by Strauss on partial differential equations and I am looking at the proof for stability requirements of numerical approximations. There is a part of the proof that I don't quite ...
2
votes
1answer
119 views
Given two functions with recurrence relations and starting values, prove that $f(2020)<5$
There are two functions $f:\mathbb N\to \mathbb R^+$ and $g:\mathbb N\to \mathbb R^+$. For all $n\in \mathbb N$: $$f(1)=1$$ $$g(1)=2$$ $$f(n+1)=\frac{1+f(n)+f(n)g(n)}{g(n)}$$$$g(n+1)=\frac{1+g(n)+f(n)...
3
votes
1answer
68 views
A question about the plastic number
The plastic number is well known to be the limiting ratio of the Padovan sequence (OEIS A000931), to wit,
$$
P_n=P_{n-2}+P_{n-3}\\
\lim_{n\to \infty} \frac{P_{n+1}}{P_n}=p
$$
However, it is also the ...
1
vote
2answers
78 views
Given the sequence $a_{n+1}^3 = a_n^2 a_{n-1}$, with $a_0=1$ and $a_1=a$ find $a$ such that $\lim\limits_{n \to \infty} a_n = 8$.
Consider the following sequence $(a_n)_{n \ge 0}$ (it has positive terms):
$$a_0 = 1$$
$$a_1 = a$$
$$\hspace{3.5cm} a_{n+1}^3 = a_n^2 a_{n-1} \hspace{2cm} n \ge 1$$
I have to find the value of $a$ ...
-2
votes
3answers
30 views
Having difficulty solving a recurrence relation
Given that $a_{n+1}=\dfrac{a_{n-1}}{1+n\cdot a_{n-1}a_{n}}$ for $n=1,2,3,....$ and $a_0=a_1=1$. Find the value of $a_{199}\cdot a_{200}$. Also give with proof the general formula of $a_{n}a_{n+1}$?
2
votes
1answer
76 views
An interesting subring of $\Pi \mathbb{Z}$
Let's look at this set ($e_{i}=(\delta_{ij})_{j}$ for all $i,j\geq0$ (kronecker delta))
$R_{\mathbb{Z}} =$$\{\sum_{i=0}a_{i}e_{i}$ : $a_{i}\in \mathbb{Z}$ $ \land$ $ \exists k,A_1,A_2,A_3,...,A_k\in\...
0
votes
2answers
43 views
How to obtain a formula for $f(z)$ given this recurrence
I am trying to figure out how to derive a formula for $f(z)$ that is a function of $z$ and maybe $k \in \mathbb{N}$:
$$
f(z) = 1+z f \bigg(\frac{z}{1+z} \bigg)
$$
As an attempt, I tried a change of ...
0
votes
2answers
36 views
How long until equilibrium between two recursive functions?
Problem
I'm trying to figure out how long it takes Particle A and Particle B to reach an equilibrium in their temperatures. I've simplified this down to a pair of recursive functions. Let's say that ...
1
vote
2answers
29 views
Doubt on a recurrence equation
I have the following recursive equation for a pmf $P(s)$:
$$P(s+1)=2 \lambda (1-\lambda) P(s)+ \lambda^2 \sum_{s'=0}^s P(s') P(s-s')$$
Here $s$ is a natural number and I have two initial conditions $P(...
1
vote
1answer
47 views
Prove that the recurrence relation $b_k = -4 \frac{n}{k} \left( b_{k-1} + b_{k-2} \right)$ is never zero.
Let the following recurrence relation be given:
$b_0 = 1$
$b_1 = -4$
$b_k = -4 \frac{n}{k} \left( b_{k-1} + b_{k-2} \right)$ with $ k \leq n$ and $k,n \in \mathbb{N}$
$n$ is a constant.
Question: ...
0
votes
2answers
82 views
Finding $\frac{I_1}{I_2}$ from recurrence relation
Consider following recurrence relation:
$$2(\sum_{i = 0}^k I_{n-i}) + I_{n-k} = I_{n-k-1}$$
$k = 0 , 1 , \dots , n-1$
Also $I_0 = \frac{V}{R}$.
Assuming that $n \ge2$ is a fixed integer, I'm ...
0
votes
3answers
43 views
Solve the recurrence: $T(n) = \sqrt{2n}T(\sqrt{2n})+\sqrt{n}$
I found a recurrence of a similar form on this forum, but I couldn't use it to gain any intuition for my question. So far, I've tried 3 things. I've tried unrolling it but could not really see a ...
-2
votes
2answers
23 views
what happens to this equation after change of variable?
I have the following equation $f$:
$$
f(\frac{1}{z}) = 1 + \frac{1}{z} + \frac{1}{z(z+1)} + \frac{1}{z(z+1)(z+2)} + ...
$$
If I make a change of variable $\frac{1}{z}=k$, does this mean that the ...
