OliForum Matematico

Chiamiamo $S_n$ il numero di possibili successioni crescenti di numeri interi, alternati pari e dispari, da 0 a n. Ad esempio, se $n=3$ le successioni sono $(0,1,2,3)$ e $(0,3)$, quindi $S_3=2$. Dimostrare che $S_n$ è l'$n$-esimo numero di Fibonacci $F_n$.

Si ricorda che la successione di Fibonacci $F_n$ è definita nel seguente modo: $F_0=0$, $F_1=1$, $F_{n+1}=F_n+F_{n-1}$ per ogni $n\ge 1$.

Non si dovrebbe aggiungere alla tesi "per $n\ge1$" ?
Perchè $S_0=1$, mentre $F_0=0$...

Si, Drago... S_0 ed F_0 fanno eccezione...

$F_0=1$ nel testo originale

frod93 ha scritto:$F_0=1$ nel testo originale

O.o

Comunque, faccio questo per induzione
P. BASE: $S_1=1=F_1$
P. INDUTTIVO: Supponiamo che per $2\le i\le n$ valga $S_i=F_i$
Intanto $S_0=1$, banalmente.
Vediamo ora cos'è $S_{n+1}$; sarà sicuramente una sequenza del tipo $(0,a_1,\dots ,a_m,n+1)$. Ma $a_m$ può essere soltanto un numero della stessa parità di $n$, ed inoltre per ogni sequenza in cui $a_m$ è l'ultimo termine, vi è una sola sequenza il cui ultimo termine è $n+1$ e il penultimo è $a_m$. Il numero di sequenze il cui ultimo termine è $a_m$ è esattamente $S_{a_m}$, dunque $S_{n+1}=S_{n}+\dots+S_{n-2k}+\dots+S_x$, dove $x$ è 0 se $n$ è pari, 1 altrimenti. Distinguiamo ora i due casi:
1) $n$ pari
$S_{n+1}=S_n+\dots+S_0=F_n+\dots+F_0+1=F_{n+1}-1+1=F_{n+1}$ (la prima è per ipotesi induttiva, la seconda è una proprietà nota sui Fibonacci)
2) $n$ dispari
$S_{n+1}=S_n+\dots+S_1=F_n+\dots+F_1=F_{n+1}$ (come sopra)
In enrtambi i casi risulta $S_{n+1}=F_{n+1}$. []

Seppur il testo e' al di sotto delle aspettative (so che è facile contestare da questa parte :/ ) la dimostrazione scritta da Drago non e' scritta molto chiaramente, seppur le idee ci sono tutte..

$S_1=F_1=1$ banalmente e supponiamo che la tesi $S_i=F_i$ sia verificata per ogni $i=1,2,\ldots,n-1$. Allora $S_n$ e' il numero di successioni strettamente crescenti di interi da $0$ a $n$ a parità alterne, i.e. oltre la successione banale $(0,n)$ tutte e sole le altre da $0$ a $1\le m\le n-1$ con $m \not \equiv n \pmod 2$. In altre parole $S_n=\displaystyle 1+\sum_{j\in \mathbb{Z} \cap [1,n-1], j\not \equiv n \pmod 2}{S_i}$. Considerata l'ipotesi induttiva, e che $F_0=F_1=1$, possiamo riscrivere $S_n$ come $\displaystyle \sum_{j\in \mathbb{Z} \cap [0,n-1], j\not \equiv n \pmod 2}{F_i}$. Ma allora $S_n-S_{n-2}=F_{n-1}$, i.e. $S_n=S_{n-1}+S_{n-2}=F_{n-1}+F_{n-2}=F_n$. []

Scrivo la mia soluzione.

Sporcandosi un po' le mani, innanzitutto scriviamo che:

$ S_0=1 (0) $
$ S_1=1 (0,1) $
$ S_2=1 (0,1,2) $
$ S_3=2 (0,1,2,3; 0,3) $
$ S_4=3 (0,1,4; 0,1,2,3,4; 0,3,4) $

