Talk:Recurrence relation

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class Mid Priority  Field: Algebra
One of the 500 most frequently viewed mathematics articles.

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

Contents

[edit] 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)

[edit] 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 an = rn."


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.


[edit] 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)
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)

[edit] 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

[edit] 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 λ1 is r. The characteristic equation has degree n. Finally, the numbers c1, …, cn 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} - 16 a_{n-3} - 16 a_{n-4} + 32 a_{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: an = 2n, an = n2n, an = n22n, an = ( − 2)n and an = n( − 2)n. The general solution is
\begin{align} a_n &= C_1 2^n + C_2 n2^n + C_3 n^22^n + C_4 (-2)^n + C_5 n(-2)^n \\ &= (C_1 + C_2n + C_3n^2) 2^n + (C_4+C_5n) (-2)^n. \end{align}
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)

[edit] 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)