I was wondering if anybody knows where there is a derivation of Binet's formula for the Fibonacci sequence, and whether there is a similar formula for the Tribonacci sequence (with a derivation)...

Cheers
Deano

F_n+1=F_n+F_n-1,(n ³ 1; F₀=0; F₁=1) (1)

and the generating function of the sequence is

F(x)=

å n ³ 0

Fn xn

.

Multiply (1) by xⁿ and sum over n ³ 1 to get

(F(x)-x)/x=F(x)+xF(x),

it follows that

F(x)=x/(1-x-x²).

Now

1-x-x²=(1-C₊x)(1-C_-x), (C_±=(1±Ö5)/2)

and so

x/(1-x-x2) = x/((1-C+x)(1-C-x)) = 1/(C+-C-)(1/(1-C+x)-1/(1-C-x)) = 1/Ö5 æ è å j ³ 0  C+j xj - å j ³ 0  C-j xj ö ø

which is just the difference of two geometric series, hence

F_n=1/Ö5(C₊ⁿ-C_-ⁿ) (n=0, 1, 2, ...). (2)

But since C₊ > 1 and C_- < 1, the second term is small enough to ignore, so a good approximation to F_n is

F_n=1/Ö5((1+Ö5)/2)ⁿ. (3)

In fact F_n is just the nearest integer to (3).

Or...
x² -x-1=0 has two roots A and B, they must satisfy:
A² =A+1 and B² =B+1
Multiply the first by Aⁿ and the second by Bⁿ , we get:
Aⁿ⁺² =Aⁿ⁺¹ +1 and Bⁿ⁺² =Bⁿ⁺¹ +1
Subtract the first from the second and divide by A-B
to get
(Aⁿ⁺² -Bⁿ⁺² )/(A-B)=(Aⁿ⁺¹ -Bⁿ⁺¹ )/(A-B)+(Aⁿ -Bⁿ )/(A-B)
set H_n =(Aⁿ -Bⁿ )/(A-B)

A way to understand why Yatir's method works is the following:
F_n+1 -F_n -F_n-1 = 0 (*)
Suppose the solution is of the form F_n = Aⁿ . This gives the equation A² -A-1 = 0. This has two roots say x and y.
Now notice that if g(n),h(n) are solutions of (*) then so is ag(n)+bh(n) for any constants a,b.
So axⁿ + byⁿ is a solution of (*).
Using F₁ =F₂ =1 you can find a and b.

This looks very much like the method of solving ordinary differential equations with constant coefficients. Equation (*) is a second order difference equation with constant coefficients.

Demetres

Demetres,

could you please elaborate a little more where you say:

Now notice that if g(n),h(n) are solutions of (*) then so is ag(n)+bh(n) for any constants a,b.
So axn + byn is a solution of (*).

Thanks
Deano

Suppose that g(n) , h(n) satisfy (*) i.e. g(n+1) - g(n) - g(n-1) = 0 and h(n+1) - h(n) - h(n-1) = 0 . Then if we define a new function f by f(n) = ag(n) + bg(n) where a,b are any constants then it is easy to show that f(n+1) - f(n) - f(n-1) = 0.

Did you understand why xⁿ and yⁿ where solutions of (*) or do you also want me to elaborete more on that ?

Demetres

The Tribonacci recurrence is

Multiply (1) by xⁿ and sum over n ³ 4

(T(x)-x-2x²)/x²=T(x)+xT(x)

it follows that

T(x)=1/(1-x-x²-x³).(2)


You can use this generating function to calculate the coefficients; there is an explicit formula for T_n (see Mathworld for example) but it is very messy; for an asymptotic formula for T_n , use Darboux's lemma.

Thanks Ben and Yatir,

Demetres,

I "kind of" understand why x_n and y_n were solutions, but if you could clarify once more just to make it crystal clear that i understand , then it would be greatly appreciated...

Thanks a lot
Deano

From this I got the equation A²-A-1 which gives two solutions x and y ( I just didn't bother to write them down explicitly they are [1±Ö5]/2. Then you can easily check that these satisfy (*) since xⁿ⁺¹-xⁿ-x^n-1=x^n-1[x²-x-1]=0 (and similarly for y)

Demetres