[L03] Numeri di Fibonacci

[Salvador]

Al variare di $n$ intero positivo, si consideri il numero $s_n$ di sequenze di interi crescenti, alternativamente pari e dispari, che cominciano con 0 e terminano con $n$. Ad esempio, per $n=3$ si hanno solo le sequenze $0,1,2,3$ e $0,3$, per cui $s_3=2$. Si dimostri che i numeri $s_n$ sono i numeri di Fibonacci.

[Roob]

Testo nascosto:

Tutte le sequenze che arrivano a [tex]n[/tex] e contengono [tex]1[/tex] possono essere ottenute sommando [tex]1[/tex] a tutti gli elementi delle sequenze che arrivano a [tex]n-1[/tex] e aggiungendo lo [tex]0[/tex] iniziale, mentre quelle che non contengono [tex]1[/tex] possono essere ottenute aggiungendo [tex]2[/tex] a tutti gli elementi tranne lo [tex]0[/tex] delle sequenze che arrivano a [tex]n-2[/tex].
Visto che una sequenza o contiene o non contiene [tex]1[/tex]
[tex]\displaystyle s_{n}=s_{n-1}+s_{n-2}[/tex]
E visto che [tex]s_1=F_1[/tex] e [tex]s_2=F_2[/tex]
[tex]s_n=F_n[/tex]

[Salvador]

A posto. Io invece avevo pensato così:

Testo nascosto:

Considero una sequenza che arriva a $n>2$ e cancello il suo ultimo elemento. A questo punto ci sono due possibilità:
- l'ultimo elemento rimasto è $n-1$, per cui la sequenza corrisponde a una di quelle per $n-1$;
- l'ultimo elemento rimasto è $<n-1$: poiché ha la stessa parità di questo, esso è anche $<n-2$: si può dunque aggiungere $n-2$ alla sequenza, ottenendone una di quelle di $n-2$.
È possibile poi applicare il procedimento inverso alle sequenze che terminano in $n-2$ e $n-1$ ottenendo sequenze in $n$, pertanto $s_n=s_{n-1}+s_{n-2}$ per $n>2$ e poiché $s_1=s_2=1$, $s_n=F_n$.

[Salvador]

Come posso mettere il pedice $n-1$ a $s$ senza avere le parentesi?

[Roob]

Con le graffe

Codice: Seleziona tutto

s_{n-1}

[Salvador]

Ah ok grazie. E come si fa quella cosa Codice: seleziona tutto?

[Roob]

Nell'editor tra le varie cose come "tex" o "spoiler" c'è "code"