Questions tagged [recurrence-relations]

Questions regarding functions defined recursively, such as the Fibonacci sequence.

Filter by
Sorted by
Tagged with
0 votes
0 answers
18 views

Difference between self-similarity and recurrence

For me intuitively self-similarity and recurrence are not exactly the same, however a lot of self-similar objects like fractals are defined via a recurrent equation. Is there a self-similar object ...
user avatar
-1 votes
0 answers
28 views

Solve the recurrence relation : T(n) = 2T(2n/3) + n^2 using iteration method [closed]

Please help me solve the recurrence relation using iteration method: T(n) = 2T(2n/3) + n^2.
user avatar
0 votes
0 answers
37 views

Getting rid of asymptotic notation in Recurrence Relations

Let's suppose I want to resolve the following Recurrence Relation: $$ T(n) = \begin{cases} 1 & n=1 \\ T(n-1) + \Theta(n) & \text{otherwise} \end{cases} $$ I want to prove that ...
user avatar
5 votes
2 answers
87 views

Using a generating function to solve a recursion

I know that the generating function for the sum of Fibonacci numbers with even index is \begin{align} F_e(z) &= \sum_{n \ge 0} F_{2 n} z^n \\ &= \frac{F(z^{1/2}) + F(- z^{1/2})}{2} \\ &...
user avatar
2 votes
0 answers
37 views

Help with finding analytical formula of a recurrence relation using iteration.

$$\displaystyle{\displaylines{g(0)=1}}$$ $$\displaystyle{\displaylines{g(n)=3^n-g(n-1)+1}}$$ Find the analytical definition of the recurrence relation using iteration $$\displaystyle{\displaylines{g_{...
user avatar
2 votes
2 answers
61 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^{...
user avatar
4 votes
2 answers
97 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 ...
user avatar
  • 475
1 vote
0 answers
62 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 ...
user avatar
0 votes
3 answers
56 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 ...
user avatar
2 votes
0 answers
54 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{\...
user avatar
1 vote
1 answer
56 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 ...
user avatar
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}=...
user avatar
  • 739
1 vote
0 answers
20 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}$ ...
user avatar
6 votes
1 answer
52 views

Fibonacci sequences within the Fibonacci sequence recurrence

I'm trying to perform a runtime analysis of the following simple recursive Fibonacci number algorithm: ...
user avatar
  • 75
3 votes
2 answers
138 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 ...
user avatar
  • 863
0 votes
0 answers
19 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 ...
user avatar
3 votes
1 answer
113 views

Find the number of ways of tiling a $3\times n$ rectangular grid with $2\times 1$ dominoes

I'm trying to find the number of ways $(a_n)$ of tiling a $3\times n$ rectangular grid with $2\times 1$ dominoes, where rotation is allowed. I want to find a recurrence relation for $(a_n)$ and an ...
user avatar
1 vote
0 answers
62 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? ...
user avatar
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^...
user avatar
  • 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}...
user avatar
2 votes
1 answer
60 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 ...
user avatar
  • 492
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 ...
user avatar
1 vote
1 answer
284 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 ...
user avatar
  • 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?
user avatar
  • 1
4 votes
1 answer
91 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}\...
user avatar
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 ...
user avatar
  • 21
1 vote
0 answers
16 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)$ ...
user avatar
  • 417
1 vote
2 answers
57 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 ...
user avatar
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: ...
user avatar
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{...
user avatar
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 ...
user avatar
  • 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^{...
user avatar
4 votes
0 answers
160 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 ...
user avatar
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 ...
user avatar
  • 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.$
user avatar
-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 ...
user avatar
  • 21
0 votes
1 answer
66 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 ...
user avatar
  • 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]...
user avatar
  • 133
0 votes
4 answers
91 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 ...
user avatar
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 ...
user avatar
4 votes
1 answer
81 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)...
user avatar
  • 641
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 ...
user avatar
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}-...
user avatar
2 votes
2 answers
85 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_{...
user avatar
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 ...
user avatar
  • 335
0 votes
0 answers
61 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, ...
user avatar
  • 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 }...
user avatar
  • 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 ...
user avatar
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?
user avatar
  • 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 ...
user avatar

1
2 3 4 5
165