Questions tagged [recurrence-relations]
Questions regarding functions defined recursively, such as the Fibonacci sequence.
8,240
questions
1
vote
1
answer
27
views
Solution (recurrence relation) of non-linear DE using the method of power series
I have to solve this non-linear DE
$y' -e^y -x^2 = 0 , y(0)=c$
using powerseries.
$y(x) = \sum_{n=0}^\infty a_{n}x^n $
$y'(x) = \sum_{n=1}^\infty na_{n}x^{n-1} $
so we get
$\sum_{n=1}^\infty na_{n}x^{...
- 53
4
votes
2
answers
93
views
An interesting recurrent equality, possibly easier to solve in its differential form?
I encountered an interesting inequality that I'm not sure how to approach. Here $c$ is a positive constant.
$$f(n+1) - f(n) = c f(n)\sum_{m=0}^n f(m)$$
I am not familiar with techniques to solve ...
- 475
1
vote
0
answers
53
views
Is there a simpler function $f$ equivalent to $f(x)=af(x-1)^2+bf(x-1)+c$?
I have been using the function $$f(x)=af(x-1)^2+bf(x-1)+c$$ for a project, but wanted to know if there was a closed form of the equation or a form of the function in relation to $f(0)$ or $f(1)$. If ...
- 11
0
votes
3
answers
55
views
Find the general solution of the recurrence relation $3x_{n+2} − x_{n+1} − 2x_{n} = 5$.
Find the general solution of the recurrence relation $3x_{n+2} − x_{n+1} − 2x_{n} = 5$.
Attempt
First I found the auxiliary equation:
$3 \lambda ^ 2 - \lambda - 2 = 0$.
To get the solutions:
$\lambda ...
- 43
2
votes
0
answers
50
views
Expressing $\int_0^\pi \sin^n(x)dx$ in terms of the gamma function
Let $I_n = \int_0^\pi \sin^n(x)dx$ and suppose that we have already established a recursive relation $I_n = \frac{n - 1}{n}I_{n-2}$ and we know that $\Gamma(x + 1) = x\Gamma(x), \Gamma(1/2) = \sqrt{\...
- 259
1
vote
1
answer
50
views
How to define a recursive non-constant geometric sequence non-recursively (if that even makes sense)
The title, basically.
I have a sequence that I've defined as $a_n=a_{n-1}(4n^2-8n+3)$, where $a_0=1$ and $a_1=-1$. I want to find a way to define it non-recursively, yet my mind has failed me.
I've ...
0
votes
0
answers
18
views
Finding the stationary value of a linear recurrence [duplicate]
I encountered the following recurrence when I was analyzing a problem in probability theory:
$$
a_{n}=\frac{ a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}+a_{n-5}+a_{n-6} }{6},
$$
with $a_{-5}=a_{-4}=a_{-3}=a_{-2}=...
- 739
1
vote
0
answers
19
views
Combinatorics, 2-Tree, Sequence
I've just thought about a combinatoric problem.
Say you have a tree with $n$ nodes at the $n$-th level ($2$-tree). Number elements based on their position left to right, top to bottom. Let $a_{n,i}$ ...
6
votes
1
answer
51
views
Fibonacci sequences within the Fibonacci sequence recurrence
I'm trying to perform a runtime analysis of the following simple recursive Fibonacci number algorithm:
...
- 75
3
votes
2
answers
134
views
Possible positions of the knight after moving $n$ steps in Chessboard.
Problem
There is a knight on an infinite chessboard. After moving one step, there are $8$ possible positions, and after moving two steps, there are $33$ possible positions. The possible position after ...
- 823
0
votes
0
answers
18
views
Reference Request: Implicit Difference Equations
I know that there are some studies on implicit differential equations such as
$$ f(x, y, y') = 0. $$
I did some search but found very few results on the discrete version---implicit difference ...
- 363
2
votes
1
answer
85
views
Find the number of ways of tiling a rectangular grid with dominoes
I'm trying to find the number of ways $(a_n)$ of tiling a rectangular grid with dominoes. I want to find a recurrence relation for $(a_n)$.
1
vote
0
answers
60
views
If $𝑓∘𝑔∘ℎ=𝑓 ∧ 𝑔∘ℎ∘𝑓=𝑔$ then must $ℎ∘𝑓∘𝑔=ℎ$?
If not, then What can be said of each $𝑓,𝑔,ℎ$ and are there any simpy-definable minimal conditions imposable upon one or more of the indexable functions that would ensure this symmetric closure? ...
- 19
0
votes
0
answers
34
views
Nonhomegeneous Recurrence Relation
How can I find recurrence relation that
the sequence
$a_n = (n-3)2^n +\frac{n}{2^n}$ satisfy.
I have recurrence relation for linear part.
Charecteristic equation is $(r-2)^2 = r^2 -4r+4$. (since $n.2^...
- 121
0
votes
1
answer
28
views
How can I solve mutual recurrence relation?
I want to solve recurrence relation as following :
$$ g_{l+1} = (1-2t)g_l+2\sqrt{t(1-t)}b_l \quad and \quad b_{l+1}=(1-2t)b_l-2\sqrt{t(1-t)}g_l \quad $$
$$ g_0=\sqrt{t} \quad and \quad b_0 = \sqrt{1-t}...
2
votes
1
answer
58
views
What is the value of $a_1a_2\cdots a_{2019}$?
Let $a_1=\frac 34$ and for any $n\geq2$ $4a_n=4a_{n-1}+\frac {2n+1}{1^3+2^3+\cdots n^3 }$. What is the value of $a_1a_2\cdots a_{2019}$?
I tried $1^3+2^3+\cdots +n^3=\frac {n^2(n+1)^2}{4}$ and
I ...
- 450
0
votes
0
answers
14
views
Linear Recurrences approximation to exponential
I have been reading the solutions to the MIT primes 2011 solutions and am having trouble understanding their logic.
The text basically says that if a_k = a_{k-1} + a_{k - 2} ... a_{k - n}, then a_k is ...
- 1
1
vote
1
answer
277
views
Recursive relation practice
My questions:
Call a string of letters "legal" if it can be produced by concatenating (running together) copies of the following strings:
'v', 'ww', 'xx' 'yyy' and 'zzz'.
For example, the ...
- 5
-3
votes
0
answers
35
views
If $s(n)=3n^2−3n+5$, then $s(n)=2s(n−1)−s(n−2)+c$ for all integers $n\ge 2$. What is the value of $c$?
Solve the following:
If $s(n)=3n^2−3n+5$, then $s(n)=2s(n−1)−s(n−2)+c$ for all integers $n\ge2$. What is the value of $c$?
How do I solve this question?
- 1
4
votes
1
answer
89
views
Solve $a_n=n(a_{n-1}+a_{n-2})$ where $a_0=1,a_1=2$ using generating functions
I am trying to solve a recurrence relation,$a_n=n(a_{n-1}+a_{n-2})$ where $a_0=1,a_1=2$, using generating functions. So, I did: let $$A(x)=\sum_{n\geq 0}a_n\frac{x^{n}}{n!}$$
$$\sum_{n\geq 0}a_{n+2}\...
user1056381
1
vote
1
answer
36
views
solve the recurrence relation $h_n - 0h_{n - 1} - 3h_{n - 2} + 2h_{n - 3}= 0$
$h_n - 0h_{n - 1} - 3h_{n - 2} + 2h_{n - 3}= 0$
$h_0=2, h_1=0, h_2=7$, and n≥3
is given
here is what I did
$x^3-3x+2=0$
$h_n=a1^n+b(-2)^n$
roots of the polynomial are 1 and -2 but there are 3 ...
- 21
1
vote
0
answers
15
views
Proving an inequality for a recursive function using induction
Recently, I have been studying induction proofs as preparation for an exam and I've been stuck at the following exercise for quite some time now, even though I feel like I'm almost there.
Let $T(n)$ ...
- 355
1
vote
2
answers
56
views
Recurrence relation $f(n)=2f(n-1)+n\log(n)$
How to solve the following recurrence relation: $f(n)=2f(n-1)+n\log(n)$ ?
I tried to write $f(n-1)=2f(n-2)+(n-1)\log(n-1)$, so
$f(n)=4f(n-2)+2(n-1)\log(n-1)+n\log(n)$
and then the general relation at ...
- 55
0
votes
1
answer
28
views
Recurrence Equations: Uneven amount of letters
I have a recurrence relation problem that states the following:
Given the alphabet $\sum = \{a,b,c\}$ how many words can be formed that have an uneven amount of "a"'s
From my understanding:
...
1
vote
0
answers
22
views
Verify the monotonically increasing property of this array
I'm doing some exercises on calculating the Array limiting and I am stucked in verifying a monotonically increasing array. Hope someone can help me with the problem.
For an array,
$x_1=1, x_2=1+\frac{...
- 13
0
votes
1
answer
74
views
Find a simple path in given tree with minimum number of edges
Suppose given a Tree $T=(V,E)$. Each nodes in $T$ has a degree at most two. Also, edges in $T$ has weight distinct and positive natural. Suppose $|V|=n$, our goal is find a simple path with length ...
- 1
0
votes
0
answers
27
views
Solving the recurrence relation $\mathcal{T}(n) = \sqrt{n}\text{ }\mathcal{T}(\sqrt{n}) + \mathcal{O}(n^{2}) $
Given Recurrence Relation
$$\mathcal{T}(n) = \sqrt{n}\text{ }\mathcal{T}(\sqrt{n}) + \mathcal{O}(n^{2}) $$
Master Theorem doesn't apply here.
Tried using $n= 2^{k}$, but got stuck at $$\mathcal{T}(2^{...
4
votes
0
answers
159
views
Sum of a recursive series
Find $S_n=\sum_{k=1}^{x} a_{k}$ , where $a_1 = 1$ and $\forall k>1 : a_{k}=a_{k-1}+{\lfloor \sqrt {a_{k-1}} \rfloor} $ and $x$ is a natural number such that $a_{x} \leq n < a_{x+1}$. For simply ...
- 69
1
vote
0
answers
44
views
How do I solve this non-linear differential equation?
I have a formula describing a non-linear system which is as follows:
$-y(x)'' + A|y(x)|^2y(x) = k^2 y(x)$
where A is a constant that I can choose to be a positive or negative integer. I also have ...
- 11
-3
votes
2
answers
37
views
Finding sequence [closed]
I'm looking for the pattern of this series -> $1, 2, 1, 2, 1, 2$. Any help would be appreciated.
$S_k = 2/S_{k-1}, k \in \mathbb{Z}, k \ge 2, S_1 = 1.$
- 3
-1
votes
0
answers
38
views
particular solution form of $h_n - h_{n - 1} = 3 - n$
Particular solution form of $h_n - h_{n - 1} = 3 - n$
In the rhs, we have
$-n$ is of the form : $h_n = -A_1n +A_2$
$3$ is of the form : $h_n = A_3$
because $A_2$ and $A_3$ are some numbers we can ...
- 21
0
votes
1
answer
65
views
How can I find a generating function of $a_n = 8a_{n-1} + 10^{n-1}, a_0=1$ with recurrence relation?
With $a_0 =1$, $a_n = 8a_{n-1} + 10^{n-1}$
Let a generating function with it, $G(x) = \sum a_k x^k$ = $a_0 + \sum (8a_{k-1} +10^{k-1}) x^k =a_0 + \sum 8a_{k-1}x^k + \sum10^{k-1} x^k = a_0 + 8x\sum ...
- 547
1
vote
0
answers
17
views
Solving recurrence with boundary conditions on both sides
I want to solve the following recurrence, for any parameter $x>0$:
$ a[i]= \frac{1}{x} a[i+1]+ (1- \frac{1}{x}) a[i-1]$ for $i \in \{1,...,n-1\}$
$a[0]= 0, a[n]=1$.
i.e. find a closed form for $a[i]...
- 133
0
votes
4
answers
90
views
Given $x_{1} > 2$ and the recursively defined sequence $x_{n+1}=1+\sqrt{x_{n}-1}$
Given $x_{1} > 2$ and the recursively defined sequence $x_{n+1}=1+\sqrt{x_{n}-1}$.
Proof:
(a) $x_{n} \geq 2\ \forall n \geq2$ (which seems obvious given the initial condition, but I also would like ...
1
vote
1
answer
74
views
Is the following sequence $x_{n+1}$ = $x_{n} + 1/x_{n}$ convergent given $x_{1} >0$? [duplicate]
I got the following result : $x_{n+1} = x_{n}+\frac{1}{x_{n}}$ and so forth.
As $x_{1}>0$, then I know by plugging that $x_{k}>1$ for every natural $k$. Hence, the terms in the denominator tend ...
3
votes
1
answer
78
views
Closed-form solution of the recurrence relation $f(m,n)=f(m-1,n)+f(m,n-1)+f(m-1,n-1)$
I'm working with the recurrence relation $f(m,n)=f(m-1,n)+f(m,n-1)+f(m-1,n-1)$, with the boundary condition $f(m,0)=f(0,n)=1$.
After some work, it is not hard to show the generating function is $F(x,y)...
- 631
1
vote
2
answers
62
views
Solution of the recurrence relation $y_n = \frac{1}{2} + \frac{1}{2}y_{n-1}$
$y_0 = 0$ and $y_n = \frac{1}{2} + \frac{1}{2}y_{n-1}$. Solution of this reccurent equation is $y_n = 1 - \frac{1}{2^n}$, accordingly with the software. But I do not understand the minus sign since it ...
0
votes
1
answer
18
views
How to solve discrete time first order difference equations when b is a function of t?
I am having some trouble solving this particular equation:
$y_{t+1}-2y_t=2^t$
Which brought me to realize that I don't even understand how to solve the general case of a difference equation $y_{t+1}-...
1
vote
2
answers
83
views
Show that, if $t_{3n}=x$, $t_{3n+1} = y$ and $t_{3n+2} = z$ for all values of $n$, then $p^3+q^3+3pq-1=0$
A sequence of numbers $t_0,t_1,t_2,...$ satisfies $$t_{n+2} = pt_{n+1} + qt_n, ~~~n\geq0$$
where $p$ and $q$ are real. Throughout this question, $x,y,z$ are non-zero real numbers.
Show that, if $t_{...
1
vote
1
answer
105
views
Writing the recurrence $O_t=-\frac1{T_w}\sum_{i=t-T_p}^{t-1}O_i-\frac1{T_i}\sum_{i=1}^{t-T_p-1}O_i+B_t$ in terms of its initial value
I want to write the following solely in terms of its initial value $O_1$
$$
O_t = - \frac{1}{T_w} \sum_{i=t-T_p}^{t-1} O_{i}
- \frac{1}{T_i} \sum_{i=1}^{t-T_p-1} O_i
+ B_t
$$
where
$T_w ...
- 335
0
votes
0
answers
60
views
Prove that sequence $b_n=a_n-\ln n,n\in\mathbb{N}$ is positive and decreasing if $a_0=1, a_{n+1}=a_n+e^{-a_n}, n\in\mathbb{N_0}$ [duplicate]
You have the following recurrence formula:
$$a_0=1,\quad a_{n+1}=a_n+e^{-a_n}, \quad n\in\mathbb{N_0}$$
Now define sequence:
$$b_n=a_n-\ln n,\quad n\in\mathbb{N}$$
Prove that:
$$0 \lt b_{n+1} \lt b_n, ...
- 15.4k
0
votes
0
answers
16
views
PDE with mass immigration and mass killing at zero
I am interested in the following PDE: Let $1> \alpha > \frac12$ and
$$\frac{d}{dt} f(x,t) = \frac{d}{dx} f(x,t) + \alpha (x+1)^{-\alpha -1} \left[1- \exp\left(-f(0,t)\right)\right], \mbox{ for }...
- 381
2
votes
2
answers
56
views
Question about a step in a derangement proof
I read a proof about derangement and I didn't understand this step:
$d_n - nd_{n-1} = -(d_{n-1}-(n-1)d_{n-2}) \implies d_n=nd_{n-1}+(-1)^n$
I see that we have $S_n = -S_{n-1}$ if $S$ is the stuff on ...
- 119
0
votes
1
answer
43
views
How do we solve the recurrence $T(n) = 2T(n/3) + n^{ \log_32 }\log\log n$?
How do we solve the recurrence $T(n) = 2T(n/3) + n^{ \log_32 }\log\log n$? Also, is it possible to solve this recurrence by the Master method?
- 31
0
votes
0
answers
33
views
Solving recurrences by substitution method
I was trying to understand divide and conquer algorithm from Introduction to Algorithms book by CLRS. I came across the part where they explained about solving recurrences using substitution as in ...
- 47
4
votes
1
answer
160
views
Why doesn’t $T(n) = 2T(\frac{n}{2}) + O(n^2)$ solve to $T(n) = \Theta(n^2)$?
I am told that the following statement is not true:
$T(n)=2 T (\frac{n}{2})+ O(n^2)$ then $T(n)=\Theta (n^2)$
My challenge is we can solve it by Master Theorem and reach to $T(n)=\Theta (n^2)$. What ...
- 139
0
votes
0
answers
21
views
Closed form for this recursion
The recurrence is
$$T(n)=n^\alpha T^a(n^\beta) + poly(\log n)$$
where $a\in\mathbb N$ and $0\leq\alpha,\beta\leq1$.
Is there a good bound on $T(n)$?
- 6,073
0
votes
0
answers
11
views
Solving linear interdependent system of recurrence relations
Suppose you had the following system of recurrences:
$$f_1(x) = \sum_{i=1}^k\sum_{j=1}^m c_{1ij} \cdot f_j(x-i)$$
$$f_2(x) = \sum_{i=1}^k\sum_{j=1}^m c_{2ij} \cdot f_j(x-i)$$
$$\vdots$$
$$f_m(x) = \...
- 235
1
vote
1
answer
56
views
Quadratic first order recurrence relation, is there a solution?
I am trying to find a solution for $a_n$, writing $a_n$ as a function of $n$,
according to the following recurrence relation:
$$a_n=3.9*a_{n-1}(1-a_{n-1}) ; a_0 = \frac{1}{2}$$.
I have tried ...
- 13
6
votes
1
answer
202
views
What is the minimum number of lego pieces required to complete a NxN maze and also what is total nummber of corresponding configurations?
There should be only one path between any two empty cells and any empty cell should be reachable from any other empty cell.
(in all of the following examples "x" denote lego position and &...
- 161