mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Combinatorics & Combinatorial Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=112)
-   -   Divisibility sequences based on recurrence relations (https://www.mersenneforum.org/showthread.php?t=22811)

 carpetpool 2017-12-21 00:19

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.

 science_man_88 2017-12-21 00:42

[QUOTE=carpetpool;474469]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.[/QUOTE]
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.

 All times are UTC. The time now is 21:45.

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