Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [recurrence-relations]

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

A recurrence relation is an equation that recursively defines a sequence or multidimensional array of values: once one or more initial terms are given, each further term of the sequence or array is defined as a function of the preceding terms.

Simple examples include the geometric sequence $a_{n}=r a_{n-1}$, which has the closed-form $a_{n}=r^n a_0$, the aforementioned Fibonacci sequence with initial conditions $f_0=0,f_1=1$ and recurrence $f_{n+2}=f_{n+1}+f_n$, and series: the sequence $S_n =\sum_{k=1}^{n} a_k$ can be written as $S_n= S_{n-1}+a_n$.

The term order is often used to describe the number of prior terms used to calculate the next one; for instance, the Fibonacci sequence is of order 2.

See the Wikipedia page for more information.

8985 questions
3
votes
1 answer

Solving the recurrence $t(n)=t(n/2)+n^2$ using the iteration method

Any hints on how to solve $t(n) = t\left(\frac n2\right) + n^2$ with the iteration method? What I've got so far: $$t(n)=n^2+t\left(\frac n2\right)$$ $$t(n)=n^2+\left(\frac n2\right)^2+t\left(\frac n4\right)$$ $$t(n)=n^2+\left(\frac…
Chafic
  • 133
3
votes
1 answer

Proof for recursively defined sets

Language $L\subset \{a,b\}^*$ is such that: $\epsilon \in L$ $a \in L$ For any $x\in L$, $xb\in L$ and $xba\in L$ Nothing else in $L$. Im just learning recursive sets, but with that definition am I correct that: $\epsilon \in L$ so: $b\in L$ and…
Deniz Cetinalp
  • 829
3
votes
3 answers

Finding closed form of $u_{n+1} =2u_n - n^2$

Find a closed form formula for $u_n$ where $u_{n+1} =2u_n - n^2$ and $u_0=a$ I'm not totally sure how closed form expressions are derived of a given sequence. I tried generating functions which goes like this: $\begin{aligned} \sum_{n=0}^{\infty}…
zaemon_23
  • 465
3
votes
1 answer

How to find general term of ${a_{n}}$?

Suppose $a_{1}=a_{2}=\frac{1}{3}$, for $n = 3, 4, 5, ...$ , we have $$a_{n}=\frac{a_{n-1}^2(1−2a_{n-2})}{2a_{n-1}^2 − 4a_{n-2}a_{n-1}^2+a_{n-2}}$$ (1) Prove that $\frac{1}{a_{n}} −2$ are square numbers (2) Find out the general term formula of…
Anirudh Kumar
  • 31
3
votes
3 answers

Solving linear non homogeneous recurrence relations

$a_{n+2}+3 a_{n+1}+2 a_n=5 n+3$, where $a_0=1, a_1=4$. I am trying to solve the homogeneous part first, I have the roots as r = -1 and r = -2, by factorising the characteristic equation which I have as $r^2 + 3r + 2 = 0$. So I have the homogenous…
user1176177
  • 39
3
votes
2 answers

Solving recurrence relation: What am I missing in my working?

Apologies for the uninformative title, this is a relatively specific question so it was hard to title. I'm solving the following recurrence relation: $a_{n} + a_{n-1} - 6a_{n-2} = 0$ With initial conditions $a_{0} = 3$ and $a_{1} = 1$ And I…
Arvin
  • 1,733
3
votes
3 answers

What is the general solution of the linear difference equation $y_{n+3}-4y_{n+2}+5y_{n+1}-2y_n=2^n$

What is the general solution to the linear difference equation: $$y_{n+3}-4y_{n+2}+5y_{n+1}-2y_n=2^n$$ I followed the instructions given in this video. And I got the following for the homogeneous part I got: $$y_n^c = A+Bn+C2^n$$ for the particular…
Yahya Fati
  • 83
3
votes
1 answer

How do you find the general solution of the recurrence relation: $a_n=(a_{n-1})^2+(a_{n-2})^2,a_1=1, a_2=2$

How do I find the general solution of this recurrence relation? $$a_n=(a_{n-1})^2+(a_{n-2})^2,a_1=1, a_2=2$$ I didn't find any general solution for this recurrence relation.
user1010242
3
votes
2 answers

Solving Recurrence Relation With Replacement

I have trouble solving this question: T(n) = $4\sqrt{n}$ T($\sqrt{n}$) + $2n^{2}$ I write n = $2^{m}$ and than: T($2^{m}$) = $4*2^{m/2}$ T($2^{m/2}$) + $2*2^{2m}$ and than: S($m$) = $4*2^{m/2}$ S($m/2$) + $2*2^{2m}$ can anybody give me a hint
Barry
  • 33
3
votes
1 answer

Asymptotics of the solution of the following recurrence relation

$f(k)={k \choose k-1} f(k-1) + { k \choose k-2} f(k-2) + .... {k \choose 3} f(3)$ $f(3) = 1$ $k \ge 3$ Even good upper and lower bounds will help me as I am trying to find how this function grows asymptotically.
AnkurVijay
  • 647
3
votes
0 answers

First-order non-homogeneous recurrence relations with variable coefficients

Looking at the method for solving recurrence relations given on Wikipedia here, I found myself confused by some aspects of the method. To save people tabbing backwards and forwards, here is what it says: For [a] general first-order non-homogeneous…
Richard Burke-Ward
  • 441
3
votes
2 answers

Second-order recurrence relation over another variable

Given the recurrence relation $$ \pi_0 = 0$$ $$ \pi_1 = 1$$ $$ \pi_{i+1} = \frac { (2i + 1) m \pi_i - (i + 1) \pi_{i - 1} } {i} $$ I tried to work through a simplistic tutorial and all I was able to find out is that $ \pi_i $ is a…
Reinderien
  • 192
3
votes
2 answers

Recurrence relation on $a_n$

Given the recurrence relation$$ a_{n}=\sum_{t=0}^{n-1}\left(\begin{array}{l} n \\ t \end{array}\right)(-1)^{n-t-1} 2^{t(n-t)} a_{t}, \quad a_{0}=1 $$ with $a_0=1$, I tried to evaluate $a_3$, and I got it equal to $25$, but the book shows it equal to…
user948104
3
votes
1 answer

Asymptotics of a Recursively defined sequence

Suppose we define the sequence $a_n$ recursively by $p_1=1/2, a_1=2$, $p_{n+1}=p_n-\frac{{p_n}^2}{a_np_n+1}, a_{n+1}=a_n+\frac{1}{p_n}$. How does $(a_n)$ behave for large $n$? For instance, what is a function $f(n)$ satisfying $\lim\limits_{n \to…
Alexander
  • 4,292
3
votes
2 answers

Recurrence relation $a_{n} = a_{n-1}+a_{n-2}+n$

How to solve this recurrence relation? $a_{n} = a_{n-1}+a_{n-2}+n,a_{1}=a_{0}=1$ What I have tried: $r^2 = r + 1 \rightarrow r = \frac{1+\sqrt{5}}{2},\frac{1-\sqrt{5}}{2}$ non-homogeneous part: $$ \begin{split} a_{n} &= cn+b \implies c(n)+b =…
gigili
  • 41
1 2 3
…
96 97