What is Recurrence: Definition and 256 Discussions

In mathematics, 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.
The term difference equation sometimes (and for the purposes of this article) refers to a specific type of recurrence relation. However, "difference equation" is frequently used to refer to any recurrence relation.

View More On Wikipedia.org
Recent contents Top users
  1. S

    MHB Solve Recurrence: $s_n = 2_{s_n-1} - s_{n-2}$ | Discrete Math

    Derive an exact formula (solve the recurrence definition) for the following recursive sequence: $s_n = 2_{s_n-1} - s_{n-2}$ where $n \ge 2$, and $s_0 = 4$, $s_1 = 1$. So I saw someone solving this by making it a differential equation or something? How would you do that? should I do let...
  2. S

    Learning Recurrence Relations: Challenges & Solutions

    Homework Statement : [/B] I am just learning recurrence relations, and they are proving challenging.Homework Equations -- [/B]Let's have xn = 3xn-1 + 6xn-2. I wanted to look at it with two scenarios. The first is x0 = 1 and x1 = 3. The second is x1=3 and x2 = 4 The Attempt at a Solution Is...
  3. ognik

    MHB Reversing recurrence relationships

    A couple of times I have come across the suggestion that numerically evaluating a recursive relation in reverse can be a valuable approach. I can see this where, for example, the boundary conditions at one 'end' are inaccurate or undiscoverable. However, while the arithmetic of manipulating...
  4. N

    MHB Finding this recurrence relation for stuck-together right-angle triangles

    Given the image: http://i.stack.imgur.com/EJ3ax.jpgand that $x_0 = 1, y_0=0$ and $\text{angles} \space θ_i , i = 1, 2, 3, · · ·$ can be arbitrarily picked. How can I derive a recurrence relationship for $x_{n+1}$ and $x_n$? I actually know what the relationship is, however, don't know how to...
  5. T

    Can a recurrence relation be proven using induction?

    Homework Statement prove that s_k <= 2s_{k-2}+3 for all ints k >= 3 if s1=1 and s2 = 3 and s2=5 and s4=9The Attempt at a Solution base case k = 3 s_3 <= 2s_1 + 3 5 <= 2+3 that is true. Now i must prove the inductive step. This is where I am having trouble. I assume that s_k <= 2s_{k-2}+3...
  6. Jimster41

    Confusion: Fluctuation Theorem, Poincare Recurrence Theorem

    Is Poincare' Recurrence Theorem (PCRT) considered a possible explanation for the "low entropy" initial conditions of the universe? Is the following a roughly correct paraphrasing of it? For a phase space obeying Liouville's theorem (closed, non-compress-able, non-decompress-able), the...
  7. D

    Several questions about the poincare recurrence time?

    Keep in mind I am a complete layman when it comes to physics. Is the Poincare recurrence time the time it will take for the universe to be exactly in the state again as it is now or the time before the universe will even begin to be able to starting producing basic patterns from chaos? What is...
  8. ellipsis

    Prove recurrence relation via mathematical induction

    $$ T(n) = \begin{cases} 2 & \text{if } n = 2 \\ 2T(\frac{n}{2})+n & \text{if } n = 2^k \text{, for } k > 1 \end{cases}\\ \text{ } \\ \text{ } \\ \text{ } \\ \text{Prove } T(n) = n\lg(n) \text{ if } n = 2^k\text{, for } k > 1.$$ I am crawling through the "Introduction to Algorithms" textbook...
  9. M

    MHB Solving a Recurrence: $a_0 = 2$

    Not sure if Discrete Math is the correct category, but I'm looking for some idea / hint on how to tackle the following recurrence. $a_0 = 2$, and $a_{n+1} = 2a_{n} + \sqrt{3(a_n)^2 - 12}$ for $n \in \Bbb{N}$. Some attempts to massage the equation got me: $(a_{n+1}-a_n)^2 = 2a_na_{n+1} - 12$...
  10. J

    Question on solving linear recurrence relations

    Why does the characteristic equation of a linear recurrence relation always look like an = series of constants multiplied by a number raised to n
  11. evinda

    MHB Recurrence relation - initial condition

    Hello! (Smile) I want to find the exact solution of the recurrence relation: $T(n)=2T(\sqrt{n})+1$.$$m=\lg n \Rightarrow 2^m=n \\ \ \ \ \ \ \ \ \ 2^{\frac{m}{2}}=\sqrt{n}$$ So we have: $T(2^m)=2T(2^{\frac{m}{2}})+1$ We set $T(2^m)=S(m)$, so we get: $S(m)=2S \left( \frac{m}{2}\right)+1$...
  12. C

    Solve the recurrence relation using iteration

    Homework Statement [/B] Solve the recurrence relation (use iteration). an = an-1 + 1 + 2n-1 a0 = 0 Then prove the solution by mathematical induction. Homework EquationsThe Attempt at a Solution a1 = 2 a2 = 5 a3 = 10 a4 = 19 a5 = 36 The solution appears to be an = n + 2n - 1 How are we...
  13. evinda

    MHB Show that $S(m)=\Theta(m^2)$ with Recurrence Relation

    Hello! (Smile) Let $S(m)=S(m-1)+m$. I want to show that $S(m)=\Theta(m^2)$. That's what I have tried: We suppose a positive integer $m>0$. We suppose that $S(m-1)=\Theta((m-1)^2)$, so it holds that $\exists c_1, c_2>0$ such that : $$c_1 (m-1)^2 \leq S(m-1) \leq c_2(m-1)^2$$ We will show that...
  14. M

    MHB Solve Recurrence $$T(n)=aT(n-1)+bn^c$$

    Hey! :o I want to solve the following recurrence: $$T(n)=aT(n-1)+bn^c , T(1)=1$$ I have done the following: $$T(n)=aT(n-1)+bn^c \\ =a \left ( aT(n-2)+b(n-1)^c\right )+bn^c \\ =a^2T(n-2)+ab(n-1)^c+bn^c \\ =a^2 \left (aT(n-3)+b(n-2)^c\right )+ba(n-1)^c+bn^c...
  15. M

    MHB How is the Solution to the Given Recurrence Relation Derived?

    Hey! :o I need some explanations at the proof of the following theorem. Theorem: Let $a$, $b$ and $c$ be nonnegative constants. The solution to the recurrence $$T(n)=\left\{\begin{matrix} b & ,\text{ for } n=1\\ aT(n/c)+bn & ,\text{ for } n>1 \end{matrix}\right.$$ for $n$ a power of $c$ is...
  16. 22990atinesh

    Is there a mistake in my solution for this recurrence?

    Homework Statement ##T(n) = 2 T(\frac{n}{2}) + 2## ##T(1) = 2## Homework EquationsThe Attempt at a Solution I'm coming up with ##T(n) = n-1## on solving it by recursion tree method. But that's not the ans
  17. 22990atinesh

    Can You Solve This Recurrence Using the Recursion Tree Method?

    Homework Statement ##T(n) = 2 T(n-1) + n, n \geq 2## ##T(1) = 1## Homework EquationsThe Attempt at a Solution I'm using recursion tree method to solve the above recurrence T(n) = Summation of non-leaf nodes + leaf nodes ##T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-1}##
  18. 22990atinesh

    What Is the Solution to the Recurrence Relation T(m^2)?

    Homework Statement If ##T(n+1)=T(n)+ \lfloor \sqrt{n+1} \rfloor , n \geq 1## ##T(1)=1## then ##T(m^2) = ? , m \geq 1## Homework EquationsThe Attempt at a Solution ##T(n)=T(n+1) - \lfloor \sqrt{n+1} \rfloor , n \geq 1## ##T(m^2)=T(m^2+1) - \lfloor \sqrt{m^2+1} \rfloor## ... ##T(m^2)=...
  19. T

    MHB Solving Linear Recurrence Relations

    Solve each of the following linear recurrence relations: 1. t(1)=1 t(2)=4 t(n) - 5t(n-1) + 6t (n-2)= 0 for n>1 2. a(n)=4a(n-1) - 4a (n-2) with initial conditions a(0) = 4 and a(1)=12 3. t(1)=3 t(2)=3 t(n) + 2t (n-1) + t(n-2) = 0
  20. evinda

    MHB Recurrence Relation: Master Theorem Solution

    Hello! (Wave) I want to use the master theorem, in order to find the exact asymptotic solution of $S(m)=4S \left ( \frac{m}{2}\right )+m^3 \sqrt{m}$. $$a=4 \geq 1, b=2>1, f(m)=m^3 \sqrt{m}$$ $$m^{\log_b a}=m^{\log_2{2^2}}=m^2$$ $$f(m)=m^{3+\frac{1}{2}}=m^{\log_b a+ \frac{3}{2}}$$ Thus...
  21. evinda

    MHB Proving $T(n)=O(n^2 \lg^2 n)$ Using Recurrence Relation

    Hello! (Wave) I want to prove that $T(n)=4 T \left ( \frac{n}{2}\right )+n^2 \lg n=O(n^2 \lg^2 n)$,where $T(n)$ is constant for $n \leq 8$, using the following method: "We choose a specific function $f(n)$ and we try to show that for an appropriate $c>0$ and an appropriate $n_0 \in...
  22. evinda

    MHB Upper Bound for Recurrence Relation: $T(n) \leq c n^2 \log^2 n$

    Hello! (Wave) I want to find an asymptotic upper bound for the recurrence relation: $T(n)=9T \left (\frac{n}{3} \right ) + n^2 \log n $, $T(n)=c, \text{ when } n \leq 9$, using the following method: We choose a specific function $f(n)$ and we try to show that for an appropriate $c>0$ and an...
  23. K

    Monotony of a recurrence relation

    What method should i use to know if a recurrence relation is increasing or decreasing? i was given the following relation: A1 = 1 An=(An-1)^5 - 3 I know for sure it actually decreases since every term for n>=2 is a negative number raised to and odd number, but i don't know how to demonstrate...
  24. evinda

    MHB Proving by Induction: Solving Recurrence Relation

    Hello! (Wave) I want to prove by induction, that the solution of the recurrence relation $T(n)=2T \left ( \frac{n}{2} \right )+n^2, n>1 \text{ and } T(1)=1$ is $n(2n-1)$. We have to suppose that $n=2^k, k \geq 0$, right? Do I have to prove the solution by induction with respect to $n$ or to...
  25. alyafey22

    MHB A recurrence formula for an integral

    I was solving an integral and on the process of integration by parts it seems that I have a certain recurrence formula that I have to solve. Before I post it I want to understand how to solve a simpler case which is $$A(p,q) = A(p-1 , q ) +A(p,q-1) $$ where the base case $A(p,1)$ and $A(1,q)$...
  26. F

    MHB How to derive a recurrence relation from explicit form

    I am given a formula in explicit form and as a recurrence relation. It is asked to derive the recurrence relation from the explicit form. How is this done?
  27. anemone

    MHB Calculating $U_{513}$ of a Sequence Defined by Recurrence Relation

    Let $U_1,\,U_2,\,\cdots$ be a sequence defined by $U_1=1$ and for $n>1$, $U_{n+1}=\sqrt{U_n^2-2U_n+3}+1$. Find $U_{513}$.
  28. mnb96

    Obtaining recurrence relation from a given sequence

    Hello, it is known that given a certain recurrence relation that describes a sequence of numbers, it is often possible to obtain a function f[n] that directly yields the n-th number of the sequence. This is usually accomplished by using powerful techniques involving generating functions or the...
  29. Greg Bernhardt

    How are recurrence relations used in mathematics and computer science?

    Definition/Summary A recurrence relation is an equation which defines each term of a sequence as a function of preceding terms. The most well-known are those defining the Fibonacci numbers and the binomial coefficients. An ordinary differential equation can be considered as a recurrence...
  30. J

    Recurrence relations with rabbits pairs

    A single pair (male and female) of rabbits is born at the beginning of the year. Assume the following: 1) Each pair is not fertile for their first month bet thereafter give birth to four new male/female pairs at the end of every month 2) no rabbits die a) let r_{n} be the number of pairs of...
  31. J

    Nonhomogeneous recurrence relations

    Homework Statement Solve the recurrence relation an = 3an−1 −2an−2 +3, a0 = a1 = 1.Homework Equations an = general solution + particular solutionThe Attempt at a Solution I started with finding the general solution, which was easy. it ended up being A12n + A0 now I am having trouble solving...
  32. A

    MHB Inhomogeneous recurrence relation

    Hi all, Could someone please explain to me the process involved in converting an inhomogeneous recurrence to a homogeneous recurrence, I'm completely confused as to how it works.Thanks
  33. Saitama

    MHB Can the Limit of a Recurrence Relation Problem Approach the Square Root of 2?

    Problem: Let $a_0$ and $b_0$ be any two positive integers. Define $a_n$, $b_n$ for $n\geq 1$ using the relations $a_n=a_{n-1}+2b_{n-1}$, $b_n=a_{n-1}+b_{n-1}$ and let $c_n=\dfrac{a_n}{b_n}$, for $n=0,1,2,\cdots $. Write a)Write $(\sqrt{2}-c_{n+1})$ in terms of $(\sqrt{2}-c_n)$. b)Show that...
  34. S

    Recurrence relation involving multiple sequences

    Homework Statement I'm given a recursive sequence with the following initial terms: ##\begin{matrix} f_0(0)=1&&&f_1(0)=0\\ f_0(1)=2&&&f_1(1)=1 \end{matrix}## Now, I'm asked to justify that we have the following recursive relations: ##\begin{cases} f_0(n)=2f_0(n-1)+f_1(n-1)\\...
  35. MarkFL

    MHB Yahoo Answers: Linear Homogeneous Recurrence - JunkYardDawg

    Here is the question: I have posted a link there to this thread so the OP can view my work.
  36. Y

    MHB Solve Recurrence Relation w/ 3 Terms & Initial Conditions

    How to solve this question. Please explain step by step.
  37. MarkFL

    MHB Jackin's question at Yahoo Answers regarding a linear recurrence

    Here is the question: I have posted a link there to this thread so the OP can view my work.
  38. E

    Solving Recurrence Relations in Matlab: A Homework Challenge

    Homework Statement Evaluate the following series ∑u(n) for n=1 → \infty in which u(n) is not known explicitly but is given in terms of a recurrence relation. You should stop the summation when u(n) < 10^(-8) u(n+1) = (u(n-1))^2 + (u(n))2 with u(1) = 0.5, u(2) = 0.6 Note 1:The lecturer...
  39. B

    MacroEcon, Stock Prices, Recurrence Relations (and Linear Algebra?)

    Homework Statement This is a question from an upper level econ course that is giving me quite a bit of trouble. Fluency in linear algebra is assumed for the course. I'm taking a linear algebra course for the first time this semester so I'm still scrambling to learn the basics. If anyone has a...
  40. M

    Questioning Recurrence Relation: 3n-1 - an-1

    I boxed the portion of the solution that I am questioning. How come the number of invalid strings is only 3n-1 - an-1 and not 3(3n-1 - an-1) ? As you can see there are three cases (Which are to the right of the black box) In all the three cases, the portion boxed in red is a string...
  41. M

    Finding Recurrence Relation for Bit Strings with Consecutive Zeros

    I am having difficulty knowing which "cases" include in the recurrence equation. My solution to problem in paint document. Cases 1 - 6: All cases contain strings of length n Let ak represent number of bit string of length k with a pair of consecutive 0s. For cases 1 and 2. an-1, k = n-1. 1...
  42. F

    MHB Solving third order recurrence relation

    I'm trying to solve a third order recurrence relation but not sure how. I wrote the characterisitc polynomial and factored it into (x-1)^3. Now what?
  43. F

    MHB Find Recurrence Relation for Flipping n Switches

    A circuit has n switches, all initially off. In order to be able to flip the ith switch, the (i-1)th switch must be on and all earlier switches off. The first switch can always be flipped. Find a recurrence relation for the total number of times the n switches must be flipped to get the nth...
  44. A

    Combinatorics: Finding recurrence relation

    Find the number of ways to arrange three types of flags on an n foot flag pole: red flags (1 foot high), white flags (1 foot high), blue flags (3 feet high) Find a recurrence relation for this number with one condition that there cannot be three 1 foot flags in a row (regardless of their...
  45. jk22

    How to solve this functional (recurrence) equation ?

    I'm in a problem where I have to solve the following functional equation : F(n)^2=n+F(n+1) Does anyone know some methods to solve this kind of problems ? A similar equation happens in Ramanujan example of root denesting : http://en.wikipedia.org/wiki/Nested_radical#Square_roots
  46. U

    Frobenius series without recurrence relation

    Homework Statement Consider x^2y''-xy'+n^2y=0 where n is a constant. a) find two linearly independent solutions in the form of a Frobenius series, initially keeping at least the first 3 terms. Can you find the solution to all orders? b) for n=1 you shouild find only one linearly...
  47. Fernando Revilla

    MHB How do you solve the recurrence relation P(n) = 1 + 5n by induction?

    I quote a question from Yahoo! Answers I have given a link to the topic there so the OP can see my response.
  48. MarkFL

    MHB VulcaBlack's Inhomogeneous Linear Recurrence Q&A

    Here is the question: I have posted a link there to this topic so the OP can see my work.
  49. M

    MHB Solving Recurrence Relations: Are My Results Right?

    Helloo! I have to solve the following recurrence relations: (a) T(n)=sqrt(2)*T(n/2)+lgn (b) T(n)=3*T(n/4)+nlgn (c) T(n) 3*T(n/3)+n/2 (d) T(n)=5*T(n/2)+Θ(n) (e) T(n)=9*T(n/3)+O(n^2) Could you tell me if my results are right? Using the master theorem I found: (a)T(n)=Θ(sqrt(n)) (b)T(n)=Θ(nlgn)...
  50. MarkFL

    MHB Julia's question at Yahoo Answers regarding a linear recurrence

    Here is the question: Here is a link to the question: Pre Calculus homework help please!? - Yahoo! Answers I have posted a link there to this topic so the OP can find my response.
Back
Top