Sia \(F_n\) la successione di Fibonacci, con \(F_1 = F_2 = 1\). Dimostrare che
\( \displaystyle F_{2n} = \sum_{k=0}^{n-1}{ \binom{n+k}{2k+1} } \)
P.S. Se volete, ho trovato un'identità con i binomiali per una generica successione \(a_{n+2} = \alpha a_{n+1}+\beta a_n\). Se a qualcuno interessa, la posto!
Fibonacci perde il pelo ma non i binomiali
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Fibonacci perde il pelo ma non i binomiali
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Fibonacci perde il pelo ma non i binomiali
Diciamo che il discorso è un po' più generale, e in un certo senso in queste successioni ci va un po' di sfiga perchè servono tanti binomiali, però ciccia.
Comunque, data una successione
\( a_{n+2} = \alpha a_{n+1} + \beta a_n \)
che parte da \(a_1, a_2\) vale questa cosa orrenda se scritta così ma poi in fondo non tanto male:
\[ a_n = \sum_{ k \equiv n \pmod{2}, k \le n} \binom{ (n+k)/2 -1}{k} \alpha^k\beta^{(n-k)/2 -1} a_1 + \sum_{k \equiv n+1 \pmod{2}, k \le n} \binom{(n+k-1)/2}{k} \alpha^k\beta^{(n-k-1)/2 } a_2 \]
Dividendo nei casi \(n\) pari, dispari già viene una cosa scritta in modo più umano (spero mi sia uscito scritto bene):
\[a_{2n}= \sum_{ k \le n} \binom{n+k -1}{2k} \alpha^{2k}\beta^{n-k -1} a_1 + \sum_{ k \le n-1} \binom{n+k}{2k+1} \alpha^{2k+1} \beta^{n-k} a_2 \]
\[a_{2n+1}= \sum_{k \le n} \binom{ n+k}{2k+1}\alpha^{2k+1}\beta^{n-k-1} a_1 + \sum_{k \le n} \binom{n+k}{2k}\alpha^{2k}\beta^{n-k}a_2 \]
Comunque, data una successione
\( a_{n+2} = \alpha a_{n+1} + \beta a_n \)
che parte da \(a_1, a_2\) vale questa cosa orrenda se scritta così ma poi in fondo non tanto male:
\[ a_n = \sum_{ k \equiv n \pmod{2}, k \le n} \binom{ (n+k)/2 -1}{k} \alpha^k\beta^{(n-k)/2 -1} a_1 + \sum_{k \equiv n+1 \pmod{2}, k \le n} \binom{(n+k-1)/2}{k} \alpha^k\beta^{(n-k-1)/2 } a_2 \]
Dividendo nei casi \(n\) pari, dispari già viene una cosa scritta in modo più umano (spero mi sia uscito scritto bene):
\[a_{2n}= \sum_{ k \le n} \binom{n+k -1}{2k} \alpha^{2k}\beta^{n-k -1} a_1 + \sum_{ k \le n-1} \binom{n+k}{2k+1} \alpha^{2k+1} \beta^{n-k} a_2 \]
\[a_{2n+1}= \sum_{k \le n} \binom{ n+k}{2k+1}\alpha^{2k+1}\beta^{n-k-1} a_1 + \sum_{k \le n} \binom{n+k}{2k}\alpha^{2k}\beta^{n-k}a_2 \]
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Fibonacci perde il pelo ma non i binomiali
Chi prova quella inziale?
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: Fibonacci perde il pelo ma non i binomiali
Dovrebbe venire con un double counting, perché entrambi i membri dell'identità sono il numero di modi di salire una scala di $2n-1$ gradini potendo fare passi di $1$ o $2$ gradini alla volta (questa perlomeno è l'idea, probabilmente non riuscirò a convincere più di tanto con la spiegazione seguente).
Vediamo il LHS: Qui basta notare che il primo gradino si raggiunge in un solo modo (facendo un passo da $1$, qualsiasi altra mossa ci manda oltre), il secondo in due (due passi da $1$ oppure uno solo da $2$); inoltre il gradino $m$ si raggiunge in un modo dal gradino $m-1$ (facendo un passo da $1$) ed in un modo dal gradino $m-2$ (facendo un passo da $2$), dandoci la regola ricorsiva dei Fibonacci (volendo qui si può formalizzare per induzione).
Vediamo il RHS: Partiamo dalla "parola" con il massimo numero di "2", ovvero $\underbrace{2222...2}_{n-1}1$, chiaramente i suoi possibili anagrammi saranno ${(n-1)+1\choose 1}$. Trasformando $k$ "2" in una coppia di "1" (per $k\leq n-1$ perché ovviamente non possiamo trasformare più "2" di quelli a disposizione), chiaramente gli anagrammi saranno ${(n-1)+1+(2k-k)\choose 2k+1}={n+k\choose 2k+1}$. Sommando su tutti i possibili $k$, otteniamo ovviamente il numero di modi di arrivare al nostro scalino, e la tesi dovrebbe quindi essere dimostrata.
Come potevo formalizzare meglio questo ragionamento? Perché messo giù così, non mi convince tanto
Vediamo il LHS: Qui basta notare che il primo gradino si raggiunge in un solo modo (facendo un passo da $1$, qualsiasi altra mossa ci manda oltre), il secondo in due (due passi da $1$ oppure uno solo da $2$); inoltre il gradino $m$ si raggiunge in un modo dal gradino $m-1$ (facendo un passo da $1$) ed in un modo dal gradino $m-2$ (facendo un passo da $2$), dandoci la regola ricorsiva dei Fibonacci (volendo qui si può formalizzare per induzione).
Vediamo il RHS: Partiamo dalla "parola" con il massimo numero di "2", ovvero $\underbrace{2222...2}_{n-1}1$, chiaramente i suoi possibili anagrammi saranno ${(n-1)+1\choose 1}$. Trasformando $k$ "2" in una coppia di "1" (per $k\leq n-1$ perché ovviamente non possiamo trasformare più "2" di quelli a disposizione), chiaramente gli anagrammi saranno ${(n-1)+1+(2k-k)\choose 2k+1}={n+k\choose 2k+1}$. Sommando su tutti i possibili $k$, otteniamo ovviamente il numero di modi di arrivare al nostro scalino, e la tesi dovrebbe quindi essere dimostrata.
Come potevo formalizzare meglio questo ragionamento? Perché messo giù così, non mi convince tanto
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)
"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)
Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?
PRIMA FILA TUTTI SBIRRI!
"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)
Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?
PRIMA FILA TUTTI SBIRRI!
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Fibonacci perde il pelo ma non i binomiali
Daje! L'idea è proprio quella! La formula generale che ho scritta è esattamente questo discorso scimmiottato per una ricorsione generale.
Per la formalizzazione:
Per la formalizzazione:
Testo nascosto:
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe