 mersenneforum.org Divisibility sequences based on recurrence relations
 Register FAQ Search Today's Posts Mark Forums Read 2017-12-21, 00:19 #1 carpetpool   "Sam" Nov 2016 2·163 Posts 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.   2017-12-21, 00:42   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by carpetpool 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.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post JM Montolio A Miscellaneous Math 3 2018-02-27 16:11 carpetpool Information & Answers 0 2017-11-28 07:44 fivemack Factoring 7 2007-08-04 17:32 Unregistered Information & Answers 2 2007-01-18 17:13 jinydu Puzzles 6 2004-05-15 14:02

All times are UTC. The time now is 08:04.

Mon Jan 18 08:04:53 UTC 2021 up 46 days, 4:16, 0 users, load averages: 2.00, 2.18, 2.12