Talk:Recurrence relation

Untitled

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 from 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) (Edited 25 April to correct a typo.)

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ⁿ."

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) [email protected]

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, 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)

Agreed. User:Linas (talk) 07:39, 1 December 2013 (UTC)

Derivative of a nonlinear map

I think the section on Stability of nonlinear first-order recurrences is confusing. It is somehow intuitive that the recurrence converges to a fixed point $x^{*}$ if the slope in the neighborhood of $x^{*}$ is less than unity. However, what does "slope" and taking $f'(x^{*})$ mean exactly? What's the derivative of a recurrence?

For example, take the logistic map $x_{n}=f(x_{n-1})=1-\alpha x_{n-1}^{2}$. Although $f$ is differentiable, if one plots the recurrence it is clear that the recurrence is in fact not differentiable. The slope at any $x$ is not defined unless $x$ is a fixed point, in which case the slope is 0.

Furthermore, take for example $\alpha =1$ and $x=0$. Then $f'(x)=-2x=0$ which is less than unity. However, $x=0$ is certainly no fixed point; the system will oscillate indefinitely between 1 and 0. — Preceding unsigned comment added by Msnel (talk • contribs) 17:47, 19 April 2012 (UTC)

A method for discrete linear systems

Matrix powers of the form $A^{t}$ are useful for solving linear difference equations that look like:

$x_{t+1}=Ax{t}+Bu(t)$,

where $x(t)$ is the state space, $u(t)$ is the input, $A$ is the state-space matrix, and $B(t)$ is the input matrix.

This method was taught to me by a Hungarian mathematician and I'm not even sure what it is called. The problem is to find $A^{t}$.

Anyways I will include an example and steps below. Given $A={\begin{pmatrix}1&1&0&0\\0&1&1&0\\0&0&1&-1/8\\0&0&1/2&1/2\end{pmatrix}}$

First, compute the eigenvalues. $\lambda _{1}=3/4$ and $\lambda _{2}=1$ each with an algebraic multiplicity of two.

Now, take the exponential of each eigenvalue multiplied by $t$: $\lambda _{i}^{t}$. Multiply by an unknown matrix $B_{i}$. If the eigenvalues have an algebraic multiplicity greater than 1, then repeat the process, but multiply by a factor of $t$ for each repetition. If one eigenvalue had a multiplicity of three, then there would be the terms: $B_{i_{1}}\lambda _{i}^{t},B_{i_{2}}t\lambda _{i}^{t},B_{i_{3}}t^{2}\lambda _{i}^{t}$. Sum all terms. I cannot post this to the primary article without some additional sources. I'm sure it must be published somewhere, I just do not know where.

In our example we get: $A^{t}=B_{1_{1}}(3/4)^{t}+B_{1_{2}}t(3/4)^{t}+B_{2_{1}}1^{t}+B_{2_{2}}t1^{t}$.

So how can we get enough equations to solve for all of the unknown matrices? Increment $t$.

${\begin{aligned}IA^{t}=&B_{1_{1}}(3/4)^{t}+B_{1_{2}}t(3/4)^{t}+B_{2_{1}}+B_{2_{2}}t\\AA^{t}=&B_{1_{1}}(3/4)^{(t+1)}+B_{1_{2}}{(t+1)}(3/4)^{(t+1)}+B_{2_{1}}+B_{2_{2}}{(t+1)}\\A^{2}A^{t}=&B_{1_{1}}(3/4)^{(t+2)}+B_{1_{2}}{(t+2)}(3/4)^{(t+2)}+B_{2_{1}}+B_{2_{2}}{(t+2)}\\A^{3}A^{t}=&B_{1_{1}}(3/4)^{(t+3)}+B_{1_{2}}{(t+3)}(3/4)^{(t+3)}+B_{2_{1}}+B_{2_{2}}{(t+3)}\end{aligned}}$

Since the these equations must be true, regardless the value of $t$, we set $t=0$. Then we can solve for the unknown matrices.

${\begin{aligned}I=&B_{1_{1}}+B_{2_{1}}\\A=&(3/4)B_{1_{1}}+(3/4)B_{1_{2}}+B_{2_{1}}+B_{2_{2}}\\A^{2}=&(3/4)^{2}B_{1_{1}}+2(3/4)^{2}B_{1_{2}}+B_{2_{1}}+2B_{2_{2}}\\A^{3}=&(3/4)^{3}B_{1_{1}}+3(3/4)^{3}B_{1_{2}}+B_{2_{1}}+3B_{2_{2}}\end{aligned}}$

