Curiosità ($n$-esima...) sui numeri di Fibonacci

[Dorian]

Nel mio vecchio libro di Algebra c'è questo:

Dimostrare che ogni intero positivo si può scrivere come somma di un numero finito di numeri di Fibonacci distinti.

[Gaal Dornick]

Provo che $AAn in NN, n>=1: n$ è somma di elementi distinti di ${F_n}_(n in NN)$

ove $F_0=1, F_1=2...$ e vale che $F_n<F_(n+1)$ (mi serviva questa proprietà, e quindi faccio partire da lì la successione)

La dimostrazione è per induzione:
n=1 $1=F_0$

supponiamo che la tesi sia verificata per $i<n$
se $n$ è di Fibonacci, ok.
se $n$ non è di Fibonacci ($=> n>=4$)
determino il più grande numero di Fibonacci <n:

poichè $lim_(i) F_i=+oo$ definitivamente $F_i>=n$
sia $A={F_i|F_i>=n, i in NN}$
$A$ è un sottoinsieme non vuoto di $NN$, quindi è dotato di minimo.
Sia $nu in NN t.c. F_(nu)=minA$
sia $bar(nu)=nu-1$: sicuramente $F_(nu)>=n>=4>3=F_2$, $F_2<F_(nu) $quindi $2<nu$.

Sicuramente $F_(bar(nu))$ non è in A quindi $F_(bar(nu))<n$
Inoltre è il più grande numero di Fibonacci a farlo (per la stretta crescenza di ${F_i}$)
$0<n-F_(bar(nu))<n$
per l'ipotesi induttiva $n-F_(bar(nu))$ è somma di elementi distinti di ${F_i}$. Proviamo che tra questi non può esservi $F_(bar(nu))$: se per assurdo vi fosse, si avrebbe:
$n<=F_(bar(nu)+1)=F_(bar(nu))+F_(bar(nu)-1)<F_(bar(nu))+F_(bar(nu))<n$
I WIN


In realtà è molto costruttiva come dimostrazione: la feci per provare che valeva la tesi..e scrivere il programma che calcola esplicitamente questa decomposizione. Carina, mi divertii molto.

[G.D.]

Nel mio vecchio libro di Algebra c'è questo:

Dimostrare che ogni intero positivo si può scrivere come somma di un numero finito di numeri di Fibonacci distinti.

Anche noto come Teorema di Zeckendorf.

[Dorian]

Nel mio vecchio libro di Algebra c'è questo:

Dimostrare che ogni intero positivo si può scrivere come somma di un numero finito di numeri di Fibonacci distinti.

Anche noto come Teorema di Zeckendorf.

Non lo sapevo... Nel mio libro è presentato semplicemente come esercizio...

[Dorian]

Anche noto come Teorema di Zeckendorf.

Guardando meglio, l'esercizio chiede di dimostrare una proposizione più debole del teorema di Zeckendorf... Infatti a noi va bene anche una decomposizione in numeri di Fibonacci consecutivi!

[Dorian]

Qualcuno ha dato un'occhiata al link segnalato da Wizard?
Ho una perplessità: si dice che

se $N$ è un sottinsieme non vuoto e finito di $NN$ di numeri non consecutivi ($|i-j|>1, AAi,j in N, i!=j$), allora:

$sum_(i in N) F_i<F_(max(N)+1)$

ma preso $N={1,3,5}$, abbiamo che $F_1+F_3+F_5=1+2+5=8=F_6$, quindi la disuguaglianza vale in senso lato.

Il problema è questo: come è possibile dedurre l'unicità della somma di Zeckendorf se la disuguaglianza non è stretta?

[G.D.]

Non mi intendo di TdN: conoscevo questo risultato e ne conoscevo il nome, ma non ho mai conosciuto la dimostrazione. Quindi non ti so dire. Prova a dare un'occhiata [http://planetmath.org/?op=getobj&from=objects&id=8810]quiì[/url].

[Dorian]

Com'è noto:

$lim_(n->+oo) F_(n+1)/(F_n)=phi$;

dove $phi$:=$(1+sqrt(5))/2$.

Ma non tutti sanno che:

$-phi=sin(666°)+cos(6*6*6°)$...

Impressionante, vero?

[miuemia]

non capisco bene gli esponenti

[Dorian]

non capisco bene gli esponenti

Non sono esponenti, stanno solo ad indicare che l'angolo è espresso in gradi...