Fibonacci perde il pelo ma non i binomiali

[Gottinger95]

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!

[Troleito br00tal]

Fico, postala.

[Gottinger95]

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 \]

[Gottinger95]

Chi prova quella inziale?

[Lasker]

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

[Gottinger95]

Daje! L'idea è proprio quella! La formula generale che ho scritta è esattamente questo discorso scimmiottato per una ricorsione generale.
Per la formalizzazione:

Testo nascosto:

1. Se ti senti vecio induzione funge sempre (pure se è un po' scomodo il fatto che \(n\) è pari al LHS, forse dovresti trovare qualcosa per \(n\) dispari);
2. Immagina di "sciogliere" la ricorsione di Fibonacci, finchè non arrivi a \( F_n = \alpha_n F_1 + \beta_n F_2 = \alpha_n + \beta_n\). Chi sono \(\alpha_n, \beta_n\)?
Per ogni "scelta" di cammino da \(n\) a 1 quando sciogli la ricorsione (i.e. faccio passi, in ordine, lunghi \(1,2,1,1,2,1,1,2,2,1\)), c'è un 1 in più in \(\alpha_n\) (perchè?). Dunque...
Sono stato un po' vago, insomma, c'è ancora una cosina da aggiustare nel tuo ragionamento, cioè il fatto che "la scala" finisce sia quando arrivo al gradino 1 che quando arrivo al gradino 2.