A Fibonacci type sequence

  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. Hurkyl

    Hurkyl 15,987
    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. 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. matt grime

    matt grime 9,395
    Science Advisor
    Homework Helper

    h(n) is just the sum of two geometric progressions. You can evaluate those.
  6. 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. and then G(n,m) = ( (1+sqrt(2))^m + (1-sqrt(2))^m ) * 2^{n-1}.
  8. CRGreathouse

    CRGreathouse 3,497
    Science Advisor
    Homework Helper

    The first sequence is the Pell numbers, A000129. How did the second sequence come up, out of curiosity?
  9. 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. 0rthodontist

    0rthodontist 1,249
    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. 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. 0rthodontist

    0rthodontist 1,249
    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. 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. 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. 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 thead via email, Google+, Twitter, or Facebook

Have something to add?