Questions tagged [recurrence-relations]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
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....
0
votes
1answer
32 views

Solving a linear difference equation

I have to find a general solution for the difference equation given as $$ y_{n+1} = y_n + h(1 - y_n) $$ with initial condition: $ y_0 = 0$ and $h$ constant. The solution should be $$ y_n = 1 - (1-h)^n$...
0
votes
1answer
24 views

Counting flips for a binary counter

$$T(n)=\sum_{i=0}^{k-1}\left\lfloor\frac n{2^i}\right\rfloor<n\sum_{i=0}^\infty\frac1{2^i}=2n$$ $$\implies T(n)=O(n)$$ For context: This calculates the number of flips for a binary counter. I ...
1
vote
2answers
36 views

Limit of a definite nonelementary integral

I have to prove that $\lim_{n\to \infty}\int_0^{1/2}x^ne^{2x-1}\;dx=0$ without calculating the primitive. I have already proved that it can be defined as a recurrence sequence: $$y_1=\frac{1}{4e},\...
4
votes
1answer
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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}$$?
1
vote
4answers
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 ...
3
votes
0answers
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, "...
0
votes
0answers
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 ...
-3
votes
0answers
29 views

How to prove that the Lucas Numbers satisfy these three properties [closed]

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 $...
1
vote
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_n$ such that the equation requires no recursion (allowing me ...
-1
votes
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.
0
votes
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+...
0
votes
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 functions $f$ 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 ...
1
vote
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}\...
0
votes
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}
1
vote
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 $...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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,...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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. ...
-1
votes
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 ...
0
votes
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:...
0
votes
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} =\...
0
votes
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 ...
0
votes
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' \...
1
vote
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 ...
0
votes
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_{...
1
vote
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 ...
5
votes
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}{...
1
vote
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 ...
1
vote
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 ...
0
votes
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} ...
1
vote
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'(...
0
votes
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 ...
4
votes
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 ...
2
votes
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 $$...
0
votes
0answers
12 views

Solving a recurrence relation where the indices are far off

I am trying to find a closed form expression for $x_j$ which 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} ...
1
vote
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?
-1
votes
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$ ...
0
votes
2answers
36 views

Inequality for Binomial distribution function

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 ...
0
votes
1answer
27 views

Solve recurrence relation without initial conditions

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 ...

1
2 3 4 5
155