Talk:Recurrence relation

This page may be a stub but still, it is excellent and covers the subject quite well. Keep up the good work.

Non-homogeneous recurrence & steady state

Section "Solving / General methods" (bottom) mentions shifting the sequence by a value, obtained form the steady state solution of the recurrence rule. It would be nice if someone qualified fills in 1) why does this work, and 2) what happens if there is no stable state, i.e. when 1-A-B = 0. Thanks! Pasmao (talk) 17:46, 18 April 2012 (UTC)

Relationship to differential equations

This article should discuss the relationship between diference/recurrence equations and differential equations. Specifically, it should show that discretization of a diferential equation yields a difference equation. This relationship is of vital importance to numerical simulations of physical processes on computers. --Fredrik Orderud 01:17, 30 May 2005 (UTC)

Right. But I think that probably belongs at the bottom of the article, after the recurrence relation is defined. for now, I plan to comment out that section, does not look good to have an unfinished section in an otherwise nice article. Oleg Alexandrov 02:55, 30 May 2005 (UTC)

The part about the similarity between the method of solving recurrence equations and differential equations is rather sketchy. It should be either removed or rewritten. Karl Stroetmann 00:05:17, 1 October 2005 (CEST)

A more intuitive explanation?

In the main article, there is an introduction to solving linear recurrance relations:

"Consider, for example, a recurrence relation of the form

$a_{n}=Aa_{n-1}+Ba_{n-2}.\,$

Suppose that it has a solution of the form a_n = r^n."

About a year ago, someone (probably a student) asked "WHY?" in the actual body of the article, on the main page. Why assume this? I think the question is a good one with a useful answer.

The article already includes a mathematically rigorous explanation below this quote, but I believe that to be inaccessible to the less experienced students for whom this article would be most useful.

At minimum, I think that quote should include a note referencing the justification listed below.

Difference equations?

It is stated without justification that difference equations are "a specific type of recurrence relation." In what way are difference equations only a subset of recurrence relations? As far as I know, they are one and the same. If this is not the case, some explanation of how they differ is in order. Otherwise, my edit would be reasonable. --Roy W. Wright 21:57, 18 November 2006 (UTC)

The equation $a_{n+1}=\tan a_{n}\,$ is not called a difference equation, but it is a recurrence relation. -- Jitse Niesen (talk) 05:29, 19 November 2006 (UTC)

Why is that not a difference equation? I would have called it a first-order, autonomous, nonlinear difference equation. It can also be written in "difference" notation as $d(a_{n})=a_{n}-\arctan(a_{n})$, which seems to meet the definition given in this article.--Rinconsoleao (talk) 18:24, 12 February 2009 (UTC)

True, the definition given in many texts would exclude that relation. Then might it be appropriate to say in the article that a difference equation is a specific type of recurrence relation of the form $a_{n+1}=a_{n}+F(a_{n},...)\,$? -- Roy W. Wright 09:08, 23 November 2006 (UTC)

I tend to see recurrence relations as just one where a function with certain parameters can be expressed as some function of the parameters, including the same function or a function that somehow links back to this function without a circular reference. Therefore, I see this article as inadequate, having explained mostly on only linear recurrences. -- 165.21.154.115 (talk) 12:47, 12 June 2008 (UTC)

I must agree with Roy W. Wright in that difference and recurrence equations are one and the same. If you google define: difference equation, the second definition (not the google-definition of course, which is this article) defines difference equations more general. Furthermore, in Relationship to difference equations, the time scale calculus that unifies the theory of difference equations with that of differential equations is mentioned. Please correct me if I'm wrong, but as far as I understand this theory applies to what is here defined as recurrence equations. It seems odd to have a theory about how a small subset of recurrence equations fit with differential equations, when all these equations actually have similar solutions as described in Relationship to differential equations.Espen Sirnes

• The MathWorld reference says that "recurrence relations" are also called "difference equations". --Rinconsoleao (talk) 17:51, 12 February 2009 (UTC)
• All the reference books listed in Recurrence relation#References (except one) have titles about "difference equations" rather than "recurrence relations".
• The EqWorld reference calls these equations "difference equations" instead of "recurrence relations".
• The section Recurrence relation#Relation to difference equations states that "Every recurrence relation can be formulated as a difference equation. Conversely, every difference equation can be formulated as a recurrence relation."

