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

Difference of Consecutive Terms in a Recurrence Sequence

I have a question that seems simple, but it has caused me some trouble when trying to prove it. Given a recurrence relation with non-negative integer coefficients, $$ G_{n+1} = c_1G_n + c_2G_{n-1} + \cdots + c_sG_{n+1-s} + c_{s+1}G_{n-s} + \cdots +…
user723034
0
votes
1 answer

Asymptotics of Recursive Bound

Suppose that we knew that for $n>N$, we have $$F(n) \le F(n-g(n)) +h(n)$$ for some well behaved functions $g,h$. (for a concrete example, let’s say $N=1,g(n)=n^\alpha, h(n)=n^\beta$ where $\alpha,\beta \in (0,1))$) I was wondering then how we can…
Zach Hunter
  • 1,828
0
votes
1 answer

$A_k\leq C [2^{2k}A_{k-1}]^{\mu+1}, \ k=0,1,...$ implies $A_k\to 0$?

Consider the nonlinear recursive relation $$A_k\leq C [2^{2k}A_{k-1}]^{\mu+1}, \ k=0,1,...$$ where $C,A_k,\mu>0$. How can one show that if $A_0$ is small, then $A_k\to 0$? Thanks.
Tomás
  • 22,559
0
votes
1 answer

Solving recurrence relation with 2 variables

If I have a recurrence relation like $$T(n,k)=\frac{T(n-1,k)+T(n,k-1)}{2}$$ with initial values $\forall n \quad T(n,0)=T_0$ and $\forall k \quad T(0,k)=0$. How can I solve it? By the way this came up when I was solving a physics problem
spitfire
  • 13
0
votes
1 answer

Difference equation system solution

A system is written $$ S_n = f^nS_0 \\ P_n = p(f-1)f^{n-1}S_0 $$ for $n\leq T$. For $n\geq T$: $$ S_{n+1} = f(S_n-P_n ) \\ P_{n+1} = p(f-1)(S_n-P_n ) $$ The constants $S_0,f,p$ are all positive real (and $p<1$). I would like to obtain a general…
Mobeus Zoom
  • 329
0
votes
3 answers

How to solve recurrence relations - expected value

I'm solving a question where the recurrence relation I created is as follows: $$\begin{cases}E_0=0\\E_1=2\\E_n = 2E_{n-1} + 2&\text{for }n>1\end{cases}$$ How can I create a closed form solution for this?
Eric Aldrin
  • 625
0
votes
2 answers

Problem with non-homogeneous recurrence relation

I am having trouble solving this recurrence relation: $$a_{n+1}=a_n+3n^2-2 \quad , \quad a_0=3$$ The solution will be $a_n=a_n^h+a_n^p$ where $a_n^h$ is the solution of the homogeneous problem and $a_n^p$ is a particular solution of the…
kubo
  • 1,918
0
votes
0 answers

Recursive relation of putting $2^k -1$ fixed order elements in a stack

What is the recursive relation showing the possible ways of putting n = $2^k -1$ elements in a stack where always the ith element is in ith place(the element number one is always in first place in the stack). we define the amount of element i,…
MMM
  • 47
0
votes
2 answers

Inhomogeneous Difference Equation $p_{n}+\frac{1}{4}p_{n-1}=\frac{3}{4}$ with $p_0=0, p_1=3/4$

I'm trying to solve the above equation, and this is where I've got to so far: Consider homogeneous problem $p_{n}+\frac{1}{4}p_{n-1}=0$. We then have characteristic equation $\omega^{n-1}(\omega + 1/4)=0$ and hence $\omega=-1/4$. So we have…
maths54321
  • 709
  • 5
  • 10
0
votes
1 answer

Recurrence equation process of solving

i am solving some reccurence relations and I am getting lost and not sure where to go I have $$T(n)=T(n-1)+ 1/7^{(n-1)}\quad \text{ where } T(1)=1$$ Which I tried solving with something like this T(1)=1 T(2)=T(1) + 1/7^(1) T(3)=T(2) +…
ThePejnMan
  • 1
0
votes
1 answer

Help with a recurrence relation?

I stumbled on this recurrence relation while looking at a kind of growth process. Unfortunately I haven't seen anything like this since high school! Is there a way to solve this? $a_2 = 0$, and for $i=3,4,5,\dots$ $$a_i =…
Ben S.
  • 505
0
votes
2 answers

How can I solve this basic recurrence $T(n) = \sqrt{n} \cdot T(\sqrt{n}) + n^2$?

Could someone post the detailed steps for calculating a tight upper bound of the following recurrence? $$T(n) = \sqrt{n} \cdot T(\sqrt{n}) + n^2$$
user781975
0
votes
1 answer

Particular solution to nonhomogeneous difference equation.

I'm working on one of the problems in Edelstein-Keshet's book 'Mathematical models in Biology'. The problem in question asks me to show that for some constant $K$, $X_{n}=K$ is a solution to the equation $aX_{n+2}+bX_{n+1}+cX_{n}=d$, with $d\neq 0$.…
Modesto Rosado
  • 445
0
votes
1 answer

Solve nonlinear Recurrence Relation

I am trying to solve the following recurrence relation for general constants $c_1,c_2,c_3$: $R(k) = c_1 + \frac{c_2}{R(k-1)}$, $R(0)=c_3$ I got a solution from Mathematica, but can't figure out how to get there.
tizi
  • 3
0
votes
1 answer

Linear non-homogeneous recurrence relation with combination and power on right-hand side

Solve the recurrence $h_{n+2} - 2h_{n+1} + h_n = {n \choose 2} + 2^n$ where $n \geq 0$, with initial values $h_0$ = 1 and $h_1$ = 1. I tried solving this question by writing $h_{n+3}$ term as $h_{n+3} - 2h_{n+2} + h_{n+1} = {n+1 \choose 2} +…
vk1234
  • 25
1 2 3
…
96 97