Fibonacci/binomiale $F_{n+1}=sum_{0\le 2k \le n}((n-k),(k))$
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}$).
$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}$).
Risposte
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!
$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!
"Levacci":
$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$.
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)$.
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)$.
"elgiovo":Bella Dimostrazione!
Un pò di snake oil mi consente di ottenere una seconda dimostrazione.
Avresti dovuto partire con...
Sì, errore ingenuo. Cercherò di aggiustare, se possibile, l'induzione. Comunque, complimenti ad elgiovo e a ficus per il problema
.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo