OliForum Matematico

Al posto del Sudoku, un esercizio bello di combinatoria allo stato puro:

$ \sum_{k=0}^{n} {{2n-k}\choose{k}} = F_{2n+1} $

Adesso io vado in ferie qualche giorno a Londra,
Buone vacanze!

Combinatoria pura, eh? Che Dio mi perdoni, se mi concedo questa timida divagazione...

Claim: per ogni $ n\in\mathbb{N} $: $ \displaystyle \sum_{k=0}^n \binom{n-k}{k} = F_{n+1} $, dove $ \{F_n\}_{n\in\mathbb{N}} $ indica la successione dei numeri di Fibonacci: $ F_0 = 0 $, $ F_1 = 1 $ ed $ F_{i+2} = F_{i+1} + F_i $, se $ i\in\mathbb{N} $).

Dim.: la tesi è evidente per $ n = 0 $. Ammettendone poi la consistenza per ogni $ k = 0, 1, \ldots, n $, essendo $ n\in\mathbb{N} $, e sfruttando susseguentemente l'identità di Stiefel, si trova:

$ \displaystyle \sum_{k=0}^{n+1} \binom{n+1-k}{k} = \sum_{k=0}^{n+1} \left\{\binom{n-k}{k} + \binom{n-k}{k-1}\right\} = $$ \displaystyle\sum_{k=0}^{n} \binom{n-k}{k} + \sum_{k=0}^{n-1} \binom{n - 1 -k}{k} = F_{n+1} + F_n = F_{n+2}\;\! $,

pur di considerare che, essendo $ u, v \in \mathbb{Z} $: $ \displaystyle\binom{u}{v} = 0 $, se $ v < 0 $ vel $ \,0 \leq u < v $. Di qui la tesi, per induzione estesa su $ n $.

Ovviamente il tuo problema, Catraga, è una particolarizzazione del risultato precedente. Deh, buone vacanze!

Quella che chiami identità di Stiefel sarebbe $ \binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1} $ ?

Sì, Flyer, ed immagino pure di essere l'unico (o fra i pochi!) ad attribuirle quel nome, vero?

No, la chiamavo anch'io qualche anno fa in quella maniera.

La dimostrazione proposta e' una semplice applicazione del principio di induzione (vorrei anche vedere pero' quella ovvia particolarizzazione ad hoc del risultato generale... ). Esiste anche una dimostrazione costruttiva...

Sia chiamata bella una parola di 2 lettere (A;B) lunga n t.c. non abbia un numero dispari di B consecutive.
Sia g(n) il numero di parole belle.

Se la prima lettera è una A allora può essere seguita da una qualsiasi parola bella lunga n-1.
Se la prima lettera è una B allora anche la seconda dovrà essere una B che potrà poi essere seguita da una qualsiasi parola bella lunga n-2.

Per cui g(n)=g(n-1)+g(n-2)
E' facile vedere che g(1)=1 e g(2)=2 da cui si può concludere che:
$ \displaystyle g(n)=F_{n+1} $

Wlog considero ora le coppie di B (posso disporre le B solo per coppie..) come una lettera sola C.
Devo avere quindi k C e J A in modo t.c. $ 2k+j=n $.

Fissato k le configurazioni di questo tipo risultano essere:
$ \displaystyle \frac{(k+j)!}{k!j!}= {n-k \choose k} $
Il massimo valore che k può assumere è $ [\frac{n}{2}] $, il minimo è 0.

E' quindi facile concludere che:
$ \displaystyle g(n)=\sum_{k=0}^{[\frac{n}{2}]} {n-k \choose k}=F_{n+1} $

da cui:
$ \displaystyle \sum_{k=0}^{n} {2n-k \choose k}=F_{2n+1} $

Mi piacerebbe dirti che era l'interpretazione che davo io all'identita', ma a distanza di un anno non mi ricordo.... la mia memoria a breve termine e' molto a breve termine, a proposito come sono arrivato fin qua?
Comunque interessante l'interpretazione...