Talk:Lucas sequence

Condition on P and Q

To clear up any confusion - the correct condition on P and Q is

$P^{2}-4Q\neq 0$

as given by Paulo Ribenboim in My Numbers, My Friends. MathWorld incorrectly has the condition

$P^{2}-4Q>0$

but all the relations work equally well if P²-4Q is negative. Gandalf61 08:41, 5 May 2006 (UTC)

Clarification of opening

Lucas sequences were first studied by French mathematician Edouard Lucas.

Is this really true? In general, the sequences of convergents in simple continued fraction expansions of quadratic surds contain embedded Lucas sequences. I understand that Lucas generalized the notion, and wrote quite a few papers about his generalized sequences. But Joseph Louis Lagrange (d. 1813) solved the general problem posed by Pell's equation, and Euler studied the convergents of continued fractions long before Lagrange did, so I think this sentence is stretching the truth, at a minimum. DavidCBryant 23:09, 9 December 2006 (UTC)

Changed "first studied by" to "named after". Gandalf61 12:21, 10 December 2006 (UTC)

Thanks! Say, I noticed one other thing. Some of the equations in this article appear in a big font, and others are much smaller. (I'm talking about separate lines produced by a pair of <math></math> tags.) Is that intentional? Would it be OK if I fix them to all display in the larger font? DavidCBryant 14:09, 10 December 2006 (UTC)

Not intentional AFAIK, so feel free to fix ! Gandalf61 17:32, 10 December 2006 (UTC)

Comments on proposed merger

I disagree with the proposed merger of Lucas number into Lucas sequence. Lucas sequences encompass not just Lucas numbers but also Fibonacci numbers, Pell numbers, and in fact any sequence defined by a linear recurrence relation with a quadratic characteristic equation. Making Lucas numbers a special case by merging them into the Lucas sequence article would be anomalous and misleading. Gandalf61 09:40, 21 January 2007 (UTC)

In the german Wikipedia Lucas sequence and Lucas number are only in one article, because they have no different names in german. Both are Lucas-Folgen.

I disagree a merge of Lucas number and Lucas sequence too, because they are different, and have different names.

If someone would like to merge Lucas number to Fibonacci number, i would understand, and accept, because they are twins. --Arbol01 11:17, 21 January 2007 (UTC)

Do not merge the articles. Lucas sequences have wide application in cryptography, primality testing, etc. Lucas numbers are a special instance of a Lucas sequence; they're historically notable in their own right. DavidCBryant 12:39, 21 January 2007 (UTC)

I'm against a merger and agree with the above arguments. Lucas numbers have a similar name but don't have more reason to be in Lucas sequence than other instances of Lucas sequences with their own article. PrimeHunter 18:36, 21 January 2007 (UTC)

Not a problem, this is why I only suggested it. Arbol01: There are certain users who have a problem with Lucas numbers on the Fibonacci numbers page. It just seemed to me that as Fibonacci sequence redirects to Fibonacci number that Lucas number and Lucas sequence should be merged. I see that since I proposed the merger that a link has been added from Lucas number to Lucas sequence. I will remove the proposal. Danielklein 00:57, 24 January 2007 (UTC)

I think Fibonacci number is too long for details about Lucas numbers and other generalizations. If Lucas number should be merged anywhere (I don't support that), then I would prefer Generalizations of Fibonacci numbers (which needs some editing in the Lucas numbers section). PrimeHunter 13:57, 24 January 2007 (UTC)

Redoing opening and more

I think I can improve it. Note that it is incorrect as it stands. Lots of sequences satisfy a give recurrence but only two (not) all of them qualify as Lucas sequences.--Gentlemath (talk) 06:59, 22 February 2009 (UTC)

Looking a bit further I see that 1) Fibonacci is the case P=1 Q=1 (not Q=-1) as stated here (this might be the source of the 2) If P^2-4Q=0 we still have the sequences U and V, we just don't have the formulas. I'll fix this but I don't know if I'll get to the chart at the end.--Gentlemath (talk) 07:55, 22 February 2009 (UTC)

HUGE MESS

You can see changes I made then reverted. Basically there needs to be a choice made between

x_n=Px_{n-1} + Qx_{n-2} -OR- x_n=Px_{n-1} - Qx_{n-2}

pick one or the other. then get the charts and facts in shape. I think + is the usual choice but maybe not.

In the case D=0 we still have U and V defined .. just another way. Check if the (corrected) table of formulas works.

In any case I suggest a chart like

n .... U[n] ..... V[n]

0 .... 0 ........ 2

1 .... 1 ........ P

2 .... Q ........ P^2+2Q

3 .... PQ+Q .... P^3+3PQ

carried on a few more lines (of course the - choice would change things) cheers!--Gentlemath (talk) 08:35, 22 February 2009 (UTC)

Yes, Using the + definition we have

                                  2
                           2, P, P  + 2 Q

                           2       3
                       3, P  + Q, P  + 3 Q P

                     3           4        2      2
                 4, P  + 2 Q P, P  + 4 Q P  + 2 Q

                 4        2    2   5        3        2
             5, P  + 3 Q P  + Q , P  + 5 Q P  + 5 P Q

           5        3        2   6        4      2  2      3
       6, P  + 4 Q P  + 3 P Q , P  + 6 Q P  + 9 P  Q  + 2 Q

And the various relations appear to work independent of D=0 or D<>0

in the D=0 case U_n=n*s^{n-1} and V_n=2*S^{n} and all is well.--Gentlemath (talk) 08:56, 22 February 2009 (UTC)

The correct recurrence relation is

$x_{n}=Px_{n-1}-Qx_{n-2}\,.$

See, for example, the MathWorld definition. The incorrect recurrence relation was introduced by MFH on 14th February. I have fixed the article so that it uses the correct relation throughout. Gandalf61 (talk) 10:31, 22 February 2009 (UTC)

Sorry, except for the minor typo (the "+Q" instead of "-Q"), all I did (and I think it was a great improvement) was to create a first paragraph (this is the text [up to the first explicit line break] which you see when your cursor hovers over the link when you are using WP:NAVPOP - as most active wikipedians do) which summarizes the essential information of the article. IMHO this was very nice after my edit (modulo correcting +Q to -Q), and it is a huge mess now. All those using WP:NAVPOP are invited to compare the two versions by hovering over the title line ("Revision as of..."). But not only the NAVPOP is now completely useless, but also the first phrase is now simply wrong, since a Lucas sequence is not one of two sequences, but there is an infinite number of Lucas sequences. Please consider putting back the introduction as it stood after my edit (except for the + sign). At least avoid putting empty lines around a displayed equation which is in the middle of a paragraph. And bear in mind the WP:NAVPOP aspect when designing the first paragraph (not: section -- only the text up to the first explicit line break (as it occurs also for a displayed equation) is visible). Thanks in advance. — MFH:Talk 21:00, 27 February 2009 (UTC)

I have made some changes to the opening paragraph that, I hope, address most of your concerns. Gandalf61 (talk) 14:38, 28 February 2009 (UTC)

Thanks, that's much better... but what exactly do you dislike in that version (except for the "+Q", of course)? I still think it contains more info & useful links (accessible via WP:NAVPOP) than the current version and is at the same time "smoother" to read. — MFH:Talk 18:25, 28 February 2009 (UTC)

Ok, much better than before and better than after my revisions. I do have to note that Mathworld is almost entirely the work of one guy Eric Weisstein. He is a great guy and the site has much of value, but he makes his own choices on terminology. Most is standard but some is not and some is even kind of misguided.

The reference Proofs That Really Count (a fantastic book by the way) can be viewed through Google books

(try http://books.google.com/books?id=FXLGzXwbwIAC&pg=PA17&dq=lucas+sequence&lr=&ei=4JahScHgD5bCyQSz4KVa#PPA35,M1 )

and on page 35 one finds:

Page 35 Definition Given integers s and t, the Lucas sequence of the first kind is defined by U_0 = 0, U_1 = 1 and for n > 2, U_n = sU_{n-1} + tU_{n-2} For combinatorial ...

The point being that there and in a few other academic sources I consulted I found +. It does not actually matter as long as one is consistent so I am not going to change it. Note too that nothing bad happens when D=0 except that you can't use the formula that requires dividing by a-b.

--Gentlemath (talk) 18:38, 22 February 2009 (UTC)

Final thought (for now) All the examples use Q=-1. Wouldn't it be nicer to use addition and Q=1? Remember that this is the case d=2 of x_n=c_1x_{n-1}+c_2x_{n-2}+...+c_dx_{n-d}.--Gentlemath (talk) 22:54, 22 February 2009 (UTC)

Not Just MathWorld. Paulo Ribenboim uses the "-" convention in Chapter 1 of My Numbers, My Friends. If you have references for the "+" convention, we could mention that as well, but we must be careful not to confuse the reader and return to the "huge mess" that you were complaining about at the start of this thread. Gandalf61 (talk) 07:28, 23 February 2009 (UTC)

I looked at recent articles in math journals. Both the + convention and the - convention show up. I found more that said things like x_n=s x_n-1 + t x_n-2 but the articles using P and Q for the parameters do tend to be x_n=Px_n-1 - Qx_n-2. So I agree that it should stay as it is. The reader who likes the + convention can just substitute -Q for Q which amounts to changing the first 17 - signs (not including subscripts) into + signs and all the -1 in the examples to 1. --Gentlemath (talk) 20:08, 23 February 2009 (UTC)

Mess (cont'd)

There are lots of trivial relations in this article that are not at all specific to Lucas sequences, but belong to Recurrence_relation#Solving_generally. While in Ribenboim's book for example the case of real-valued terms is considered, I think that the properties that essentially make a 2nd order const.coeff recurrence a "Lucas sequence" are

• P²≠4Q,
• initial terms are (0, 1), resp. (2, P).

So it is confusing when the "general solution x_n" is introduced later on in the article (and in particular the case D=0), while the introducing phrase is IMHO unnecessarily overcharged by notations U_n(P,Q) and V_n(P,Q).— MFH:Talk 13:01, 3 March 2009 (UTC)

There isn't lots of anything in this article because it is pretty short. One would usually assume that P and Q are relativey prime integers since their gcd divides all the terms after the first two. Then P^2-4Q<>0 rules out exactly one case, P=2 and Q=-1. It is not that interesting but all the relations hold, so what is lost by excluding it. Which relations do you think should be removed? I support changing U_n(P,Q) to U_n in more places (maybe all) but I'll let someone else do that. I have tracked down the history (E.L. Dickson History of Theory of numbers Vol I chap XVII) in brief, Lucas employed the roots a and b of x^2-Px+Q=0 (where P & Q are relatively prime integers) to define the two sequences U and V. The main goal was to to use the U to study primes. That is where some of those relations come in. I'm not sure if all that detail is needed. --Gentlemath (talk) 06:27, 6 March 2009 (UTC)

Credit where credit is due

Since Lucas himself used the letters P and Q with x^2=PX-Q, that is surely the appropriate convention. (although he may have used lower case u and v). I think that the article as it currently is in MathWorld is just about perfect. It includes just enough identities for fast calculation and mentions the important fact that primality proof is an important motivation with, again, just enough details to say why. (Actually I'd like to see a 127 by 127 binary array proving 2^127-1 is prime ...)

This article at one point incorrectly called any integer sequence satisfying a 2nd order homogenous linear recurrence a Lucas Sequence. In correcting that I left in that it is reasonable to use U and V as a basis for the set of all solutions. If the roots a and b are integers then obviously we would prefer a^n and b^n. I agree that that could come out although it does not lengthen things much. I figured better to transition it to a minor detail, let it rest and then let it either stay or evaporate completely. I think that 2nd order homogenous linear recurrences don't have a nice treatment in Wikipedia so it might be nice to create one before erasing the few lines devoted to it here. --Gentlemath (talk) 20:03, 6 March 2009 (UTC)

Fibonnacci and Lucas sequences

I can't understand this article because it's written for people who already know what it means, but it says:

Famous examples of Lucas sequences include the Fibonacci numbers, Pell numbers, Lucas numbers and Jacobsthal numbers.

The article on the rank-size distribution (concerning the size of cities in a country or region) says

A special case of the Fibonacci sequence is the Lucas sequence consisting of these sequentially additive numbers 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, …

which seems to contradict this article. In particular I get the impression that the Lucas sequence is sort of a family of sequences, whereas the article on rank-size distribution seems to assert that the Fibonnaci sequence is more general and that there is only one Lucas sequence which follows that pattern.

Am I right in suspecting the other article is wrong? Would the following be a better re-write:

Similar to the Fibonnaci sequence is the sequence consisting of the sequentially-additive numbers 1, 3, 4, ... (cf. Lucas sequences).

There would also be the occasional consequential change later on (e.g. changing “the Lucas sequence as above” to “the sequence (as) above”).

Can anyone clarify this? Thanks!

—Felix the Cassowary 11:03, 1 September 2009 (UTC)

The numbers 1, 3, 4, 7, 11, ... are Lucas numbers. Both Fibonacci numbers and Lucas numbers are examples of the more general idea of a Lucas sequence. The link in rank-size distribution should point to the Lucas number article, not the Lucas sequence article - I have fixed it. Gandalf61 (talk) 11:27, 1 September 2009 (UTC)

For internal consistency, the Wikipedia article on public-key cryptography should reference the Lucas-based cryptosystems cited among the applications in this Lucas sequence article. Peter J. Smith.118.92.203.118 (talk) 10:03, 17 March 2013 (UTC)

A cool pattern

I found a cool pattern with sequences with the recurrence x_n=3*x_n-1+x_n-2. There are a lot of sequences starting with two 1-digit numbers that have 8-digit numbers of the form ABCDAECD. Here are some examples.

1, 1, 4, 13, 43, 142, 469, 1549, 5116, 16897, 55807, 184318, 608761, 2010601, 6640564, 21932293, 72437443...

2, 5, 17, 56, 185, 611, 2018, 6665, 22013, 72704, 240125, 793079, 2619861, 8651165, 28572857, 94369736...

That is a very interesting pattern! Bobby Jacobs (talk) 18:50, 14 April 2017 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Lucas sequence. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20150202074230/http://www.joye.site88.net/papers/JQ96lucas.pdf to http://www.joye.site88.net/papers/JQ96lucas.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 01:32, 8 January 2018 (UTC)

Where to find an explanation of analog of exponentiation via repeated squaring method for U(1,-1) (Fibonacci)

The article section mentions "analog of exponentiation by repeated squaring". The concept used for this is similar (using bits of n as powers of 2), but it is not quite exponentiation or squaring. Example code to calculate Fibonacci(n) in O(log(n)) time. In some cases, p is used instead of c and q is used instead of d.

uint64_t fib(uint64_t n)
{
    uint64_t a, b, c, d;
    a = d = 1;
    b = c = 0;
    while (1) {
        if (n & 1) {
            uint64_t bd = b*d;
            b = bd + a*d + b*c;
            a = bd + a*c;
        }
        n >>= 1;
        if (n == 0)
            break;
        {
            uint64_t dd = d*d;
            d = dd + 2*d*c;
            c = dd + c*c;
        }
    }
    return b;
}

I had to create my own derivation for this code, as I could not find a reference for this anywhere. I started with the Lucas sequence relations, and used them to derive the algorithm for the code above.

Lucas sequence relations:

fib(m+1) = fib(m) + fib(m-1)
fib(m+n) = fib(m+1) fib(n) + fib(m) fib(n-1)
fib(2m)  = fib(m) lucas(m) = fib(m) (fib(m+1) + fib(m-1)) = fib(m+1) fib(m) + fib(m) fib(m-1)

initial state
c = fib(0) = 0
d = fib(1) = 1

for each iteration, p = 2^i
c = fib(p-1)
d = fib(p)

d' = fib(2p)
   = fib(p+1) fib(p) + fib(p) fib(p-1)
   = (fib(p) + fib(p-1)) fib(p) + fib(p) fib(p-1)
   = fib(p) fib(p) + fib(p) fib(p-1) + fib(p) fib(p-1)
   = fib(p) fib(p) + 2 fib(p) fib(p-1)
   = d d + 2 d c

c' = fib(2p-1) = fib(p+p-1)
   = fib(p+1) fib(p-1) + fib(p) fib(p-2)
   = (fib(p) + fib(p-1)) fib(p-1) + fib(p) (fib(p) - fib(p-1))
   = fib(p-1) fib(p) + fib(p-1) fib(p-1) + fib(p) fib(p) - fib(p) fib(p-1)
   = fib(p) fib(p) + fib(p-1) fib(p-1)
   = d d + c c

initial state
a = fib(-1) = 1
b = fib( 0) = 0

during the calculation, m = current cumulative bits of n 
a = fib(m-1)
b = fib(m)

when a bit of n == 1, then a and b are updated:
b' = fib(m+p)
   = fib(m+1)fib(p) + fib(m)fib(p-1)
   = (fib(m) + fib(m-1))fib(p) + fib(m)fib(p-1)
   = fib(m)fib(p) + fib(m-1)fib(p) + fib(m)fib(p-1)
   = bd           + ad             + bc

a' = fib(m-1+p)
   = fib(m)fib(p) + fib(m-1)fib(p-1)
   = bd           + ac

Rcgldr (talk) 10:50, 21 February 2020 (UTC)