Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Definition of "recurrence relation"

  1. Aug 3, 2016 #1

    Stephen Tashi

    User Avatar
    Science Advisor

    The definition from the current Wikipedia article is a good start:

    My technical question is whether "each further term" is a function of only the values of the preceeding terms, or is it also a function of the index of the "further term"?

    For example, if we are given that the values of two consecutive terms are (in order) ##x## and ##y## and given the equation ## z = x + 2y## where ##z## is the next consecutive term, then we don't have to know that ##z## is the 5th term or the 24th term etc. in order to find ##z## from ##x## and ##y##.

    However, if we are given an equation like ##z_n = 2 z_{n-1} - 3 n z_{n-2} ## then I can find the "further term" ##z_n## if am given the value of the the previous two terms and the index ##n##, but it isn't obvious that I can find an an arbitrary term ##z## from previous terms ##x## and ##y## without knowing ##n##.

    On the one hand, it seems natural to allow the definition of "reccurence relation" to assume that ##n## is known, because the familiar examples of recurrence relation say things like ##z_n = .....## , explicitly using ##n## like the argument of a function.

    On the other hand, given any sequence of positive numbers ##a_0, a_1, a_2, ...## we would have the recurrence relation ##a_{n} = f(n) a_{n-1} ## where ## f(n) = \frac{a_n}{a_{n-1}} ##. So sequences of numbers satisfying recurrence relations would not be particularly special.

    It might be possible to leave dependence on ##n## out of the definition of recurrence relation and still have equations like ##z_n = 2z_{n-1} -3 nz_{n-2} ## be equivalent to recurrence relations if we can deduce the value of ##n## involved from the values of the two consecutive terms. The recurrence relation would be an equation employing a function that was implemented as a complicated algorithm - to the effect of "given x and y and the first two terms ##z_0, z_1## of the sequence, perform the following steps to deduce the index ##n## .....and then set ##z =2x + 3ny##".
     
  2. jcsd
  3. Aug 3, 2016 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The distinction is like the one where you have a differential equation like ##y^{\prime\prime} + 2y^\prime + 4y = 0## where all the coefficients are constant, or more complicated ones like ##xy^{\prime\prime} + xy = x^2##, where the coefficients are allowed to depend on the independent variable ##x##. Clearly, with constant coefficients, it is easier to handle.

    In the same way, you have recurrence relations where the coefficients are constant, like ##a_{n+1}= 2a_n##, or allowed to depend on an independent variable ##n##, like with ##a_{n+1} = na_n##. Clearly, the first type is easier to handle.

    The correspondence between differential equations and recurrence relation is more than just cosmetic, they are two sides of the same coin.
     
  4. Aug 3, 2016 #3

    fresh_42

    Staff: Mentor

    I tried to understand what it is about. I'm not quite sure, though. As soon as you use the term function instead of sequence, the enumerator of the sequence becomes a variable, namely the evaluation point of the function. Of course we can always resolve the recursion. I don't know whether this always results in a nice closed form, as e.g. the Fibonacci sequence, which can be written
    ##F(n) = \frac{1}{\sqrt{5}} \cdot (φ^{n} - (1-φ)^{n})## with ##φ = \frac{1+\sqrt{5}}{2}##
     
  5. Aug 3, 2016 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    I'll interpret that to mean that the definition of "recurrence relation" applies to equations where a term z in a sequence is equal to a function that depends on the values of some previous terms and also may depend explicitly on the index n of z in the sequence.

    However, I don't think of an equation like ##z_n = f(n,z_{n-1}) = n^2 - 3 n ## as being a recurrence relation even though it gives ##z_n## as a function of ##n## and ##z_{n-1}##. (Of course, the fact that ##f## is constant with respect to ##z_{n-1}## doesn't disqualify it from being a function of ##z_{n-1}##.)

    Looking for the definition of "recursive function" on the web, I find that people avoid giving any simple definition for it. There are various ways to precisely define the concept of a "recursively defined function" but they are specialized into various types of recursively defined functions. I have to wonder why people tread carefully when defining "recursively defined function" and are casual in defining a "recurrence relation".
     
  6. Aug 3, 2016 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Then you shouldn't look at an equation like ##y=f(x,y') =x^2-3x## as a differential equation either. I can appreciate this sentiment. But there is no reason to make a convoluted definition when even this pathological case follows all theorems.
     
  7. Aug 3, 2016 #6

    Stephen Tashi

    User Avatar
    Science Advisor

    I think you are saying that for any sequence ##a_0, a_1,a_2## there is an associated function ##f(n)## defined by ##f(n) = a_n##. I agree.

    My question is whether we want a definition of "recursion relation" to be so inclusive that an equation like ##a(n) = f(n) ## is a "recursion relation".

    Micromass says it is mathematically best to allow such equations to be called recursion relations because it preserves a connection between differential equations and the recursion relations that arise in finding power series solutions to those equations. I, personally, am not concerned with preserving that connection. However, I suspect that he is correct, in the sense that if we try to create a definition of "recursion relation" that excludes such examples, the definition will get complicated.
     
  8. Aug 3, 2016 #7

    fresh_42

    Staff: Mentor

    I think he's right, too (of course). Definitions like this do usually try to cover the largest possible variety and narrow down ranges of consideration by additional (often named) properties or classes. Thus I'd define a recursion of degree ##k## as ##a_n = f_\mathcal{I}(g(n),a_\iota)## with ##\iota \in \mathcal{I} \subseteq \{0,1, \dots , n-1\}## and ##|I|=k##.

    In the end it will certainly differ from author to author or from paper to paper. Would be interesting to know if there are conventions in language / automaton theory.
     
  9. Aug 3, 2016 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I'd even go further than you, and define it as
    [tex]f(n,a_n, a_{n-1},...)=0[/tex]
    In the same way, I would define a differential equation as
    [tex]f(x,y,y',...)[/tex]
     
  10. Aug 3, 2016 #9

    fresh_42

    Staff: Mentor

    You mean, as - in my notation - ##k = k(n)##?
    I'm thinking about your second differential equation and whether it covers the time dependent cases, too....
     
  11. Aug 3, 2016 #10

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    No, I didn't really follow your notation at all.
     
  12. Aug 3, 2016 #11

    fresh_42

    Staff: Mentor

    Shall the points in ##f(n,a_n,a_{n-1},...) = 0## indicate, that the number of predecessors that define the ##n##-th term may vary with ##n## as well? E.g. like ##f_{2n} = a_{2n-1}+a_{2n-2}+a_{2n-3}## and ##f_{2n-1} = a_{2n-2}-a_{2n-3}##?
    This would generate some challenging sequences.
     
  13. Aug 3, 2016 #12

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes, sure, I see no reason to put any restriction on that.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Definition of "recurrence relation"
  1. Recurrence Relation (Replies: 11)

  2. Recurrence relation (Replies: 7)

  3. Recurrence relation (Replies: 6)

  4. A recurrence relation (Replies: 7)

Loading...