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

2 number theory problems

  1. Jun 1, 2010 #1
    I have wrestled with the following two problems for a couple of hours each and have been successful. Now I am interested in how a more experienced mathematician would go about solving these.

    I encourage you to look past my lack of latex skills (lol), and do your best with the attachment I poorly put together.

    A note about the second problem, If anyone is unaware F denotes the Fibonacci numbers and L denotes the Lucas numbers. Second, the term on the left side is a little blurry but it says the 2n Fibonacci number. Also I challenge you to solve this second problem without strong induction. Which I semi-managed to do. I proved a secondary result with strong induction then used that result to use regular induction on the main problem.

    Attached Files:

  2. jcsd
  3. Jun 2, 2010 #2
    I have not completely worked out the first one, but I would try to form a one-to-one correspondence between the nonzero integers in base 3 and the nonzero integers in the form given by the problem.

    For the second, induction seems like a good way to go. However, if you have derived the closed form formulas for both, the result follows immediately.
  4. Jun 2, 2010 #3
    First problem:

    The way I proved it was to prove for a fixed s, every integer in n with absolute value less than or equal to [itex]3^0 + 3^1 + \cdots + 3^s[/itex] can be expressed uniquely in the form:
    [tex]\sum_{j=0}^s c_j 3^j[/tex]
    with [itex]c_j \in \{-1,0,1\}[/itex] (I don't require that c_s is non-zero, since if it is we can just pick the largest j with c_j non-zero, and if all c_j are 0, then we are in the exceptional case where n=0).

    First proving uniqueness suppose:
    [tex]\sum_{j=0}^s c_j 3^j = \sum_{j=0}^s d_j 3^j[/tex]
    with [itex]c_j, d_j \in \{-1,0,1\}[/itex]. You can show [itex]c_j=d_j[/itex] for all j.

    [tex]C_s = \left\{\sum_{j=0}^s c_j 3^j | c_j \in \{-1,0,1\}\right\}[/tex]
    Try to work out:
    1) How many elements are in C_s?
    2) What is the maximum and minimum element of C_s?
    When you answer these you should be able to show that C_s = {-N,-N+1,...,N-1,N} where
    [tex]N = 3^0 + 3^1 + \cdots + 3^s[/tex]
  5. Jun 2, 2010 #4
    Second problem:

    I assume you know the identity (otherwise you can easily show it):
    [tex]L_n = F_{n-1} + F_{n+1}[/tex]
    Then your identity is equivalent to:
    [tex]F_{2n} = F_nF_{n+1}+F_nF_{n-1}[/tex]
    Now let us strengthen to induction hypothesis to also say:
    [tex]F_{2n+1} = F_{n+2}F_{n+1}-F_nF_{n-1}[/tex]
    Then you can perform a normal inductive argument (there are some slightly messy calculations, but unless you already know some identities involving Lucas numbers and Fibonacci numbers I don't immediately see a cleaner way).
  6. Jun 2, 2010 #5
    Thanks for the reply rasmhop. One question.

    In one element of C_s, there are S terms. Each term may be assigned either -1, 0, or 1. Thus there are 3^s combinations and C_s includes 3^s elements. But if your right, C_s should include 2N+1 elements. Therefore I can conclude that not every integer (absolute value) less than N can be expressed in your form.

    Who is at fault here?
  7. Jun 2, 2010 #6
    0,1,2,...,s are s+1 numbers so there are s+1 terms, and thus C_s contains 3^(s+1) elements.

    The maximal value of an element of C_s is:
    [tex]N=3^0 + 3^1 + \cdots + 3^s = \frac{3^{s+1}-1}{3-1} = \frac{3^{s-1}-1}{2}[/tex]
    and the minimal is -N. 2N+1 = 3^(s+1).
  8. Jun 2, 2010 #7
    Thanks for showing me the light lol. I always forget about that zero, which hurt me a lot on exams working with convergence.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook