Demonstração da convolução de Vandermonde-Relação de Euler

Renji

Vamos provar a seguinte identidade

\sum\limits^{k}_{p=0}{r \choose p}{s \choose k-p}={r+s \choose k}

conhecida como convolução de Vandermonde ou Relação de Euler. Faremos a prova de várias maneiras distintas.

Demonstração por interpolação de Newton

Usamos a interpolação de Newton na função f,
f(n+x_{0})=\sum\limits^{n}_{k=0}{n \choose k} \Delta^k f(x_{0})

onde \Delta^k f(x_{0}) é a k– ésima diferença aplicada em x_0, isto é, aplicação do operador \Delta f(x)=f(x+1)-f(x) k vezes,

tomando f(n+x_{0})={n+x_{0}\choose p} temos \Delta^{k}f(x_{0})={x_{0}\choose p-k} pela aplicação sucessiva da Relação de Stifel, daí

{n+x_{0}\choose p}=\sum\limits^{n}_{k=0}{n \choose k}{x_{0}\choose p-k}.

Outra demonstração algébrica

Daremos agora uma segunda demonstração algébrica, bem conhecida.

(1+x)^{r}=\sum\limits^{r}_{k=0}{r \choose k}x^{k}

(1+x)^{s}=\sum\limits^{s}_{k=0}{s \choose k}x^{k}

(1+x)^{r}(1+x)^{s}=(1+x)^{r+s}=\sum\limits^{r+s}_{k=0}{r+s \choose k}x^{k}

porém (1+x)^{r}(1+x)^{s}=(1+x)^{r+s}, vamos então multiplicar
os dois fatores

(1+x)^{r}(1+x)^{s}=\sum\limits^{r}_{k=0}{r \choose k}x^{k}\sum\limits^{s}_{k=0}{s \choose k}x^{k}

pela regra do produto de polinômios temos

\sum\limits^{r}_{k=0}{r \choose k}x^{k}\sum\limits^{s}_{k=0}{s \choose k}x^{k}=\sum\limits^{r+s}_{k=0}c_{k}x^{k}

onde

c_{k}=\sum\limits^{k}_{p=0}{r \choose p}{s \choose k-p} igualamos então

\sum\limits^{r+s}_{k=0}{r+s \choose k}x^{k}=\sum\limits^{r+s}_{k=0}c_{k}x^{k}

logo

c_{k}={r+s \choose k}=\sum\limits^{k}_{p=0}{r \choose p}{s \choose k-p}.

Demonstração por derivação

Usando a fórmula de Leibniz da n-ésima derivada do produto de duas funções

D^n f. g = \sum\limits^{n}_{k=0} {n \choose k} (D^k f ) (D^{n-k} g) .

Usamos novamente que (1+x)^{r+s} = (1+x)^s (1+x)^r e aplicamos a n-ésima derivada nas duas expressões em um ponto x=0,

vale que D^k(1+x)^s = k! {s \choose k} (1+x)^{s-k} , D^{n-k}(1+x)^r = (n-k)! {r \choose n-k} (1+x)^{r-n+k}, D^n (1+x)^{r+s}= n!{r+s \choose n} (1+x)^{r+s-n} , aplicando no ponto x=0 e usando a fórmula de Leibniz tem-se

n!{r+s \choose n} = \sum\limits^{n}_{k=0} {n \choose k} (n-k)! k! {r \choose n-k} {s \choose k}

dividindo por n! chegamos no desejado

{r+s \choose n} = \sum\limits^{n}_{k=0} {r \choose n-k} {s \choose k}
pois o termo {n \choose k} é cancelado .

Demonstração por indução
Vamos provar a identidade
{x+s \choose n}= \sum\limits^{n}_{k=0} {s \choose k } {x \choose n-k }
por indução sobre s.

Para s=0
{x \choose n}= \sum\limits^{n}_{k=0} {0 \choose k } {x \choose n-k }= {x \choose n }
logo a identidade vale, independente do valor n.

Suponha validade para s
{x+s \choose n}= \sum\limits^{n}_{k=0} {s \choose k } {x \choose n-k }

(independente do valor em n )
vamos provar para s+1

{x+s+1 \choose n}= \sum\limits^{n}_{k=0} {s+1 \choose k } {x \choose n-k }.
Pela relação de Stifel vale

{x+s+1 \choose n} = {x+s \choose n} + {x+s \choose n-1}

usamos a hipótese da indução para esses dois fatores da relação de Stifel
{x+s+1 \choose n}= \sum\limits^{n}_{k=0} {s \choose k } {x \choose n-k } + \sum\limits^{n-1}_{k=0} {s \choose k } {x \choose n-1-k } =

={s \choose 0 } {x \choose n } +\sum\limits^{n}_{k=1} {s \choose k } {x \choose n-k } + \sum\limits^{n}_{k=1} {s \choose k-1 } {x \choose n-k } =

= {s+1 \choose 0 } {x \choose n } +\sum\limits^{n}_{k=1} \underbrace{({s \choose k } + {s \choose k-1 })}_{{s+1 \choose k }} {x \choose n-k }= \sum\limits^{n}_{k=0} {s+1 \choose k } {x \choose n-k } .

Vejamos agora um corolário direto desse resultado
Corolário
Em
\sum\limits^{k}_{p=0}{r \choose p}{s \choose k-p}={r+s \choose k}

tomando r=s=k segue

\sum\limits^{k}_{p=0}{k \choose p}{k \choose k-p}={2k \choose k}

usando que {k \choose k-p} = {k \choose p} temos finalmente

\sum\limits^{k}_{p=0}{k \choose p}^2={2k \choose k}.

Apêndice: Dedução da fórmula de Interpolação De Newton

Vamos deduzir a identidade f(n+x_{0})=\sum\limits^{n}_{k=0}{n \choose k} \Delta^k f(x_{0}) que usamos na primeira demonstração, a dedução dela pode ser feita de maneira muito simples.
Sabemos que
\Delta f(x) =f(x+1) - f (x) , denotando E^k f(x)=f(x+k) temos

\Delta f(x) = (E-1) f (x) daí \Delta =E-1 , E = (\Delta +1), elevamos à n e expandimos por binômio de Newton no segundo membro

E^n = \sum\limits^n_{k=0} {n \choose k} \Delta^k
aplicamos em f(x_0) , logo

E^n f(x_0) = \sum\limits^n_{k=0} {n \choose k} \Delta^k f(x_0)

ou de forma equivalente

f(n+x_0) = \sum\limits^n_{k=0} {n \choose k} \Delta^k f(x_0)

essa identidade pode ser usada para deduzir outros resultados de teoria dos números.

Download
Na pasta abaixo ( no 4shared), temos dois textos sobre coeficiente binomial (de minha autoria), neles se encontram essas demonstrações e muitas outras
Download

Deixe um comentário