1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A Fibonacci type sequence

  1. Jun 30, 2006 #1
    Let g(n) = 2g(n-1) + g(n-2), g(0)=0, g(1)=1.
    The explicit formula is g(n) = ((1+t)^n - (1-t)^n) / (2t), where t is sqrt(2).

    Let h(n) = the sum of the first n+1 terms of g, ie h(n) = g(0)+g(1)+...+g(n).
    Then a possible recursive definition of h(n) will be similar to that of g(n), except that 1 will have to be added to it each time:

    h(n) = 2h(n-1) + h(n-2) + 1, h(0)=0, h(1)=1.

    How can I find (or what is) the explicit formula for h(n), please?
  2. jcsd
  3. Jun 30, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You can find h(n) directly -- you have the expression for g(n), and you know how to compute that sum explicitly.

    If you really wanted to do it from the recursion, then you could modify h to get a simpler expression. For example, what would the recursion for k(n) = h(n) + a look like? Then, maybe you can find an a that makes it simple!
  4. Jun 30, 2006 #3
    I admit I still haven't found the explicit formula for h(n), but, before finding it, there are other issues that seem to be interesting.

    For instance, it seems that g(n) is approximately (h(n-1)+1/2)*sqrt(2), and the higher n, the closer the value of that formula is to g(n).
    For example, h(6) = 0 + 1 + 2 + 5 + 12 + 29 + 70 = 119, and 119.5*sqrt(2) = 168.9985..., while g(7) = 169.

    Further, let G(n,m) = 2G(n,m-1) + G(n,m-2), G(n,0)=2^n, G(n,1)=2^n.
    G(0,m) : 1, 1, 3, 7, 17, 41, 99, ...
    G(1,m) : 2, 2, 6, 14, 34, 82, 198, ...
    G(2,m) : 4, 4, 12, 28, 68, 164, 396, ...
    G(3,m) : 8, 8, 24, 56, 136, 328, 792, ...
    Now, it seems, G(n, m) = (h(m-1)+1/2)*2^{n+1}.

    For example, with n= 3 and m = 6,
    G(3,6) = 792, and h(6-1)=49, and indeed 49.5 * 2^4 = 792.
    Last edited: Jul 1, 2006
  5. Jun 30, 2006 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    h(n) is just the sum of two geometric progressions. You can evaluate those.
  6. Jun 30, 2006 #5
    Yes, thanks, of course, then I get h(n) = ((1+t)^{n+1} + (1-t)^{n+1} - 2) / 4, where t is sqrt(2).
  7. Jul 1, 2006 #6
    and then G(n,m) = ( (1+sqrt(2))^m + (1-sqrt(2))^m ) * 2^{n-1}.
  8. Jul 6, 2006 #7


    User Avatar
    Science Advisor
    Homework Helper

    The first sequence is the Pell numbers, A000129. How did the second sequence come up, out of curiosity?
  9. Jul 8, 2006 #8
    I myself am familiar with this sequence (h(n)) and it is related to well known sequences in the Online Encyclopedia of integer sequences. Let A(n) = A000129 also the sequence b(n) = A001333. Then a(n)*b(n) = s(n) = A001109 where s(n) squared are equal to h(2n)*(h(2n)+1)/2, i.e., the square triangular numbers. Also h(n)=(b(n)-1)/2.
  10. Jul 8, 2006 #9


    User Avatar
    Science Advisor

    If you didn't know that h(n) is the sum of two geometric sequences, you can use generating functions or the method of undetermined coefficients.
    Last edited: Jul 8, 2006
  11. Jul 9, 2006 #10
    Thanks for all the help and the useful comments.

    Sorry for not answering your question earlier, CRGreathouse, but I cannot provide any revealing answer - I think I was playing with the numbers in Excel, searching for patterns.

    Orthodontist, thanks, but I haven't heard about the method of undetermined coefficients. As far as generating functions are concerned, I do not find them very easy:

    For instance, consider u(n) = 6u(n-1)-u(n-2), u(0)=1, u(1)=5 (a fascinating sequence, giving the values of the hypothenuse, or c, in Pythagorean triples a^2+b^2=c^2, where |a-b|=1, see http://www.research.att.com/~njas/sequences/A001653 ).

    As far as generating functions are concerned, I can get as far as this:

    (i) u(x) = u(0) + u(1)*x + u(2)*x^2 + ... + u(n)*x^n + ...

    multiply (i) by -6x:

    (ii) -6x*u(x) = -6*u(0)*x - 6*u(1)*x^2 - 6*u(2)*x^3 - ... - 6*u(n)*x^{n+1} - ...

    multiply (i) by x^2:

    (iii) x^2*u(x) = u(0)*x^2 + u(1)*x^3 + u(2)*x^4 + ... + u(n)*x^{n+2} + ...

    Then add (i), (ii), and (iii):

    u(x)*(1 - 6x + x^2) = u(0) + x*(u(1) - 6*u(0)) + x^2 * (u(2) - 6*u(1) + u(0)) + ... + x^n * ( u(n) - 6*u(n-1) + u(n-2) ) + ...

    As u(0)=1 and u(1)=5, I get

    u(x) = (1 - x)/(1 - 6x + x^2).

    I can of course find the roots of x^2 - 6x + 1:
    a = 3 + 2*sqrt(2), and
    b = 3 - 2*sqrt(2).

    But I am stuck there. How do I get to the explicit formula?
  12. Jul 9, 2006 #11


    User Avatar
    Science Advisor

    Instead of u(x) I guess you mean f(x). You have the roots a and b, so your fraction is
    Now you expand by partial fractions to get
    where [tex]A = \frac{1-a}{a-b}[/tex]
    and [tex]B = \frac{1-b}{b-a}[/tex]
    Dividing top and bottom by -a or -b for your two fractions, you can see that the solution sequence is the sum of two geometric sequences, one with first term -A/a and ratio 1/a, and the other with first term -B/b and ratio 1/b, which checks out.

    By the way, your method is a little weird. The way I learned it, you multiply the whole thing through by x^n, sum over all n, rewrite in terms of the generating function f(x), then solve for f(x).

    The method of undetermined coefficients works by knowing (from a table or memory) the general forms of sequences up to constant coefficients, and then solving for the coefficients. In this case u is a homogeneous sequence, where only constant multiples of u appear in the definition, so one solution of u(n) is Crn for some C and r. Substitute that back into the sequence definition and simplify, giving you the equation
    r2-6r+1 = 0
    So r happens to be either a or b that you mentioned earlier. The general solution for the series is
    u(n) = C1a^n+C2b^n. Use the fact that you know the first few terms of the series to solve for C1 and C2.
    C1 + C2 = 1
    aC1 + bC2 = 5
    C2 = [tex]\frac{5-a}{b-a}[/tex]

    C1 = [tex]\frac{b-5}{b-a}[/tex]
    and now you have determined the sequence.
    Last edited: Jul 9, 2006
  13. Jul 11, 2006 #12
    Thank you.
    Then, using the generating function method, with a= 3 + 2*sqrt(2), and b = 3 - 2*sqrt(2),
    A = (-1-sqrt(2)) / (2*sqrt(2)), and B = (1-sqrt(2)) / (2*sqrt(2)),

    and so

    u(n) = -A/a^{n+1} - B/b^{n+1}.

    This works, but it is not as nice as I thought it would be, especially with the (n+1)th power in the denominators.

    However, going back to an interesting property of the u(n) sequence, I wonder if there is a proof for the following statement (if true):

    The sequence u(n) = 6*u(n-1) - u(n-2), u(0)=1, u(1)=5 generates all and only the integer solutions in c of a^2 + b^2 = c^2 where |a-b|=1.
  14. Jul 12, 2006 #13
    u(n) = 6*u(n-1)-u(n-2), u(0)=1, u(1)=1 (this yields the same sequence as with the choices u(0)=1 and u(1)=5) is also the difference sequence of the sequence of the square roots of square triangular numbers:
    S(n) = 6*S(n-1)-S(n-2), S(0)=0, S(1)=1, that is


    This has two consequences:
    (1) another explicit formula for u(n) can be simply derived from the explicit formula of S(n),
    (2) the statement in post 12 can be rephrased as : the difference between the square roots of two consecutive square triangular numbers is the hypothenuse, or c, of a Pythagorean triple a^2 + b^2 = c^2, where |a-b| = 1.

    Just to note that yet another formula seems to work:

    u(n) = ( (1 + sqrt(2))^{2*n-1} - ((1 - sqrt(2))^{2*n-1} ) / ( 2*sqrt(2) ), for the same sequence as
    u(n) = 6*u(n-1)-u(n-2), u(0)=1, u(1)=1 .

    Sorry if I just repeated something that has already been stated somewhere (for instance there is a lot of related info, with links and references, at http://www.research.att.com/~njas/sequences/A001653 ).
    Last edited: Jul 13, 2006
  15. Jul 15, 2006 #14
    I have found something that may be well known, and so I would appreciate either a link or reference, or some help towards proving this:

    f(n) = a*f(n-1) + b*f(n-2), f(0) = 0, f(1) = 1, and
    g(n) = a*g(n-1) + b*g(n-2), g(0) = A, g(1) = B. Then
    g(n) = B*f(n) + A*b*f(n-1).

    The advantage in this is that once we know the closed form expression for f(n), it is easy to derive the formula for g(n), with any initial values A and B.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: A Fibonacci type sequence
  1. The Fibonacci Sequence (Replies: 6)

  2. Fibonacci Primes (Replies: 6)