A Fibonacci type sequence


by erszega
Tags: fibonacci, sequence, type
erszega
erszega is offline
#1
Jun30-06, 03:43 PM
P: 36
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?
Phys.Org News Partner Science news on Phys.org
Going nuts? Turkey looks to pistachios to heat new eco-city
Space-tested fluid flow concept advances infectious disease diagnoses
SpaceX launches supplies to space station (Update)
Hurkyl
Hurkyl is offline
#2
Jun30-06, 03:47 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
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
erszega is offline
#3
Jun30-06, 05:54 PM
P: 36
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
matt grime is offline
#4
Jun30-06, 05:58 PM
Sci Advisor
HW Helper
P: 9,398

A Fibonacci type sequence


h(n) is just the sum of two geometric progressions. You can evaluate those.
erszega
erszega is offline
#5
Jun30-06, 06:38 PM
P: 36
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
erszega is offline
#6
Jul1-06, 05:07 PM
P: 36
and then G(n,m) = ( (1+sqrt(2))^m + (1-sqrt(2))^m ) * 2^{n-1}.
CRGreathouse
CRGreathouse is offline
#7
Jul6-06, 11:16 PM
Sci Advisor
HW Helper
P: 3,680
The first sequence is the Pell numbers, A000129. How did the second sequence come up, out of curiosity?
ramsey2879
ramsey2879 is offline
#8
Jul8-06, 11:45 AM
P: 891
Quote Quote by CRGreathouse
The first sequence is the Pell numbers, A000129. How did the second sequence come up, out of curiosity?
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
0rthodontist is offline
#9
Jul8-06, 07:09 PM
Sci Advisor
P: 1,253
Quote Quote by 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?
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
erszega is offline
#10
Jul9-06, 03:27 PM
P: 36
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
0rthodontist is offline
#11
Jul9-06, 05:17 PM
Sci Advisor
P: 1,253
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 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.
erszega
erszega is offline
#12
Jul11-06, 04:11 AM
P: 36
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
erszega is offline
#13
Jul12-06, 02:21 PM
P: 36
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
erszega is offline
#14
Jul15-06, 05:49 AM
P: 36
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.


Register to reply

Related Discussions
Fibonacci sequence Brain Teasers 22
The Fibonacci Sequence Linear & Abstract Algebra 6
Fibonacci Sequence Introductory Physics Homework 13
Fibonacci sequence Introductory Physics Homework 3
Fibonacci Sequence...so confused Calculus 6