Sfida binomiale!

[darkcrystal]

1. Trovare una formula chiusa per la somma $ \displaystyle \sum_{k=0}^n {2k \choose k} {2(n-k) \choose n-k} $ (ricordo che $ {0 \choose 0}=1 $)
2. Dimostrarla
3. In caso non sia già successo al punto 2, trovare una dimostrazione completamente combinatoria.

Bonne chance !

[Troleito br00tal]

Aggiunto un comodo e pratico hide -- EG
Di solito non posto soluzioni di problemi che ho già visto, ma di questo ne ho una così complicata e praticamente NON combinatoria, quindi: perché no?

Perciò avverto: SPOILER ALERT SOTTO C'È LA SOLUZIONE.






















Ok.

Testo nascosto:

Sia $C_n$ l'$n$-esimo numero di Catalan. Ricordo che $C_n=\frac{1}{n+1} {2n \choose n}$. Ricordiamo anche che $C_n=C_0C_{n-1}+...+C_{n-1}C_0$ (lascio la dimostrazione combinatorica di questo fatto al valoroso lettore (comunque è abbastanza carina)). Sia $f(x)=\sum_{i=0}^{+ \infty} C_i x^{i+1}$. Per la bella proprietà vale $f(x)^2=\sum_{i=1}^{+ \infty} C_i x^{i+1}$, da cui $f(x)^2=f(x)-x$. Ma allora $f(x)=\frac{1 \pm \sqrt{1-4x}}{2}$. Sia $f'(x)$ la derivata di $f(x)$. Vale: $f'(x)=\sum_{i=0}^{+ \infty} {2i \choose i} x^i$, ma anche $f'(x)=\pm \frac{1}{\sqrt{1-4x}}$, da cui $f'(x)^2=\sum_{i=0}^{+ \infty} (\sum_{k=0}^i {2i \choose i}) x^i$, ma anche $f'(x)^2=\frac{1}{1-4x}=\sum_{i=0}^{+ \infty} 4^i x^i$, da cui $\sum_{i=0}^{+ \infty} 4^i x^i=\sum_{i=0}^{+ \infty} (\sum_{k=0}^i {2i \choose i}) x^i$, perciò $\sum_{k=0}^n {2n \choose n}=4^n$ per ogni $n$.

[Drago96]

Io avrei tolto anche lo spazio bianco, dà fastidio
In ogni caso

Testo nascosto:

Si fa anche senza Catalan, per quanto sia una cosa molto figa!
Usiamo il simpatico binomio di Newton generalizzato: $\displaystyle(1+x)^\alpha=\sum_{i\ge0}\binom\alpha i x^i$, dove $\displaystyle\binom\alpha i=\frac{\alpha(\alpha-1)\cdots(\alpha-i+1)}{i!}$.
Ora uno vede che $\displaystyle\binom{2n}n=\frac{2^n(2n-1)!!}{n!}$ e che $\displaystyle\binom{-1/2}n=(-1)^n\frac{(2n-1)!!}{2^n\cdot n!}$.
Quindi si ha proprio $\displaystyle\sum_{n\ge0}\binom{2n}nx^n=(1-4x)^{-1/2}$
Elevando al quadrato, a sinistra abbiamo la generatrice dei numeri che ci interessano, a destra $\frac1{1-4x}$ che è la generatrice dei $4^n$