For all these reasons, it appears incorrect to say "Difference equations are a specific type of recurrence relation." And therefore the section Recurrence relation#Relation to difference equations is not discussing a special type of recurrence relation. Instead, it is defining an alternative notation for recurrence relations (i.e., for difference equations).

And all the references mentioned above (as well as my own experience) suggest to me that "difference equation" is the more standard term, and that the alternative notation in the section Recurrence relation#Relation to difference equations is a less standard notation.

So I would advocate deleting the claim that "Difference equations are a specific type of recurrence relation", and retitling the section Recurrence relation#Relation to difference equations in a more appropriate way. --Rinconsoleao (talk) 17:58, 12 February 2009 (UTC)

In every applied math, and biology paper I have read, difference equations and recurrence relations are treated as synonymous.MATThematical (talk) 16:44, 27 February 2010 (UTC)

IME(xperience), MathWorld is not reliable. It presents as fact quite a few serious mistakes that can be identified immediately by an expert. (They are fixed once identified, but there are always more.) This may or may not be one of them, but in any case, the MathWorld definition does not give substantive support to an argument. Zaslav (talk) 00:59, 24 October 2011 (UTC)

I have no opinion on the matter, not having encountered the subject of difference equations in my studies. I would just like to note that the subject must have somehow drifted from its origins: in the definition given in the lead of Rational difference equation, every one of the four arithmetic operations is used, except subtraction. Marc van Leeuwen (talk) 07:34, 24 October 2011 (UTC)

A simple recurrence with non constant coefficients

Can someone contribute an explicit solution to the recurrence

P(n+1) = n*[ P(n) + P(n-1) ] where P(0) = 1 & P(1) = 0.

P(n)/n! is among other things the probability that if n numbered balls are distributed randomly into n numbered pockets no ball will end up in the proper pocket. It is easy to see computationally that as n increases P(n)/n! tends toward 1/e.

22:21, 1 April 2007 (UTC) lklauder@wsof.com

It's P(n)=Γ(1+n,-1)/e Espen Sirnes (talk) 14:35, 2 April 2009 (UTC)

General solution for linear recurrence relation

I don't really understand the general solution described in the article, especially in part 3:

3 Write a_n as a linear combination of all the roots (counting multiplicity as shown in the theorem above) with unknown coefficients...

The equation given is unclear. From the statement " q is the multiplicity of gamma_* ", it seems to imply that the multiplicity of the root gamma_1 is r-1 because this is the highest exponent of n given in that term. This should be impossible, as the characteristic equation is only of order r. Could someone make this clearer with sigma notation for the sum? Or maybe include more terms before the ellipsis?

In addition, aren't the numbers c_1 through c_r already known - they are the coefficients in the original recurrence relation? Is this bad notation, or a misunderstanding, perhaps?

Zatomics 05:51, 15 April 2007 (UTC)

I agree that it's not very clear. In fact, I think I only understand the explanation because I already know it. The multiplicity of $\lambda _{1}$ is r. The characteristic equation has degree n. Finally, the numbers c₁, …, c_n in the general solution are not the same as the coefficients in the original equation; that's just terrible notation.

It's perhaps clearest if you look at an example. Take the linear recurrence relation

$a_{n}=2a_{n-1}+8a_{n-2}-16a_{n-3}-16a_{n-4}+32a_{n-5}.\,$

The characteristic polynomial is

$t^{5}-2t^{4}-8t^{3}+16t^{2}+16t-32,\,$

which factorizes as

$(t-2)^{3}(t+2)^{2}.\,$

So the characteristic polynomial has two roots, t = 2 (with multiplicity 3) and t = −2 (with multiplicity 2). The recurrence relation has five independent solutions: $a_{n}=2^{n}$, $a_{n}=n2^{n}$, $a_{n}=n^{2}2^{n}$, $a_{n}=(-2)^{n}$ and $a_{n}=n(-2)^{n}$. The general solution is

${\begin{aligned}a_{n}&=C_{1}2^{n}+C_{2}n2^{n}+C_{3}n^{2}2^{n}+C_{4}(-2)^{n}+C_{5}n(-2)^{n}\\&=(C_{1}+C_{2}n+C_{3}n^{2})2^{n}+(C_{4}+C_{5}n)(-2)^{n}.\end{aligned}}$

With a bit of luck, you can see from this example what the general solution looks like. -- Jitse Niesen (talk) 14:42, 16 April 2007 (UTC)

problems

solve the followng recurrence relations:-

1. T(k)+3kTk-1)=0,T(0)=1
2. T(n)=3T(floor(n/2)),T(0)=1[ceiling function i.e. ceilin g of 8.2=8] —Preceding unsigned comment added by Piyush aus (talk • contribs) 10:22, 7 December 2007 (UTC)

Mistake in "Solving non-homogeneous recurrence relations"

The example method of solution is wrong. An nth degree inhomogeneity should give an (n+1) degree guess (for example, the solution to a_n+1 = a_n + 1 is a degree 1 polynomial). I don't know anything about the 3ⁿ part so I'm just going to move the example from the article to this discussion. Can someone who knows something about this subject please fix it? Thanks. RobHar (talk) 18:56, 27 October 2008 (UTC)

From article:

Example

Let's solve the following inhomogeneous recurrence relation using the method of undetermined coefficients:

$a_{n+1}=2a_{n}+3^{n}+5n\,$

The general solution for the analogous homogeneous relation

$b_{n+1}=2b_{n}\,$

is

$b_{n}=c_{1}2^{n}\,$

The inhomogeneous part ($3^{n}+5n$) leads us to guess the particular solution

$a_{n}=c_{2}3^{n}+c_{3}n+c_{4}\,$

(the guess for $a^{x}$ is $a^{x}$, and the guess for a degree-n polynomial is a degree-n polynomial)

Substituting back into the recurrence relation, we get:

$c_{2}3^{n+1}+c_{3}(n+1)+c_{4}=2(c_{2}3^{n}+c_{3}n+c_{4})+3^{n}+5n\,$

Looking only at the coefficients of $3^{n}$:

$3c_{2}=2c_{2}+1\,$

$c_{2}=1\,$

Looking only at the coefficients of $n$:

$c_{3}=2c_{3}+5\,$

$c_{3}=-5\,$

Looking only at the coefficients of $1$ (constants):

$c_{3}+c_{4}=2c_{4}\,$

$c_{4}=c_{3}=-5\,$

So the general solution is

$a_{n}=c_{1}2^{n}+3^{n}-5n-5\,$

Needs work

The body of this article should go under the heading of linear recurrence relations because that is all that there really is. The logistic equation in the intro is great stuff but nothing non-linear happens after that. I suggest a short recurrence relations article elsewhere with pointers.

For now I'll just clean up the start of the linear homogeneous constant coefficients case.

--Gentlemath (talk) 06:56, 21 February 2009 (UTC)

Requested move

The following discussion is an archived discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.

The result of the move request was not moved. Jafeluv (talk) 16:36, 13 September 2009 (UTC)

---

Recurrence relation → Difference equation — The references of this article and those posted by Rinconsoleao's in February 2009 (Talk) suggest that dif.eq. is the standard term. In any case the section Relationship to difference equations needs to be changed. It is probably incorrect that difference equations only refer to those resulting from taking the difference of time variables, but if so it is certainly not the case that only such equations have solutions similar to differential equations. Espen Sirnes (talk) 11:28, 5 September 2009 (UTC)

As the article says, these are not the same thing; recurrence relation is any relation defined recurrently. It is of course true that difference relations need not be time series; any integers will do. Technically they need not be indexed with integers, but this is one of those cases where we should start with the central meaning and work out to generalizations. Septentrionalis PMAnderson 21:44, 5 September 2009 (UTC)

Oppose move; if a separate article on difference equations were written, it could be a virtual subarticle of this one. — Arthur Rubin (talk) 23:53, 5 September 2009 (UTC)

The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

geometric

Statement only accurate if the roots of the indicial polynomial are distinct; otherwise sequences of the form $nr^{n}$ are required, which are not geometric series. — Arthur Rubin (talk) 22:12, 21 February 2010 (UTC)

Self-published references?

I had deleted a reference to a self-published book (Bruce R. Gilson, The Fibonacci Sequence and Beyond, CreateSpace). An editor (BRG) has reinstated it. I'd like other editors' opinions. Thanks, [[::User:Goochelaar|Goochelaar]] ([[::User talk:Goochelaar|talk]]) 23:26, 4 March 2010 (UTC)

The other reference seems a personal web site, as well. I've tagged with {{verify credibility}}. The statement supported by reference one seems to follow from the theorem, which I hope is taken from some source. — Arthur Rubin (talk) 10:22, 5 March 2010 (UTC)

Neutral resolution of Difference equation vs. Recurrence relation

The above discussion over several years shows that some people use "difference equations" to refer to a subset of recurrence relations and some use it to refer to all recurrence relations. I hope I've resolved this in a neutral way with this edit: At the first mention of difference equations in the introduction, I've replaced a non-neutral sentence with "The term difference equation sometimes (and for the purposes of this article) refers to a specific type of recurrence relation. Note however that "difference equation" is frequently used to refer to any recurrence relation." Duoduoduo (talk) 20:02, 20 May 2010 (UTC)

Organization of article

I believe this article as it currently appears is mostly too high level for anyone who doesn't already have a command of this material. Partly this is due to its organization. I think that the contents ought to be arranged like this (with more sub-sections added -- the following is bare-bones):

I. Example

II. Linear recurrences

A. First-order

B. Second-order

C. Higher-order

III.Non-linear recurrences

IV. Relation to difference equations

V. Applications

This way the reader can see the big picture before diving into the details. The above sections and sub-sections II A,B,C and III would give the solution by focusing on (i) the steady-state solution, and (ii) the terms involving powers of eigenvalues, which would be presented along with the characteristic equation. The first-order section would show (maybe even graphically) the monotonic approach to the steady state. The second-order linear section would show that with complex eigenvalues one gets a trigonometric solution, which can involve fluctuations. Duoduoduo (talk) 20:24, 20 May 2010 (UTC)

Merge with Iterated function?

It appears that the articles Recurrence relation and Iterated function are about the same thing. Is there any objection to merging them? Which should be merged into which? Duoduoduo (talk) 22:56, 28 May 2010 (UTC)

Since the relation concept is wider than the function concept, if a merge takes place, I think the functions should be merged into the relations. DVdm (talk) 09:13, 29 May 2010 (UTC)

Recurrence relations are only loosely related to iterated functions. For example, the solution to the Fibonnaci equation in section 1 of this article is

$F\left(n\right)={{\varphi ^{n}-(1-\varphi )^{n}} \over {\sqrt {5}}}\,,$

which is not an iterated function of any sort. Indeed, there cannot be a function f such that f(0) = 1 and such that the list f(0), f(f(0)), f(f(f(0))), ..., enumerates the Fibonnaci numbers. So their recurrence relation cannot be solved in terms of an iterated function. — Carl (CBM · talk) 13:11, 29 May 2010 (UTC)

The Fibonacci equation itself (not its solution) can be written as a bivariate iterated function: $[F_{n+2},\ \ F_{n+1}]=g([F_{n+1},\ \ F_{n}])$. So the two concepts would appear to be identical. Duoduoduo (talk) 19:35, 29 May 2010 (UTC)

That's not what people ordinarily mean by "iterated function". Moreover as I pointed out, the ordinary solution to the Fibonnacci recurrence is not iterated in any sense, it's just a difference of two power functions. — Carl (CBM · talk) 03:49, 1 June 2010 (UTC)

It's almost the same basic idea, but treated from two very different points of view. A bit like having separate pages for weather and meteorology or something. I think it's reasonable to keep both pages, but they should cross-reference each other. Jowa fan (talk) 06:18, 1 June 2010 (UTC)

I'm removing the merge tag since there's no real support for it. Duoduoduo (talk) 21:07, 16 June 2010 (UTC)

Too narrow; needs more

The title is misleading. This article at present is almost entirely about linear, constant-coefficient recurrences. The title could be "Linear recurrence relations with constant coefficients". Either that should be the new title and there should be a separate general article, or this article needs a whole lot more content. (I tend to favor the first solution, unless someone adds the new content very soon.) Zaslav (talk) 01:03, 24 October 2011 (UTC)