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\ge 1$; $F_0=0$; $F_1=1$) (1)

and the generating function of the sequence is

$F(x)=\sum _{n\ge 0}{F}_n{x}^n$.

Multiply (1) by $x^n$ and sum over $n\ge 1$ to get

$(F(x)-x)/x=F(x)+\mathrm{xF}(x)$,

it follows that

$F(x)=x/(1-x-x^2)$.

Now

$1-x-x^2=(1-C_{+}x)(1-C_{-}x)$, ( $C_{\pm }=(1\pm \sqrt{5})/2)$

and so

${\displaystyle \begin{array}{ccc}\multicolumn{1}{c}{x/(1-x-x^2)}& =& x/((1-C_{+}x)(1-C_{-}x))\\ \multicolumn{1}{c}{}& =& 1/(C_{+}-C_{-})(1/(1-C_{+}x)-1/(1-C_{-}x))\\ \multicolumn{1}{c}{}& =& 1/\sqrt{5}(\sum _{j\ge 0}{C}_{+}^j{x}^j-\sum _{j\ge 0}{C}_{-}^j{x}^j)\end{array}}$

which is just the difference of two geometric series, hence

$F_n=1/\sqrt{5}(C_{+}^n-C_{-}^n)$ ( $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/\sqrt{5}((1+\sqrt{5})/2{)}^n$. (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^n$ and sum over $n\ge 4$

$(T(x)-x-2x^2)/x^2=T(x)+\mathrm{xT}(x)$

it follows that

$T(x)=1/(1-x-x^2-x^3)$.(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

Demetres