This can be solved using linear algebra (don't let the fact the variables are matrices confuse you). Once solved using linear algebra you have:

${\begin{aligned}B_{1_{1}}=&128A^{3}-336A^{2}+288A-80I\\B_{1_{2}}=&{\frac {64}{3}}A^{3}-{\frac {176}{3}}A^{2}+{\frac {160}{3}}A-16I\\B_{2_{1}}=&-128A^{3}+336A^{2}-288A+81I\\B_{2_{2}}=&16A^{3}-40A^{2}+33A-9I\end{aligned}}$

Plugging in the value for $A$ gives:

${\begin{aligned}B_{1_{1}}=&{\begin{pmatrix}0&0&48&-16\\0&0&-8&2\\0&0&1&0\\0&0&0&1\end{pmatrix}}\\B_{1_{2}}=&{\begin{pmatrix}0&0&{\frac {16}{3}}&-{\frac {8}{3}}\\0&0&-{\frac {4}{3}}&{\frac {2}{3}}\\0&0&{\frac {1}{3}}&-{\frac {1}{6}}\\0&0&{\frac {2}{3}}&-{\frac {1}{3}}\end{pmatrix}}\\B_{2_{1}}=&{\begin{pmatrix}1&0&-48&16\\0&1&8&-2\\0&0&0&0\\0&0&0&0\end{pmatrix}}\\B_{2_{2}}=&{\begin{pmatrix}0&1&8&-2\\0&0&0&0\\0&0&0&0\\0&0&0&0\end{pmatrix}}\end{aligned}}$

So the final answer would be:

${A}^{t}={\begin{pmatrix}1&t&{\frac {\left(24\,t-144\right)\,{2}^{2\,t}+\left(16\,t+144\right)\,{3}^{t}}{3\,{2}^{2\,t}}}&-{\frac {\left(6\,t-48\right)\,{2}^{2\,t}+\left(8\,t+48\right)\,{3}^{t}}{3\,{2}^{2\,t}}}\\0&1&-{\frac {\left(4\,t+24\right)\,{3}^{t}-3\,{2}^{2\,t+3}}{3\,{2}^{2\,t}}}&{\frac {\left(2\,t+6\right)\,{3}^{t}-3\,{2}^{2\,t+1}}{3\,{2}^{2\,t}}}\\0&0&{\frac {\left(t+3\right)\,{3}^{t-1}}{{2}^{2\,t}}}&-t\,{2}^{-2\,t-1}\,{3}^{t-1}\\0&0&t\,{3}^{t-1}\,{2}^{1-2\,t}&-{\frac {\left(t-3\right)\,{3}^{t-1}}{{2}^{2\,t}}}\end{pmatrix}}$

This method was taught as it is nearly the same procedure to calculate $exp(At)$ (useful for linear differential equations). Except that instead of incrementing $t$ to get additional equations and using $\lambda _{i}^{t}$ in the terms, one takes the derivative with respect to $t$ to generate additional equations and using $e^{(\lambda _{i}t)}$ in the terms.Mouse7mouse9 00:44, 31 January 2014 (UTC)

"Solving non-homogeneous recurrence relations" confusion

If

$P(x)=\sum _{n=0}^{\infty }p_{n}x^{n}$

is the generating function of the inhomogeneity, the generating function

$A(x)=\sum _{n=0}^{\infty }a(n)x^{n}$

of the inhomogeneous recurrence

$a_{n}=\sum _{i=1}^{s}c_{i}a_{n-i}+p_{n},\quad n\geq n_{r},$

with constant coefficients c_i is derived from

$\left(1-\sum _{i=1}^{s}c_{i}x^{i}\right)A(x)=P(x)+\sum _{n=0}^{n_{r}-1}[a_{n}-p_{n}]x^{n}-\sum _{i=1}^{s}c_{i}x^{i}\sum _{n=0}^{n_{r}-i-1}a_{n}x^{n}.$

If P(x) is a rational generating function, A(x) is also one. The case discussed above, where p_n = K is a constant, emerges as one example of this formula, with P(x) = K/(1−x). Another example, the recurrence $a_{n}=10a_{n-1}+n$ with linear inhomogeneity, arises in the definition of the schizophrenic numbers. The solution of homogeneous recurrences is incorporated as p = P = 0.

Is a(n) supposed to be $a_{n}$?

Where did s, $n_{r}$, or even r, come from? I thought that in this subsection, the inhomogeneity had been extended, from the finite polynomial of degree r, to an infinite series.

Jmichael ll (talk) 02:31, 21 July 2015 (UTC)

Stability definition

In the context of recurrence relations, stability generally refers to the propensity of the relative error (w.r.t. the wanted sequence) to diminish or grow, rather than (as the article currently states), the converge or divergence of the values of the iterates. See Abramowitz and Stegun, and J. C. P. Miller's comments ibid. --catslash (talk) 22:39, 3 August 2015 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Recurrence relation/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Comment(s)

Press [show] to view →

I think there must be an error in the example given for the recurrence relation for the Taylor series of a differential equation. The article says: This is not a coincidence. If you consider the Taylor series of the solution to a linear differential equation: $\sum _{n=0}^{\infty }{\frac {f^{(n)}(a)}{n!}}(x-a)^{n}$ you see that the coefficients of the series are given by the n-th derivative of f(x) evaluated at the point a. The differential equation provides a linear difference equation relating these coefficients. This equivalence can be used to quickly solve for the recurrence relationship for the coefficients in the power series solution of a linear differential equation. The rule of thumb (for equations in which the polynomial multiplying the first term is non-zero at zero) is that: $y^{[k]}\to f[n+k]$ and more generally $x^{m}*y^{[k]}\to n(n-1)(n-m+1)f[n+k-m]$ Example: The recurrence relationship for the Taylor series coefficients of the equation: $(x^{2}+3x-4)y^{[3]}-(3x+1)y^{[2]}+2y=0\,$ is given by $n(n-1)f[n+1]+3nf[n+2]-4f[n+3]-3nf[n+1]-f[n+2]+2f[n]=0\,$ or $-4f[n+3]+2nf[n+2]+n(n-4)f[n+1]+2f[n]=0.\,$ However, when I apply the rule for $x^{m}*y^{[k]}$ to the given equation, I get $n(n-1)^{2}f[n+1]+3n^{2}(n-1)f[n+2]-4f[n+3]-3n^{2}(n-1)f[n+1]-f[n+2]+2f[n]=0\,$ which is different to what is given. Am I missing a trick or is the example wrong? 85.138.151.35 (talk) 14:26, 22 January 2009 (UTC)Robert

Last edited at 14:26, 22 January 2009 (UTC). Substituted at 02:33, 5 May 2016 (UTC)

Definition of Recurrence relation - dependence on index n ?

The current article defines a recurrence relation as an equation that expresses one term $z$ of a sequence as function $f$ of previous terms. It is unclear whether the intent is to allow (or require) $f$ to also be explicitly a function of the index $n$ of the term $z$. (For example, can one define a recurrence relation without mentioning the index by saying that in any consecutive sequence of terms $x,y,z$ the relation $z=x^{2}-2xy$ holds? )

Since equations such as $z_{n}=2z_{n-1}-3nz_{n-2}$ are commonly accepted as recurrence relations, I assume the intent of the definition is to allow $f$ to depend explicitly on the index of the term on the left hand side of the equation. However, this raises the possibility that an equation like $z_{n}=n^{2}+n$ can qualify as a recurrence relation via a loophole in the definition. It can be regarded as $z_{n}=f(n,z_{n-1})=n^{2}+n$ where $f$ is a function that is constant with respect to $z_{n-1}$.

If we want to prohibit equations like $z_{n}=n^{2}+n$ from satisfying the definition of a recurrence relation, we need some language that excludes constant functions from counting as "functions of the previous terms".

Tashiro~enwiki (talk) 05:35, 4 August 2016 (UTC)

Solving homogeneous linear recurrence relations with constant coefficients: Solving via linear algebra

It appears to me that the explanation why eigenvector components are powers of λ, is mistaken. I.m.h.o, that relates to the special structure of matrix C, with all its rows (except for the first) consisting of just one instance of 1 (in a different column for each row) and zeroes everywhere else. When one calculates an eigenvector for a eigenvalue λ in such a system, this will indeed generate a vector with successive powers of λ. As I understand it, however, this has nothing to do with the fact that C only enlarges any of its eigenvectors - a statement that is true of any linear operator.Frandege (talk) 20:30, 21 August 2017 (UTC)

I agree with everything you have written. Here is a proof which I think explains why the eigenvectors have their specific shape (which agrees with your explanation).

Also, I find the usage of coefficients $c_{i}$ very confusing. At the beginning of the section, they are used as coefficients for the recurrence: $y_{n}=c_{n-1}y_{n-1}+c_{n-2}y_{n-2}+\cdots +c_{0}y_{0}.$. Later however they are used as coefficients to form a linear combination of the eigenvectors: ${\vec {y}}_{n}=C^{n}\,{\vec {y}}_{0}=c_{1}\,\lambda _{1}^{n}\,{\vec {e}}_{1}+c_{2}\,\lambda _{2}^{n}\,{\vec {e}}_{2}+\cdots +c_{n}\,\lambda _{n}^{n}\,{\vec {e}}_{n}$. I have the impression that these two sets of coefficients can not be the same. This is corroborated by the derivation I found here. : --Attila Kun (talk) 12:52, 18 February 2018 (UTC)

Short description

The current short description "Definition of each term of a sequence as a function of preceding terms" is not strictly accurate as initial term(s) are not so defined, and is too long: recommended size about 40 characters (WP:SHORTDES), currently 70). To save a few more characters, "each term" could be "terms" and "preceding" could be "earlier" but can we do better?  ~ RLO1729^💬 11:38, 30 March 2020 (UTC)

