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!
Somma coi binomiali
Somma coi binomiali
Aladin to the genius: "Oh, great spirit! My desire is that you do not fullfill my desire"
The genius was enlightened.
The genius was enlightened.
La Verità più grande vive di generalizzazioni!
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! 
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! -
MindFlyer
Ultimo post prima di Londra...
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...
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...
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
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} $
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} $
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
