fibonacci/binomiale $F_{n+1}=sum_{0\le 2k \le n}((n-k),(k))$

[ficus2002]

Dimostrare che
$F_{n+1}=sum_{0\le 2k \le n}((n-k),(k))$
dove $F_n : n\in NN$ sono i numeri di Fibonacci ($F_0=F_1=1$ e $F_{n+1}=F_{n}+F_{n-1}$).

[Levacci]

Un appunto di dimostrazione (più o meno per induzione) poco prima di dormire:

$sum_(k=0)^([n/2]) ((n-k),(k)) + sum_(k=0)^([n/2]+1) ((n+1-k),(k)) = ((n+1),(0)) + sum_(k=0)^([n/2]) (((n-k),(k))+((n-k),(k+1))) = ((n+2),(0)) + sum_(k=0)^([n/2]+1) ((n+1-k),(k+1))= sum_(k=0)^([n/2]+1) ((n+2-k),(k))$

Domani, se richiesta, aggiungerò qualche parola di commento al minestrone di binomiali qua in cima, per ora troppo sonno . Mancano i casi banali ma, appunto, sono banali.

Naturalmente sono possibili errori di indici, di forma e di sostanza. Che dire? Ci ho provato!

[ficus2002]

$sum_(k=0)^([n/2]) ((n-k),(k)) + sum_(k=0)^([n/2]+1) ((n+1-k),(k)) = \ldots$

Avresti dovuto partire con
$sum_(k=0)^([n/2]) ((n-k),(k)) + sum_(k=0)^([(n+1)/2]) ((n+1-k),(k)) = \ldots$
perchè in generale $[(n+1)/2]\ne [n/2]+1$.

[elgiovo]

Un pò di snake oil mi consente di ottenere una seconda dimostrazione.

Sia $f(n)=sum_(0<=2k<=n) ((n-k),(k))$. Si può scrivere anche $f(n)=sum_(k>=0)((n-k),(k))$ perchè se $k>=n-k$ e quindi $2k>n$ il coefficiente binomiale si annulla.
Moltiplichiamo per $x^n$ e sommiamo su $n$ per ottenere la funzione generatrice della sequenza:

$F(x)=sum_(n>=0) x^n sum_(k>=0)((n-k),(k))=sum_(k>=0) sum_(n>=0)((n-k),(k)) x^n=sum_(k>=0) x^k sum_(n>=0)((n-k),(k)) x^(n-k)$.

A questo punto è utile ricordare che vale $sum_(r>=0)((r),(k))x^r=x^k/(1-x)^(k+1)$, per cui possiamo scrivere

$F(x)=sum_(k>=0) x^(2k)/(1-x)^(k+1)=1/(1-x)+x^2/(1-x)^2+ldots=1/(1-x) 1/(1-x^2/(1-x))=1/(1-x-x^2)$.

Il coefficiente di $x^n$ nello sviluppo in serie di $F(x)$ è proprio $1/sqrt5 [((1+sqrt5)/2)^(n+1)-((1-sqrt5)/2)^(n+1)]=F_(n+1)$.

[ficus2002]

Un pò di snake oil mi consente di ottenere una seconda dimostrazione.

Bella Dimostrazione!

[Levacci]

Avresti dovuto partire con...

Sì, errore ingenuo. Cercherò di aggiustare, se possibile, l'induzione. Comunque, complimenti ad elgiovo e a ficus per il problema .