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 5178 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
Dartmouth NS

2·3·23·61 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool carpetpool 1 2022-02-08 05:20 JM Montolio A Miscellaneous Math 3 2018-02-27 16:11 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 23:59.

Sat Jan 28 23:59:46 UTC 2023 up 163 days, 21:28, 0 users, load averages: 1.16, 1.05, 1.00

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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