# Questions tagged [recurrence-relations]

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

7,733 questions
Filter by
Sorted by
Tagged with
35 views

### Making a sequence non-recursive

I have a sequence that produces outputs: 1, 4, 13, 40, 121... I know that for the nth term, the output would be $3^0 + 3^1 + \ldots + 3^n$ But I don't know how to write this without it being recursive....
32 views

42 views

### How to solve $a_{n} = \frac{2a_{n-1}^2}{a_{n-2}}$, where $a_0 = 1$ and $a_1 = 2$

I'm trying to solve this reccurence relation as a part of the "linear recurrence relations with constant coefficients" chapter, with the hint that the next step is using logarithms. The ...
25 views

### Upper bound on non-linear recurrence.

As part of my work for a course, to prove the convergence of some numerical scheme I have to bound some quantity $b_n$ which is defined recursively. Suppose that I have the following inequality for ...
32 views

### Progression problem : $U_{n+2}=U_n-(-1)^n?$

Could you help me with this question ? $(U_n)$ is a sequence defined on $\mathbb N$ and : $$U_0 = 0 , U_n = U_{n-1} + n (-1)^{n-1},\mathrm{for \space every \space n} \in \mathbb N^*.$$ Q: Prove that ...
25 views

### Finding a recurrence relation for $2\times N$ tiles with red and blue tiles and utmost 2 similar colored neighbors

this question has 1 tricky aspect I don't know how to address. Basically We are asked to color $2\times N$ tiles with red or blue 1x1 tiles. However, a tile can only have up to 1 similar colored tile ...
30 views

### Lag operator computations

given $$h_t=\alpha_0+(1-\beta_1)\epsilon^2_{t-1}+\beta_1Lh_t$$ where $$Lh_t=h_{t-1}$$ how can I obtain $$h_t=\alpha_0/(1-\beta_1)+(1-\beta_1)\sum_{1=0}^\inf\beta_1^i\epsilon^2_{t-1-i}$$?
53 views

### why does the recurrence $a_{n+1} = a_n - 2 a_n^{3/2}$ look like $1/n^2$ for large n?

Consider the recurrence $a_{n+1} = a_n - 2 a_n^{3/2}$, with initial condition $a_0 \in (0, \frac{1}{4})$. I know that $a_n \approx 1/n^2$ for large $n$, but I don't understand why that is true. I'd ...
29 views

### About the stability of cycles for the logistic map $x_{n+1}=rx_n(1-x_n)$

Please indicate a reference (if there exists any) proving that when a cycle appears (i.e. for the minimal value of the logistic parameter $r$ for which a $k$-cycle exists) we also have, "...
17 views

### Solving a recurrence relation and a similar partial differential equation

The original question is: You are taking out candies one by one from a jar that has 10 red candies, 20 blue candies, and 30 green candies in it. What is the probability that there are at least 1 blue ...
29 views

