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, http://www.research.att.com/~njas/sequences/A000129 [Broken]. How did the second sequence come up, out of curiosity?
    Last edited by a moderator: May 2, 2017
  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.
    Last edited by a moderator: May 2, 2017
  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 [Broken] ).

    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?
    Last edited by a moderator: May 2, 2017
  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 [Broken] ).
    Last edited by a moderator: May 2, 2017
  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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook