Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [recurrence-relations]

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

1
vote
0answers
37 views

How to solve this nonlinear recurrence relations?

I know how to solve linear homogeneous and non-homogeneous recurrence relations. But today I found this problem. $$F_1=1$$ $$F_2=7$$ $$F_3=13$$ $$F_n = 3F_{n-1} + k(F_{n-2}F_{n-3})+10$$ Where $k$ is ...
-1
votes
0answers
17 views

Probability in a recurrence equation

I have the following recurrence equation: $$g(n+1)=\dfrac{g(n)}{n+1}+h(n)$$ with $g(0)=1$ where $h(n)$ is a random normal distribuited variable:$$\mathcal{N(0,\sigma^2)}$$ The solution of this ...
0
votes
2answers
34 views

First to flip N heads wins?

Everyone knows the classic problem of A and B playing a game, with the first to flip heads winning the game. I understand that we can easily solve for the probability of A winning if she flips first, ...
-1
votes
0answers
13 views

Solving Recurrence Relation with initial condition [on hold]

How to solve below question? Any suggestion? Solve the recurrence s(n)=8s(n-1) + 10^(n-1) wiht initial condition s(1)=9. To see more clearly, please click the below link. https://hizliresim.com/...
0
votes
1answer
19 views

Complicated linear recursion relations

Is it possible to obtain a solution for $a_n$ for the following recursion relation? $$a_n = -\frac{1}{\epsilon}(n+1)a_{n+1}+R\left(\frac{n+2}{n+1}\right)a_{n+2}+\frac{R}{\epsilon}\left(\frac{(n+3)(n+...
0
votes
2answers
73 views

About $a_0=0, a_1=1$, $a_n=3 \frac{a_{n-1}}{n-1} + 2a_{n-2}$ for $n > 1$.

Let $\{a_n\}$ be defined by as the following: $a_0=0, a_1=1$ $$a_{n}=3\frac{a_{n-1}}{n-1}+2a_{n-2}, \forall n > 1$$ For example $a_2=3, a_3=\frac{13}{2}$. Is its generating function equal to $$\...
0
votes
0answers
89 views

Prove a Bound on Prime Factors of a Recursion

Let $g(n)$ be the numerators of the elements of the recursion $i(n)=i(n-1)+\frac{1}{i(n-1)}$ when they are expressed in simplest form, with $i(0)=1$. Let $p$ be the smallest prime factor of $g(m)$. ...
-1
votes
1answer
22 views

Linear recurrence solving for tighest possible big O bounds

I am dealing with the following linear recurrence: X0 = 1 X1 = 2 Xn = 3Xn-1 + 2Xn-2 I have proven that this has an upper bound of O(4n) However, I have been asked to come up with tighter bounds ...
2
votes
1answer
83 views

Will the series $\sum \frac{1}{n} - \frac{1}{n + o(n)}$ converge?

Recently I encountered a strengthened version of this question. Suppose $x_1 > 0$ and $x_{n + 1} = \log(1 + x_n)$. Prove that $$\lim_{n \rightarrow \infty}\frac{n(na_n - 2)}{\log n} = \frac{2}{3}$$ ...
1
vote
3answers
52 views

Solving recurrence $X_n = 4X_{n-1}+5$

$X_n=4X_{n-1}+5$ How come the solution of this recurrence is this? $X_n=\frac834^n+\frac53$ I also have that $X_0=1$. I am using telescoping method and I am trying to solve it like this: $X_n= 5 ...
0
votes
1answer
17 views

Solving an inhomogeneous linear recurrence relation $s_n = r (s_{n-1} +n \cdot B)$

I have been trying to solve the following linear recurrence relation, but I cannot seem to find a good particular solution: $$s_n = r (s_{n-1} +n \cdot B) $$ Where $B$ and $r$ are constant. We ...
-2
votes
0answers
27 views

Verifying correctness of a solution to a recurrence relation

I have been trying to solve a recurrence relation: $a_n = 6_{a_{n-1}} - 9_{a_{n-2}}$ As it is a 2nd order linear, homogeneous recurrence, I solved it using the substitution method to get the general ...
-4
votes
0answers
25 views

Limit of $(a_n)$ if $a_{n+1}=a_n-\frac{1}{n\left( n+1 \right) a_n}$, $a_1=1$ [on hold]

I want to know what: $$a_{n+1}=a_n-\frac{1}{n\left( n+1 \right) a_n} \qquad a_1=1 \qquad \lim_{n\rightarrow \infty}a_n=?$$
2
votes
2answers
37 views

Second order ODE problem with a series solution

I'm trying to obtain an analytical solution to the following ODE: $$-\epsilon x y+\left(\epsilon R-x-\epsilon x^2\right)y'+\left(R-x^2\right)y''=0$$ The only method that would make sense for me is ...
0
votes
0answers
26 views

What's wrong with this approach for finding expected number of throws before 2 identical throws?

I am trying to find the expected number of throws before a die shows up the same twice in a row. The definition of expected value is $$E(n) = \sum_nnP(n)$$ I have seen other answers elsewhere on how ...
1
vote
1answer
34 views

Words of length $n$ containing an odd number of zeros

Let $a_n$ be the number of words of length $n$ with letters from the alphabet $\{0, 1, 2, 3\}$ containing an odd number of zeros. I have already verified that this is given by the recurrence ...
4
votes
1answer
50 views

Proof by Induction of Sum of Squares of Fibonacci using Difference Opperators

Consider the sequence of Fibonacci numbers $\{F_n\}_{n\geq0}$ where $F_0=0,F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n\geq2$. It is proved that \begin{equation}\sum_{i=0}^nF_i^2=F_nF_{n+1}.\end{equation} ...
2
votes
1answer
47 views

In how many ways can a $ 2 \times n $ rectangle be tiled by $ 2 \times 1 $ or $ 1 \times 1 $ tiles?

This problem is from the book "Problem Solving Strategies" by Arthur Engel (Chapter 9, problem 64) and the solution given there is $\ a_0 = 1, \ a_1 = 2,\ a_2 = 7$ and the recurrence relation being $\ ...
1
vote
0answers
42 views

Using Newton's method to find $M$, the unique positive zero of $x^2+x-1$

Using Newton's method to find $M$, the unique positive zero of $x^2+x-1$. Obtain a recursive formula for the error term $e_n$ use it to prove $a_n \rightarrow M$ Recursive formula for $a_n:\quad$ $...
0
votes
1answer
17 views

Second order non-linear difference equation solver.

Is there an algorithm which I can use to find an approximate solution of the following second-order difference equation in order to run simulations of the solution : $\nu(1 - \beta) f(u_{n+1})-g(u_{...
1
vote
2answers
18 views

Reduce the 2nd order difference equation to 1st order

I have the following 2nd order difference equation. $\alpha X_{t+1}-X_{t+2} = \beta\alpha \left(\alpha X_{t}-X_{t+1}\right)$ Clearly, one solution is the process of $\alpha X_{t}=X_{t+1}$. However, ...
1
vote
1answer
42 views

Finding a recurrence relation

I need to find a recurrence relation or an exact formula to the sequence $$1,2,4,8,12,16,24,32,40,48,64,80,96,112,128,160,192,224,256,288,\ldots$$ Well, considering $a_0=1$, $a_1=2$ and $a_2=4$, the ...
2
votes
1answer
44 views

How to solve a recurrence relation with generating functions?

I don't really understand how to solve (with generating functions) for the recurrence relation of $$a_n = a_{n-1}+2(n-1)$$ with initial conditions of $a_1 = 2$ when $n \geq 2$ This is what I was ...
3
votes
1answer
57 views

recurrence relation for $\zeta(2n)$

I found this formula. Is it correct? For $n\in\Bbb N,\ n\geq2$, $$\zeta(2n)=\frac{2n\pi^{2n}}{\Gamma(2n+2)}+\sum_{k=0}^{n-2}(-1)^{k-n}\frac{\pi^{2n-2k-2}}{\Gamma(2n-2k)}\zeta(2k+2)$$ Here's my proof....
0
votes
0answers
9 views

General solution to inhomogeneous recurrence equation/ Analogon Greens function

I have a recursive equation of the form $u_{n} = u_{n-1} - a_{n}$ For finite $n\leq k$ with $u_{k+1}=u_{1}$Where $a_{n}$ is an inhomogenity that I do not presently know. The goal is find a ...
0
votes
1answer
37 views

Is $T(n,m) = 2\, T(n-1, (m-1)(1-1/n))$ polynomial in $n$ and $m$? [closed]

Can you prove or disprove that $T(n,m)=2T(n-1, (m-1)(1-\frac{1}{n}))$ grows polynomially in $n$ and $m$? If it matters, $T(1, j) = 1$ and $T(i, 1) = 1$. Usually $m$ is much greater than $n$, or at ...
0
votes
1answer
21 views

Ensuring homographic sequences are well-defined

Given a recursive homographic sequence $\begin{cases} a_0 \in \mathbb{R} \text{ given} \\ a_{n+1} = f(a_n) \end{cases}$ where $f$ is an homographic function ($x \longmapsto \dfrac{ax+b}{cx+d}$), how ...
0
votes
1answer
30 views

Recurrence relation for 2nCn

Does there exist an easy to compute (by hand) recurrence relation for the central column of pascals triangle? I'm trying to avoid factorials. A recurrence for {1, 2, 6, 20, 70, 252... } Thanks in ...
1
vote
1answer
19 views

Find the Recurrence relation for $q_n$ given the following condition:

Let $q_n$ denote the number of strings of length $n$ (formed from digits 0,1,2,3) which have even number of $2$'s. set up a recurrence relation for $q_n$.
1
vote
3answers
27 views

Solve the recurrence relation $f(n) = 4f(n/3)+5$ where $n=3^k, k=1,2,3…$ and $f(1)=5$

Solve the recurrence relation: $f(n) = 4f(n/3)+5$ where $n=3^k, k=1,2,3...$ and $f(1)=5$ I never seen a recurrence relation like this before. What would I need to use or do to solve this?
0
votes
1answer
13 views

Solving Recurrence Relation for the number of n-letter words

Find and solve the recurrence relation for the number of n-letter words composed from letters A, B, C and D such that no A comes after any B. What I learn in the class is, $$ A = a_{n-1} $$ $$ B = 3^{...
5
votes
2answers
47 views

Logistic map (discrete dynamical system) vs logistic differential equation

I have to roughly illustrate the logistic discrete dynamical system (as a model for population growth) to some non mathematics students. I'm not an analyst or an expert of dynamical systems. Looking ...
1
vote
0answers
49 views

Solve recurrence for strings that do not contain the substring 101

Let's say $A_n$ is the number of binary string that has length $n$ and does not contain the substring 101. Calculate $A_n$ for $n=1,2\cdots8.$ Find a recurrence relation for $A_n$. What does the ...
1
vote
3answers
101 views

The series $\frac{1}{2}+\frac{2}{5}+\frac{3}{11}+\frac{4}{23}+…$

Consider the expression $\frac{1}{2}+\frac{2}{5}+\frac{3}{11}+\frac{4}{23}+...$ Denote the numerator and the denominator of the $j^\text{th}$ term by $N_{j}$ and $D_{j}$, respectively. Then, $N_1=1$, ...
-2
votes
1answer
16 views

equation formula 1 unknown appear 2 time [closed]

I am a bit stuck here in my (excel) formula is it possible to solve this ? L2*(F2+x) =H2+(J2*x) x = ? thanks for your help Chris
1
vote
2answers
47 views

Solving a difference equation for coin toss sequence probabilities

I want to solve the following difference equation: $$b_n-b_{n-1} = \frac{1}{8}(1-b_{n-3})$$ I tried to solve it similar to the solution of Fibonacci sequence here, but when I try to assume the ...
0
votes
0answers
29 views

Finding a closed form for a Recurrence

Let $ f : \mathbb{N}^3 \to \mathbb{R} $, where $f$ is defined by the following recurrence, $$ f(x,y,z) = \frac{1}{x} \left[ \sum_{n=0}^{x-1} f(x,y-1,n) \cdot H[|z-n|-2] \right] $$ where $x>z$,...
3
votes
2answers
46 views

Symmetric continued fractions property where $q^2\equiv(-1)^n$ mod $p$

Let $[a_0,a_1,a_2,\ldots,a_n,a_n,\ldots,a_2,a_1,a_0]=:\frac{p}{q}\in\mathbb{Q}$ be a symmetric continued fraction. This sequence of $a_i$'s consists of finitely many elements because $\frac{p}{q}$ is ...
-1
votes
0answers
20 views

Evaluate the time complexity of following recurrence relation: T(x,y) = Θ(x+y) + T(x/2,y/2) T(x,c) = Θ(x) for c<=2 T(c,x) = Θ(y) for c<=2

This question has been asked repeatedly in my mid and final semester exams and I haven't found any solution of it online or in any books. ...
2
votes
1answer
36 views

Polynomial representation: Marsden's Identity.

Marsden's Identity states that: For every $\tau$ in $\mathbb{R }$: $(\cdot -\tau)^{k-1}=\sum_j\Psi_{j,k}B_{j,k,t}$ with: $\Psi_{j,k}=(t_j-\tau)\times...\times(t_{j+k-1}-\tau)$ Following de Boor'...
0
votes
0answers
26 views

How to get this closed form for such recurrence?

We have for $k>0$, $n>0$, $m\geqslant0$ $$p_k(n,m)=k(n-1)!\sum\limits_{s=0}^{n-1}\frac{p_{k-1}(s+1,m+1)+p_{k-1}(m+1,s)}{s!}$$ also $$p_0(n,m)=\begin{cases} (n-1)!,&\text{$n>0, m=0$}\\ 0,&...
2
votes
2answers
81 views

Explicit formula for $a_0=1$, $a_{n+1}=a_n^2+1$

Is there an explicit formula in elementary function for the sequence $a_n$ where $a_0=1$, $a_{n+1}=a_n^2+1$? How does one prove or disprove such claims? Edit: I think my question may be formulated in ...
0
votes
0answers
17 views

What is the recurrence relation for the following situation?

Let $a_n$ be the number of non negative integer solutions to $x+y+z=n$ where $x$ is even. For $n=0$: $a_0= 1$ ($0+0+0=0$) For $n=1$: $a_1 = 2$ ($0+1+0=1$ or $0+0+1=1$) For $n=2$: $a_2 = 4$ ($0+2+0=...
0
votes
0answers
8 views

Representing rectangular function using divided differences.

I was reading the chapter 9 of A practical guide to splines (de Boor, C.) were the autor defines a B-spline of order 1, basically a rectangular function i.e. a function taking value $1$ if the ...
0
votes
0answers
14 views

Coefficients from sequence of ceil divisions

I wanted to know if there exists a systematic elegant “closed form” formula for calculating numbers ${{s}_{i,j,\left\{ 1,2 \right\}}}(n) \in {{\mathbb{N}}^{*}},$ and also positive rational numbers $...
0
votes
0answers
31 views

Iterated map $x_{n+1} = rx_n(1-x_n^2)$

In my differential equations homework, which is mostly extremely easy, there is one question which I cannot grasp. For easier reference, here is the full question as I have been given it: Consider ...
0
votes
1answer
34 views

Recurrence relation with two variables.$(n+h_{n+1}) f(n+1,m) + f(n-1,m) + h_n f(n,m-1) + (m+1) f(n,m+1)=(1+m+(n-1)+ 2h_n) f(n,m) $

I have the following recurrence relation at hand: ( $n,m$ are integers) $$(n+h_{n+1}) f(n+1,m) + f(n-1,m) + h_n f(n,m-1) + (m+1) f(n,m+1)=(1+m+(n-1)+ 2h_n) f(n,m) $$ where $h_{n}= \frac 1{n+1}$. We ...
9
votes
4answers
85 views

Recurrence and Fibonacci: $a_{n+1}=\frac {1+a_n}{2+a_n}$

For the recurrence relation $$a_{n+1}=\frac {1+a_n}{2+a_n}$$ where $a_1=1$, the solution is $a_n=\frac {F_{2n}}{F_{2n+1}}$, where $F_n$ is the $n$-th Fibonacci number, according to the convention ...
2
votes
1answer
61 views

Recurrence Relation with multiple variables

Consider the following recurrence relation with two variables and similar bounding conditions: \begin{align*} x_{1,t} &= \frac{1}{2-\frac{2}{n}} x_{1,t-1} + \frac{1}{2} x_{2,t-1} \\ x_{i,...
0
votes
1answer
31 views

Recurrence question on Binary strings

Let $B_n$ be the set of binary strings of length $n$ such that: Every even length block of $0's$ is followed exactly by $1$, and Every odd length block of $0's$ is followed exactly by $11$ (exactly ...