mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Combinatorics & Combinatorial Number Theory

Reply
 
Thread Tools
Old 2017-12-21, 00:19   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

311 Posts
Post Divisibility sequences based on recurrence relations

Recall the two types of divisibility sequences which are primarily involved in Lucas Sequences:

For U(n), if r divides s, then U(r) divides U(s).

For V(n), if r divides s, and r/s is odd, then V(r) divides V(s).

Most divisibility sequences terms U(n) and V(n), if not all, are generated by a recurrence relation of order n, meaning the first n terms (denoted [a1,a2,...an] of the sequence are given, and the rest of the terms depend on the past n previous terms.

The question is, for any recurrence relation of order n, are there finitely or infinitely many starting values or initial terms [a1,a2,...an] such that a(n) has the divisibility properties as U(n)? The same question can be asked about V(n).

For example, consider the recurrence relation

a(n)=a(n-1)+a(n-2) with starting values a(1) and a(2). Are there infinitely many pairs of numbers {a(1), a(2)} such that a(n) is a U(n) divisibility sequence, and there is also a corresponding V(n) sequence?

The only values I am aware which make this true is {1, 1} and {1, 3}

If a(1) = 1, and a(2) = 1, then a(n) is a divisibility sequence such that if r divides s, then a(r) divides a(s) (The U(n) sequence). These are the Fibonacci Numbers. The corresponding V(n) sequence has starting values a(1) = 1, and a(2) = 3.

Are there any more (two) sets values a(1) and a(2) which form divisibility sequences of the first kind, U(n), and the second kind V(n), with a(n)=a(n-1)+a(n-2) for n > 2? Consider this problem for all fixed recurrence relations of any order.

The same idea goes with a(n)=a(n-1)+a(n-2)+a(n-3), for instance, except given the first three starting values a(1), a(2) and a(3).
j
Any help, comments, suggestions appreciated. Thank you.
carpetpool is offline   Reply With Quote
Old 2017-12-21, 00:42   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by carpetpool View Post
Recall the two types of divisibility sequences which are primarily involved in Lucas Sequences:

For U(n), if r divides s, then U(r) divides U(s).

For V(n), if r divides s, and r/s is odd, then V(r) divides V(s).

Most divisibility sequences terms U(n) and V(n), if not all, are generated by a recurrence relation of order n, meaning the first n terms (denoted [a1,a2,...an] of the sequence are given, and the rest of the terms depend on the past n previous terms.

The question is, for any recurrence relation of order n, are there finitely or infinitely many starting values or initial terms [a1,a2,...an] such that a(n) has the divisibility properties as U(n)? The same question can be asked about V(n).

For example, consider the recurrence relation

a(n)=a(n-1)+a(n-2) with starting values a(1) and a(2). Are there infinitely many pairs of numbers {a(1), a(2)} such that a(n) is a U(n) divisibility sequence, and there is also a corresponding V(n) sequence?

The only values I am aware which make this true is {1, 1} and {1, 3}

If a(1) = 1, and a(2) = 1, then a(n) is a divisibility sequence such that if r divides s, then a(r) divides a(s) (The U(n) sequence). These are the Fibonacci Numbers. The corresponding V(n) sequence has starting values a(1) = 1, and a(2) = 3.

Are there any more (two) sets values a(1) and a(2) which form divisibility sequences of the first kind, U(n), and the second kind V(n), with a(n)=a(n-1)+a(n-2) for n > 2? Consider this problem for all fixed recurrence relations of any order.

The same idea goes with a(n)=a(n-1)+a(n-2)+a(n-3), for instance, except given the first three starting values a(1), a(2) and a(3).
j
Any help, comments, suggestions appreciated. Thank you.
The parity of different parts of the recurrence will affect things, for linear and polynomial recurrences. This is because, the parity of coefficients decide how often the terms divide by 2 etc.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A great universal divisibility rule JM Montolio A Miscellaneous Math 3 2018-02-27 16:11
Sieve for divisibility sequences carpetpool Information & Answers 0 2017-11-28 07:44
More relations mean many more relations wanted fivemack Factoring 7 2007-08-04 17:32
Linear recurrence on elliptic curve Unregistered Information & Answers 2 2007-01-18 17:13
Recurrence Equation jinydu Puzzles 6 2004-05-15 14:02

All times are UTC. The time now is 18:35.

Mon Sep 28 18:35:38 UTC 2020 up 18 days, 15:46, 1 user, load averages: 2.37, 2.37, 2.20

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.