Proving Conjectures About the Binet Formula for Q(\sqrt{k})

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