The dumb conjecture of the day

dodo

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].

Hurkyl

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.

dodo

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.

huba

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).