Prove these three properties: $L_1+L_3+L_5+\cdots+L_{2n-1} = L_{2n-2}-2$, $n\geq1$ $L_1^2 +L_2^2 +L_3^2+\cdots+L_n^2=L_nL_{n+1}-2$, $n\geq1$ $L_{n+1}^2 - L_n^2 = L_{n-1}L_{n+2}$, $n\geq2$ where $... 0answers 22 views ### Help needed defining closed form of recursive formula The recursive formula is$a_n$= 1.28($a_{n-1}$) - (.28$a_{n-1}$)^2 I would like to transform this into one side of the equation being$a_nsuch that the equation requires no recursion (allowing me ... 2answers 41 views ### How can we solve this recurrence relation? My friends and I are having trouble resolving this... T1 = 1, T(n) = 2T(n/2) + 1, n > 1. I would appreciate if anyone could help us solve this, and explain how to. 0answers 12 views ### Solution to Stochastic piecewise linear difference equation I am studying this system of piecewise linear stochastic equations: \begin{align*} y_t &= \mathbf{1}_{\left\{y_t\leq \underline{y}\right\}}\left(a_0 y_t + \gamma\right)+a_1\mathbf{E}_ty_{t+1}+bx_t+... 1answer 36 views ### Is there a function where the average over a set is equal to the value for that set's average? Using mathematical notation, my question is if there are any functionsf$where$\frac{1}{n} \sum_{i=1}^n f(x_i)=f\left(\frac{1}{n} \sum_{i=1}^n x_i\right)$for all sets$x=[x_1,x_2,...,x_n]? From ... 0answers 41 views ### Taking the derivative under the integral I'm studying a text on the spherical Bessel functions and I've come across the following integral: $$(-z)^l\left(\frac{1}{z}\frac{d}{dz}\right)^l\frac{1}{2}\int_{-1}^{1} e^{izx} \,dx = \frac{z^l}{2}\... 1answer 54 views ### Generating function of the recurrence relation [closed] How can I specify the generating function of the following recurrence relation? \begin{equation} a_{n} = 4a_{n-1} - 3a_{n-2} \end{equation} 0answers 25 views ### Recurrence relation similar to weighted Pascal's triangle Consider \mathbb C \langle x, y \rangle / \langle x y - \lambda y x - \mu \rangle for some constants \lambda, \mu \in \mathbb C. I am trying to obtain a closed formula for x^m y^n, for general ... 0answers 32 views ### Solving a partial differential equation with boundary condtions and a similar recurrence relation [closed] The original question is: You are taking out candies one by one from a jar that has 10 red candies, 20 blue candies, and 30 green candies in it. What is the probability that there are at least 1 blue ... 1answer 58 views ### T(n) = nT(n-1) + n^2 analysis I did a good amount of research on the above recurrence relation. It is the recurrence relation for N-Queens problem using backtracking. In this link here is a proof of how it reduces to O(n^2)\times ... 0answers 34 views ### Prove by induction a relationship between sequences I'm grappling with this problem: A sequence is defined as b_n = b_{n-1} + b_{n-2} where b_1 = 2, b_2 = 1 for all n≥3. Prove (using mathematical induction) that the relationship between the two ... 1answer 17 views ### Recurrence relation to differential equation It seems clear that one method to solve recurrence relation is the transformation to a differential equation as follows$$a_{n+k}\to f^{(k)}$$I'm trying to modelize this easy problem: "Given a ... 1answer 35 views ### How to find the general solution to the difference equation [closed] I have the below difference equation, which I need to find a general solution for: a_{n+1} = a_n^2 − 10,\ a_0 = 4 I've done simpler problems which I know how to reach a general solution for. However,... 0answers 22 views ### How to solve the recurrence relation of Chebyshev polynomials The Chebyshev polynomials of the first kind are obtained from the recurrence relation$$\begin{aligned}T_{0}(x)&=1\\T_{1}(x)&=x\\T_{n+1}(x)&=2x\,T_{n}(x)-T_{n-1}(x)~.\end{aligned}$$Is it ... 1answer 19 views ### Closed form for this power series looking like an hypergeometric? I would like to "resum" the following expression:$$\sum_{k=0}^a \frac{(-a)_k (-b)_k}{(c)_k} x^k\,, \tag{1}$$with a, b, c positive even numbers and x > 0 real. Is there a known ... 2answers 35 views ### Regarding this difference equation Consider the inhomogeneous difference equation$$u_n=u_{n-1}+u_{n-2}+\dots+u_1+1$$where we have the initial condition u_1=1 Clearly u_n=2^{n-1} is a solution. However, plugging a solution of the ... 1answer 31 views ### Understanding what a particular solution of a recurrence relation is? What does the particular solution of a linear nonhomogeneous recurrence relation actually mean? To me it looks that the particular solution looks exactly like the original given recurrence relation. ... 1answer 38 views ### Give a recurrence relation for the population of fish after n months. [closed] A lake initially contains 1000 fish. Suppose that in the absence of predators or other causes of removal, the fish population increases by 10% each month. However, factoring in all causes, 80 fish are ... 1answer 21 views ### Properties of a relation defined recursively We have the following recursively defined relation on the integers:$$ (0,0) \in R \\ (a,b) \in R \implies (a+2, b+3) \in R \text{ and } (a+3, b+2) \in R $$The following are the questions of interest:... 0answers 34 views ### Number of Ways of Writing r as a Sum of Distinct Positive Integers, all atleast s: c_{r,s} =\sum_{i=1}^{r-s} c_{i,r+1-i} +1 For r,s \ge 1, let c_{r,s} be the number of ways of writing r as a sum of distinct positive integers, all greater than or equal to s. Then I believe the following recurrence holds:$$c_{r,s} =\... 1answer 45 views ### How to prove the sum of this series I have the sum of this series\sum_{n=3,5,7,...}^{\infty}\left(\frac{1}{(n^2-1)^2}\right)$with numerical values, I can see that the sum reaches$0.0.0181168(see below), but I have a hard time ... 0answers 31 views ### Solving the Reed-Frost binomial chain model I am interested in finding an analytic solution for the Reed-Frost model, defined as a bivariate Markov chain with transition probability $$P\big(n, s, t+1 \mid n', s', t \big) = \delta_{s, s'-n} {s' \... 1answer 29 views ### recurrence relation for the number of sequences of digits I want to find a recurrence relation for the number of sequences of digits (1, 2, 3) with a sum of digits equal to n which don’t contain sub-sequnce 123\ldots. I tried out the first seven cases ... 1answer 97 views ### How do I write equations for this Fibonacci sequence The Fibonacci sequence can be defined using the recurrence relations: F_0 = 0, F_1=1, F_{n} = F_{n-1} + F_{n-2}~~ for n \in \mathbb{N} \colon n \geq 2~~~ (1) F_0 = 0, F_1=1, F_{m+2} = F_m + F_{... 1answer 28 views ### How to find the particular solution of homogenous recurrence relation with polynomial-exponential term? Non Homogenous Recurrence Relation:$$a_n=5a_{n-1}-6a_{n-2}+(13+6n)5^{n-2}$$Most problems I've solved are of the form a_n+a_{n-1}+a_{n-2}+F(N) I have never seen anything of this form its super ... 0answers 39 views ### Verify guess to solution of a nested recurrence relation I have been trying to find the sequence a_0,a_1,a_2,\dots that solves the following nested recurrence relation:$$ \begin{aligned} (1) &&c_0 &=a_0^m\\ (2) &&c_k &=\frac{1}{... 2answers 59 views ### Finding the Explicit Formula of a Recursion Using Generating Functions I have to fid the explicit formula of the following recursion: $$a_0 = 1, a_n = \sum_{i=0}^{n-1} (i+1)a_i.$$ The summation reminds me a lot of derivatives and I feel like I am going to have to take a ... 1answer 26 views ### Solving for the minimal number of moves required in the Tower of Hanoi According to ProofWiki, Thus we arrive at our recurrence rule:T_{n} = 2T_{n - 1} + 1$. The solution when solving this recurrence relation in that page is a proof by induction. Can someone verify ... 3answers 66 views ### How do i prove a recursion with$ a_n = 3 \cdot 2^{(n-1)} + 2(-1)^n $so that for all$ n \in \mathbb{N} $it is true? I am pretty new when it comes to recursion together with induction. I would appreciate if somebody could show me how to approach this kind of problem: $$a_n = \begin{cases} ... 1answer 39 views ### Prove the integral \int_{0}^{1}\frac{x^{2n}}{x^{2}+a^{2}}dx has the recurrence relation K_{n}+a^{2}K_{n-1}=\frac{1}{2n-1} Prove the integral$$\int_{0}^{1}\frac{x^{2n}}{x^{2}+a^{2}}dx$$Has the following recurrence relation$$K_{n}+a^{2}K_{n-1}=\frac{1}{2n-1}\tag{$n \ge 1$}$$I used integration by parts, let x^{2n}=f'(... 2answers 35 views ### Number of regions formed by n great circles on the sphere Find the recurrence relation satisfied by R_n, where R_n is the number of regions into which the surface of a sphere is divided by n great circles (which are the intersections of the sphere and ... 1answer 111 views ### What does [n=1] mean? Studying recurrence relations I stumbled upon this expression in a solution to the problem of finding a closed formula to this: a_n = 5a_{n-1} - 6a_{n-2}; a_0 = 0, a_1 = 1 To start the solution, the ... 5answers 383 views ### An integral and a mysterious recursive sequence Today I tried to solve the integral$$I_n= \int_0^{\frac{\pi}{2}} \frac{\mathrm{dt}}{(a \cos^2(t)+ b \sin^2(t))^n} \quad \quad \quad \quad a,b > 0$$After some dirty calculations, I obtained that$$... 0answers 12 views ### Solving a recurrence relation where the indices are far off I am trying to find a closed form expression for$x_jwhich satisfies the recurrence relation: \begin{align} x_j&=1+\frac{1}{2}x_{2j\mod n}+\frac{1}{4}x_{2(j-1)\mod n}+\frac{1}{4}x_{2(j+1)\mod n} ... 1answer 62 views ### Solve the Recurrence :T(n) = 2T(\frac{n}{2}) + n + \log n$I have tried Akra-Bazzi, which gave me O(n logn), but I am unsure if that can be applied here, or even if it can be applied, if my final answer is correct or not. How can I try solving this? 1answer 32 views ### Solving recurrence$T(n) = T(\lfloor{\frac{n}{2}}\rfloor) + T(\lceil{\frac{n}{2}}\rceil) + cn$is$O(n\text{log}(n)) [duplicate]

So I need to prove that T(n) is $O(n\text{log}(n))$, considering $c>0$ is a constant and using substitution method What I've tried so far: We need to prove that $T(n) \leq dn\text{log}(n), d\geq0$ ...
Suppose $F(y;n,p)$ is the binomial distribution function, i.e. the probability that there are $y$ or fewer successes out of $n$ independent Bernoulli trials each with success probability $p$. Is it ...
Solve the following lineal recurrence relation with constant coefficients: $$x_{t+1}=2x_t+2^{t+1}+1$$ I have an idea about how to solve this, using: $$x_t=x_{t}^h+x_{t}^p$$ where $x_{t}^h$ is the ...