Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The dumb conjecture of the day

  1. May 23, 2008 #1
    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].
  2. jcsd
  3. May 23, 2008 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
  4. May 23, 2008 #3
    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.
  5. May 23, 2008 #4
    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).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook