A Fibonacci type sequence

erszega

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?

Hurkyl

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!

erszega

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

matt grime

h(n) is just the sum of two geometric progressions. You can evaluate those.

erszega

Yes, thanks, of course, then I get h(n) = ((1+t)^{n+1} + (1-t)^{n+1} - 2) / 4, where t is sqrt(2).

erszega

and then G(n,m) = ( (1+sqrt(2))^m + (1-sqrt(2))^m ) * 2^{n-1}.

CRGreathouse

The first sequence is the Pell numbers, A000129. How did the second sequence come up, out of curiosity?

ramsey2879

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.

0rthodontist

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.

erszega

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?

0rthodontist

Instead of u(x) I guess you mean f(x). You have the roots a and b, so your fraction is
[tex]\frac{1-x}{(x-a)(x-b)}[/tex]
Now you expand by partial fractions to get
[tex]\frac{A}{x-a}+\frac{B}{x-b}[/tex]
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 Crⁿ for some C and r. Substitute that back into the sequence definition and simplify, giving you the equation
r²-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) = C₁a^n+C₂b^n. Use the fact that you know the first few terms of the series to solve for C₁ and C₂.
C₁ + C₂ = 1
aC₁ + bC₂ = 5
C₂ = [tex]\frac{5-a}{b-a}[/tex]

C₁ = [tex]\frac{b-5}{b-a}[/tex]
and now you have determined the sequence.

erszega

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.

erszega

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

u(n)=S(n)-S(n-1).

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

erszega

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:

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