WP:SHORTDES says "A target of 40 characters has been suggested, but this can be exceeded when necessary". So, 40 is not a guideline, only a suggstion. My experience is that, in mathematical aticles, it is very often extremely diffult, and even impossible, to provide a useful short description. "Mathematical concept" or "theorem" appear often, but they are useful only for telling that the article is about mathematics. Moreover, when "theorem" appears in article's title, such a short description adds nothing. My experience is that, for mathematical articles, 40 is generally too short, specially when "mathematics" must appear in the short description because this is not clear from the title (for example, completion of a ring is not about jewellery–in this case the Wikidata short description is clearly not convenient, and I have not found any convenient one).

What precedes is for saying that it would be good to do better, but I find much more important to have something useful in many other mathematical articles. D.Lazard (talk) 13:46, 30 March 2020 (UTC)

Definition section change formatting

In wikipedia, it is customary to use either {{math|...}}, or <math>...</math> for mathematical expressions and the style between them is highly not recommended to change. Many sections of the article were without formatting (''...'' was used) and I changed it to <math>...</math>, that is, the style that prevailed in the article. However, the Definition section is formatted in {{math|...}} style and without discussion, it is not recommended to change it (although there are only 5 letters to change). Can I change the design of this section for uniformity in the article?

"Recursion(Mathematics)" listed at Redirects for discussion

An editor has identified a potential problem with the redirect Recursion(Mathematics) and has thus listed it for discussion. This discussion will occur at Wikipedia:Redirects for discussion/Log/2022 April 22#Recursion(Mathematics) until a consensus is reached, and readers of this page are welcome to contribute to the discussion. Steel1943 (talk) 06:01, 22 April 2022 (UTC)

Application to musical tuning theory

In § Applications, mention could be made of the use of recurrent sequences by Erv Wilson, Kraig Grady and others to tune musical scales that feature the use of combination tones of previous notes as subsequent scale degrees. However, doing this needs reliable sources, preferably third-party of course. My nice to-do list includes looking for such sources; but don't wait on me! yoyo (talk) 23:39, 29 October 2022 (UTC)

References for "Solving first-order non-homogeneous recurrence relations with variable coefficients"

Although the method described in References - Footnotes [3] is indeed nice, I would like to know if there is another reference (book or published article that can be quoted) that describes this method. MCarr (talk) 21:07, 27 May 2023 (UTC)

Notation of factorial as recurrence relation

@D.Lazard

In this edit summary you called the following notation “undefined notation”:

$x_{0}=1$

$x_{n+1}=nx_{n}$

However it is just standard notation, a clearer one in my opinion compared to the notation that you favoured, i.e.

$0!=1$

$n!=n(n-1)!$

It is also more on topic (the article is about recurrence relations after all); and with the second notation it might not be immediately clear that the factorial is, indeed, a recurrence relation.

The first notation has also the advantage of hinting immediately the manipulations that are possible simply by following the rules of recurrence relations. And so, for example, it can be easily seen that the factorial can also be rewritten as

$x_{0}=1$

$x_{1}=1$

$x_{n+1}={\frac {x_{n}^{2}+x_{n}x_{n-1}}{x_{n-1}}}$

And so on.

This is a relatively minor point, however I do favour the first notation, especially in an article like this one. --Grufo (talk) 01:11, 14 August 2024 (UTC)

The article does not use what you call a standard notation for the subject of the article. So, your change was definitively confusing. D.Lazard (talk) 09:03, 14 August 2024 (UTC)

The article does not use what you call a standard notation for the subject of the article: What do you mean? The article opens with this:

$F_{n}=F_{n-1}+F_{n-2}$

Then it goes on with this:

$x_{n+1}=rx_{n}(1-x_{n})$

How are these notations any different? And how are they closer to your notation than to mine? --Grufo (talk) 11:48, 14 August 2024 (UTC)

§ Logistic map is definitively not a model for a good Wikipedia style; I have edited this section.

Also, the syntax of ⁠$F_{n}=F_{n-1}+F_{n-2}$⁠ and ⁠$n!=n\cdot (n-1)!$⁠ are very similar, the main diference is that the index n is pleaced before the symbol of the sequence in the latter case and as a subscript of the symbol of the sequence in the former case. D.Lazard (talk) 13:07, 14 August 2024 (UTC)

I agree that with a bit of mental elasticity the number “5” in $5!$ can be seen as the index of a recurrence relation – provided that the reader knows that the factorial is a recurrence relation. But I believe that when dealing with recurrence relations – especially when the purpose is that of empathizing a recurrence – that style looks a bit unnatural; the natural way is to write the index in a subscript position, as in $a_{5}$ or $F_{5}$ or $x_{5}$, or similar notations. --Grufo (talk) 15:19, 14 August 2024 (UTC)