The dumb conjecture of the day

  • Thread starter dodo
  • Start date
  • #1
695
2
Let [tex]Q(\sqrt{k})[/tex], for some positive integer k, be the extension of the field of rationals with basis [tex](1, \sqrt{k})[/tex]. For example, in [tex]Q(\sqrt{5})[/tex] the element [tex]({1 \over 2}, {1 \over 2})[/tex] is the golden ratio = [tex]{1 \over 2} + {1 \over 2}\sqrt{5}[/tex].

Given an extension [tex]Q(\sqrt{k})[/tex], let [tex]B(n)[/tex] denote the 'Binet formula',
[tex]B(n) = {{p^n - (1-p)^n} \over \sqrt k}[/tex], n = 0, 1, 2, ...​
where [tex]p = ({1 \over 2}, {1 \over 2})[/tex].

Conj. 1: [tex]B(n)[/tex] produces only integers, iif [tex]k \equiv 1 \ ("mod" \ 4)[/tex].

Conj. 2: When [tex]k \equiv 1 \ ("mod" \ 4)[/tex], [tex]B(n)[/tex] is the closed-form formula for the recurrence sequence
[tex]x_n = x_{n-1} + A \; x_{n-2}[/tex], n = 2, 3, 4, ...​
[tex]x_0 = 0, \ \ x_1 = 1[/tex]​
with [tex]A = {{k - 1} \over 4}[/tex].
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Isn't the second conjecture a straightforward exercise? And you don't even have to bother solving the ordinary linear difference equation: you already know the (putative) solution! (Why do you have the congruence condition on k for conjecture 2?)

And isn't conjecture 1 a trivial consequence of conjecture 2?


I suppose one thing might help to see conjecture 2: if it's right, then [itex]p^n[/itex] and [itex](1-p)^n[/itex] would be a basis for the solution space to the unconstrained version of your difference equation.
 
  • #3
695
2
I'm not sure I follow. (And in any case it's not trivial to me.) :D

As I see it, the first conjecture is a necessary previous step, for the second to be applicable. Possibly because I was interested in recurrence sequences returning only integers and with A = 1, 2, 3, ..., and frankly did not pay attention to the fact that B(n) could in fact be also the closed form for rational values of A and rational-producing sequences.

I'll try to digest what you're saying.
 
  • #4
32
0
There is a generalised Binet formula for the recurrence relation G(n) = aG(n-1) + bG(n-2), which explains much more than the problem raised.
The system does not allow me to post URLs to other sites as I have made less than 15 posts(why ???), but googling "generalised fibonacci" helps, and I also give a "traditional" reference:
Vella, A. and Vella, D. (2006) Calculating exact cycle lengths in the generalised Fibonacci sequence modulo p. Math. Gaz. 90 (available on the internet).
 

Related Threads on The dumb conjecture of the day

Replies
9
Views
9K
Replies
1
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
2
Replies
38
Views
14K
  • Last Post
Replies
3
Views
4K
Replies
16
Views
4K
Replies
11
Views
1K
Replies
1
Views
2K
  • Last Post
4
Replies
93
Views
13K
Top