Fibonacci, again

[elgiovo]

Dimostrare che $sum_(k=0)^(n-1)sum_(j=0)^(n-1)((n-1),(k))((j),(n-j-1))=f_n2^(n-1)$.

[karl]

Osserviamo dapprima che :
$sum_(k=0)^(n-1)((n-1),(k))=(1+1)^(n-1)=2^(n-1)$
Pertanto ,detta E l'espressione da calcolare,risulta:
$E=2^(n-1)sum_(j=0)^(n-1)((j),(n-j-1))$
Poniamo ora: j=n-k-1 da cui k=n-j-1
Per j=0-->k=n-1;per j=n-1-->k=0 e quindi:
$E=2^(n-1)sum_(k=0)^(n-1)((n-k-1),(k))$
Secondo la usuale convenzione e' $((a),(b))=0$ se a<b e quindi si puo' scrivere:
$E=2^(n-1)sum_(k=0)^[[(n-1)/2]]((n-k-1),(k))$
Poniamo ora :
$v_n=sum_(k=0)^[[(n-1)/2]]((n-k-1),(k))$
Risulta chiaramente $v_1=1=u_1,v_2=1=u_2$ e dunque se ci riesce
di dimostrare che $v_n+v_(n-1)=v_(n+1)$ sara' certamente $v_n=u_n$ ,come si vuole ottenere.
Occorre fare due casi:n pari=2l oppure n dispari=2l+1.
n=2l.
Abbiamo di seguito:
$v_n+v_(n-1)=sum_(k=0)^(l-1)((n-k-1),(k))+sum_(k=0)^(l-1)((n-k-2),(k))$
Nella seconda sommatoria cambiamo k in k-1:
$v_n+v_(n-1)=sum_(k=0)^(l-1)((n-k-1),(k))+sum_(k=1)^l((n-k-1),(k-1))$
Ovvero
$v_n+v_(n-1)=1+sum_(k=1)^(l-1)[((n-k-1),(k))+((n-k-1),(k-1))]+((n-l-1),(l-1))$
Cioe'(essendo n=2l):
$v_n+v_(n-1)=1+sum_(k=1)^(l-1)((n-k),(k))+((l-1),(l-1))=sum_(k=0)^l((n-k),(k))=v_(n+1)$
In maniera analoga si ragione per n=2l+1
karl

[elgiovo]

Va bene, anche se l'avevo trovata più semplicemente.