[EX] - Una dimostrazione della formula di Binet

[Sk_Anonymous]

Spero che quella che vado a chiedere non sia la dimostrazione "classica", ché in tal caso ho fatto una bella figuraccia. Sta di fatto che questa mattina, a lezione, sono rimasto piuttosto colpito (positivamente) da una dimostrazione della formula di Binet per l'ennesimo numero di Fibonacci, che si serve di tecniche e concetti propri dell'algebra lineare, come matrici, determinanti, autovalori ed autovettori.

Un invito alla dimostrazione è il seguente (per chi non sapesse come procedere):

Si sa che \(\displaystyle f_{n+1} \) (l'(n+1)-esimo numero di Fibonacci) è dato dalla relazione \[\displaystyle f_{n+1}=f_{n} + f_{n-1} \]
Formando quindi coppie di numeri di questa successione, si nota che (servendosi del prodotto tra matrici) \[\displaystyle \begin{pmatrix} f_{n} \\ f_{n+1} \end{pmatrix}=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \binom{f_{n-1}}{f_{n}} \]
che, dopo aver posto \[\displaystyle A=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \]
diviene \[\displaystyle \begin{pmatrix} f_{n} \\ f_{n+1} \end{pmatrix}=A \binom{f_{n-1}}{f_{n}} \]
Del resto, ragionando in maniera ricorsiva, si ha \[\displaystyle \begin{pmatrix} f_{n} \\ f_{n+1} \end{pmatrix}=A^{2} \binom{f_{n-2}}{f_{n-1}}=...=A^{n} \binom{f_{0}}{f_{1}} \]
Si ragioni, quindi: calcolare la potenza n-esima di una matrice richiede molti conti, anche se la matrice non presenta frazioni o numeri grossi al suo interno (come quella in questione).
Ma se si tentasse di spianare un po' la strada?
E se si cercasse, per esempio, di capire se quella matrice è diagonalizzabile?

[orazioster]

beh, ero talmente interessato, di come
si potesse impostare, che neppure ho tentato a pensarci io, ma ho guardato.
eh, in effetti la soluzione è tutta là.
interessante davvero.

[gugo82]

@Delirium: Beh, sì, questa forse è la dimostrazione costruttiva "base" della formula di Binet (o, almeno, l'ho sempre considerata tale perché è stata la prima che ho studiato).
Un'altra dimostrazione si fa usando la trasformata \(\mathcal{Z}\), ma servono un po' di conoscenze di Analisi Complessa.

Ma scommetto che ci sono millemila dimostrazioni costruttive di quella formula... Si dovrebbe googlare un po'.


P.S.: Per dimostrazione costruttiva intendo una dimostrazione in cui si deriva quella formula a partire dal problema. Ciò esclude la dimostrazione per induzione, perché, quando si fa induzione, la formula la si deve già avere sotto mano bella e pronta.

[Sk_Anonymous]

In effetti questa è una delle prime dimostrazioni costruttive che vedo a lezione.
Tempo fa, durante il corso di Algebra I, si parlò di funzioni generatrici come "metodo" per dimostrare formule chiuse come questa; c'è un capitolo dedicato sul libro del mio professore, ed è forse il caso che me lo legga.

[Seneca1]

Non voglio cavillare sull'aggettivo "costruttiva", ma di dimostrazioni costruttive dovresti averne viste parecchie (tipo teorema degli zeri o il teorema di Bolzano-Weierstrass per gl'insiemi infiniti)...

Saluti.

[Sk_Anonymous]

"Seneca":Non voglio cavillare sull'aggettivo "costruttiva", ma di dimostrazioni costruttive dovresti averne viste parecchie (tipo teorema degli zeri o il teorema di Bolzano-Weierstrass per gl'insiemi infiniti)...

Saluti.

Quando ho scritto quel post pensavo semplicemente alla "costruzione di una formula", alludendo implicitamente ad una distinzione tra una particolare dimostrazione costruttiva ed una induttiva. Poi non so, potrei aver travisato il post scriptum di gugo. Non so nulla di costruttivismo matematico.

Del resto, ancora niente teorema degli zeri per me. E' in Analisi I parte B.

[gugo82]

[OT]

"Delirium":[quote="Seneca"]Non voglio cavillare sull'aggettivo "costruttiva", ma di dimostrazioni costruttive dovresti averne viste parecchie (tipo teorema degli zeri o il teorema di Bolzano-Weierstrass per gl'insiemi infiniti)...

Quando ho scritto quel post pensavo semplicemente alla "costruzione di una formula", alludendo implicitamente ad una distinzione tra una particolare dimostrazione costruttiva ed una induttiva. Poi non so, potrei aver travisato il post scriptum di gugo. Non so nulla di costruttivismo matematico.[/quote]
Non hai travisato, Delirium. Anzi, hai colto benissimo il significato in cui ho inteso usare l'aggettivo "costruttivo".
Niente a che vedere col costruttivismo, quindi.

Tra l'altro, quella dimostrazione lì la lessi sul libro di Algebra Lineare di G. Strang, se non erro... Ma si parla di almeno 11 anni fa, quindi potrei sbagliarmi.

[/OT]

[Seneca1]

Come non scritto...