# A Fibonacci type sequence

1. Jun 30, 2006

### 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?

2. Jun 30, 2006

### Hurkyl

Staff Emeritus
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!

3. Jun 30, 2006

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

Last edited: Jul 1, 2006
4. Jun 30, 2006

### matt grime

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

5. Jun 30, 2006

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

6. Jul 1, 2006

### erszega

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

7. Jul 6, 2006

### CRGreathouse

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
8. Jul 8, 2006

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

Last edited by a moderator: May 2, 2017
9. Jul 8, 2006

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

Last edited: Jul 8, 2006
10. Jul 9, 2006

### 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 [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
11. Jul 9, 2006

### 0rthodontist

Instead of u(x) I guess you mean f(x). You have the roots a and b, so your fraction is
$$\frac{1-x}{(x-a)(x-b)}$$
Now you expand by partial fractions to get
$$\frac{A}{x-a}+\frac{B}{x-b}$$
where $$A = \frac{1-a}{a-b}$$
and $$B = \frac{1-b}{b-a}$$
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 = $$\frac{5-a}{b-a}$$

C1 = $$\frac{b-5}{b-a}$$
and now you have determined the sequence.

Last edited: Jul 9, 2006
12. Jul 11, 2006

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

13. Jul 12, 2006

### 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 [Broken] ).

Last edited by a moderator: May 2, 2017
14. Jul 15, 2006

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