Un po' con l'intuito, si può notare che, preso un generico $ n $, $ S_n $ si ottiene analizzando tutte le successioni $ S_k $ precendenti a $ S_n $, in modo che valga che $ 2 \nmid n-k $. In sostanza, Se n è pari, vedo tutte le successioni precedenti dei numeri dispari, e viceversa.

All'atto pratico, valutiamo $ S_4 $. Prima del numero $ 4 $ ci può essere un qualsiasi numero dispari: dunque, per sapere la cardinalità di $ S_4 $, opero la somma di $ S_1 $ ed $ S_3 $, dato che mi è possibile considerare tutte e sole queste successioni e aggiungere il numero $ 4 $ alla fine, per ottenere una successione appartenente ad $ S_4 $.

Dunque, in genere vale una di queste due formule:
$ S_n=S_{ n-1 }+S_{ n-3 }+ ... + S_3+S_1 $
oppure
$ S_n=S_{ n-1 }+S_{ n-3 }+ ... + S_2+S_0 $,
a seconda che $ n $ sia pari o dispari.

A questo punto, basta notare che, per gli stessi motivi citati finora, vale che:
$ S_{ n-2 }=S_{ n-3 }+ ... + S_3+S_1 $
oppure
$ S_{ n-2 }=S_{ n-3 }+ ... + S_2+S_0 $,

e dunque, in sostanza, che:
$ S_n=S_{ n-1 }+S_{ n-3 }+ ... + S_3+S_1=S_{ n-1 }+S_{ n-2 } $
oppure
$ S_n=S_{ n-1 }+S_{ n-3 }+ ... + S_2+S_0=S_{ n-1 }+S_{ n-2 } $

Dunque, abbiamo dimostrato che vale che:
$ S_n=S_{ n-1 }+S_{ n-2 } $

Per dimostrare che la successione sia esattamente uguale alla serie di Fibonacci per $ n\ge 1 $, basta notare che, per i numeri $ 1 $,$ 2 $ e $ 3 $ (bastano questi tre) vale che:

$ S_n=F_n $.

Innanzitutto $ S_1 $ e $ S_2 $ sono banalmente verificate, poi si può ragionare sul modo in cui si possono costruire le successioni da $ 0 $ a $ n+1 $: basta notare che si possono formare aggiungendo $ n+1 $ come ultimo termine delle $ S_n $ successioni da $ 0 $ a $ n $, oppure sostituendo il numero $ n-1 $ con $ n+1 $ nelle $ S_{n-1} $ successioni che terminano in $ n-1 $
Dovendo le successioni che costituiscono l'insieme di cardinalità $ S_{n+1} $ terminare con $ n+1 $, non esistono altre successioni accettabili, da cui ricaviamo la formula $ S_{n+1}=S_n + S_{n-1} $.

Faccio un po' di sano necroposting.
Notiamo che ogni successione funzionante si può ottenere in modo univoco rimuovendo blocchi di 2 termini consecutivi (che non comprendano $0$ e $n$) da $(0,1,2,...,n)$. Se rimuoviamo $(n-3,n-2)$ resta da scegliere come sistemare il resto in $S_{n-3}$ modi, altrimenti possiamo scegliere se rimuovere $(n-2,n-1)$ trovando altri $2S_{n-2}$ casi. Ricaviamo così la formula ricorsiva
$$S_n=2S_{n-2}+S_{n-3}$$
che si comporta esattamente come Fibonacci (si può verificare facilmente per induzione).

Io pensavo qualcosa di più semplice:
considero le sequenze del tipo [math]0,\dots,n e [math]0,\dots,n+1.

Per ottenere le sequenze del tipo [math]0,\dots,n+2 è sufficiente:
- considerare le [math]s_n sequenze [math]0,\dots,n e sostituire [math]n \to n+2
- considerare le [math]s_{n+1} sequenze [math]0,\dots,n+1 e aggiungere alla fine [math]n+2 ottenendo [math]0,\dots,n+1,n+2

Quindi segue che [math]s_{n+2}=s_{n} + s_{n+1}