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
2
votes
2 answers

Is there a solution to this recurrence relation

Let $a(n+2) = -a(n+1) - a(n) - 1$ for all $n\geq 1$. In this case, is there a solution for a(n) and if so, what is it and how do you find it?
Cenam
  • 63
2
votes
1 answer

Given a sequence $1,-2,-1,2 \ldots$ find a recurrence relation and solve it

Consider the sequence $1,-2,-1,2,1,-2,-1\ldots$ I'm trying to find the recurrence relation and finding a closed-form solution to it. I'm stuck at trying to find how the numbers relate to each other. I've tried to construct a $2 \times 2$ square with…
Marco Altieri
  • 23
2
votes
2 answers

Solve $T(n) =2T(n-5)+n$, $T(1)=1$ and proof the solution is true by induction

I've seen the solution of this Solve the recurrence $T(n) = 2T(n-1) + n$ So I have done 1) $T(n)=2T(n-5)+n$ , $T(n-5)=2T(n-2\cdot5)+(n-5)$ e.t.c , my final line is $$T(n)=2^kT(n-5k)+\sum_{j=0}^{k-5} 2^j(n-j).$$ Any help? From link I can't figure…
Thanos
  • 21
2
votes
3 answers

non homogeneous recurrence relation

I am trying to solve the non-homogeneous linear recurrence relation: $$f(n) = 6f(n-1) - 5,\quad f(0) = 2.$$ How do I go about doing it? This is so different from solving a homogeneous recurrence relation.
akermannn
  • 33
2
votes
2 answers

Solution of second order difference equation with non constant coefficient

What is the general approach to solve a second order difference equation with non constant coefficients? e.g $$X_{n+1} = 5nX_n + X_{n-1}$$
Subhodeep Maji
  • 29
2
votes
1 answer

A person can climb to a nth floor in steps of 1, 2 or 3. Count number of ways a person can reach 12th floor.

Example:A person can reach 1st floor in only 1 way, 2nd floor in 2 ways, 3rd floor in 4 ways and 4th floor in 7 ways. Using recursive calls i got answer as 927 but there is no such option. 1023 734 827 69
Sai Pavan
  • 51
2
votes
1 answer

A recurrence relation on two variables

How to solve the recurrence relation for $n >=m$: $$P_{n,m}=\frac{n}{n+m}P_{n-1, m} + \frac{m}{m+n}P_{n,m-1}$$ $$P_{11}=\frac{1}{2}; P_{i,0}=1 \forall i > 0; P_{i,j}=0 \forall i
user21982
2
votes
2 answers

Solving a recurrence relation $a_n =\sum_{i=0}^{n-2} a_i $

I'm given the following recursive formula: $a_n =\sum_{i=0}^{n-2} a_i \\a_1 = 1 , \; a_0 = 1 $ I noticed that $\;a_2 = 1$ as well , and for any $n>3 : \, a_n - a_{n-1} =\sum_{i=0}^{n-2} a_i \; - \sum_{i=0}^{n-3} a_i = a_{n-2} $ so this seems close…
giorgioh
  • 322
2
votes
3 answers

$8y(t+2)-6y(t+1)+y(t)=2^t$ via Annihilator Method

This question is taken directly from "Difference Equations: An Introduction with Applications",second edition, by Walter G. Kelley and Allan C. Peterson: Solve $$8y(t+2)-6y(t+1)+y(t)=2^t$$ via the annihilator method. Could someone show this in…
Matt Groff
  • 6,117
2
votes
1 answer

Find the solution to the recurrence relation $a_{n} = 3a_{n−1} +4a_{n−2}$ with initial terms $a_{0}=5$ and $a_{1} =8$

For the question Find the solution to the recurrence relation $a_{n} = 3a_{n−1} +4a_{n−2}$ with initial terms $a_{0}=5$ and $a_{1} =8$ I think the way to solve this is the Characteristic Root Technique since the recurrence relation is a…
Sam
  • 865
2
votes
2 answers

Solving the Recurrence Relation $T(n)=T(n-1)+n\log n$

Solve $\;T(n)=T(n-1)+n\log n$ This is how I started: $$\begin{align} T(n)&=T(n-2)+(n-1)\log(n-1)+n\log(n)\\ &=T(n-3)+(n-2)\log(n-2) + (n-1)\log(n-1)+n\log(n) = \end{align}$$ Actually, I'm stuck here. I can't find a way to reformat the log..
user3523226
  • 109
  • 1
  • 10
2
votes
1 answer

Prove If $a_0=2, a_{n}=\frac{\pi^{n+1}}{n!}\int_{0}^{1}t^n(1-t)^n\sin( \pi t)dt(n\geq 1)$ then $a_{n+1}+a_{n-1}=\frac{4n+2}{\pi}a_n $

I would appreciate if somebody could help me with the following problem: Please explain how to do this proof ? $$$$ If $$a_0=2, a_{n}=\frac{\pi^{n+1}}{n!}\int_{0}^{1}t^n(1-t)^n\sin( \pi t)dt(n\geq 1)~~~$$ then…
Young
  • 5,492
2
votes
1 answer

Recurrence Relation $F(n) = (n-1)F(n-2)$

How can I solve the following recurrence relation in terms of $f(1)$ ? -Assuming $n$ is odd. $$F(n) = (n-1)\cdot F(n-2)$$
choptxen
  • 33
2
votes
1 answer

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 terms $a_n$ for $n\geq3$ is obtained by adding a…
Qurultay
  • 5,224
2
votes
2 answers

Recurrence k-th pattern

I am trying to solve this recurrence $T(n) = 6 T(\frac{n}{3}) + n$. 1st recurrence: $6^2T(\frac{n}{3^2}) + \frac{6n}{3} + n$ 2nd: $6^3T(\frac{n}{3^3}) + \frac{6^3n}{3^2} + n$ 3rd: $6^4T(\frac{n}{3^4}) + \frac{6^6n}{3^3} + n$ I am having trouble…
aryamank
  • 81
1 2 3
…
96 97