Questions tagged [recurrence-relations]

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

Filter by
Sorted by
Tagged with
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^{...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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{\...
user avatar
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 ...
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
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}$ ...
user avatar
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: ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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)$.
user avatar
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? ...
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
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 ...
user avatar
  • 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 ...
user avatar
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 ...
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
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}\...
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
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)$ ...
user avatar
  • 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 ...
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
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 ...
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
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 ...
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
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 ...
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
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)...
user avatar
  • 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 ...
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
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_{...
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
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, ...
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
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 ...
user avatar
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)$?
user avatar
  • 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) = \...
user avatar
  • 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 ...
user avatar
  • 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 &...
user avatar

1
2 3 4 5
165