The dumb conjecture of the day

[Dodo]

Let Q(\sqrt{k}), for some positive integer k, be the extension of the field of rationals with basis (1, \sqrt{k}). For example, in Q(\sqrt{5}) the element ({1 \over 2}, {1 \over 2}) is the golden ratio = {1 \over 2} + {1 \over 2}\sqrt{5}.

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

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

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

[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 p^n and (1-p)^n 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).