# A Fibonacci type sequence

by erszega
Tags: fibonacci, sequence, type
 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?
 PF Patron Sci Advisor Emeritus P: 16,094 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!
 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.
HW Helper
P: 9,395

## A Fibonacci type sequence

h(n) is just the sum of two geometric progressions. You can evaluate those.
 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).
 P: 36 and then G(n,m) = ( (1+sqrt(2))^m + (1-sqrt(2))^m ) * 2^{n-1}.
 HW Helper Sci Advisor P: 3,682 The first sequence is the Pell numbers, A000129. How did the second sequence come up, out of curiosity?
P: 891
 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.
 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 $$\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.