Demonstração - Propriedade do Triângulo de Pascal (Teorema das Colunas)
Enviado: 06 Jun 2020, 10:05
Teorema das Colunas:
Prove que
[tex3]\binom{n}{n}+\binom{n+1}{n}+...+\binom{n+k}{n}=\binom{n+k+1}{n+1}\tag*{}[/tex3]
Podemos mostrar esse teorema de diferentes formas. Hoje vou fazer uma demostração que usa argumentos da Análise Combinatória. Vamos lá!
Seja o conjunto [tex3]A=\{1,2,...,n+k+1\}[/tex3]. Vamos calcular a quantidade de subconjuntos de [tex3]A[/tex3] com [tex3](n+1)[/tex3] elementos.
A maneira mais direta de fazermos isso é através de [tex3]\binom{n+k+1}{n+1}[/tex3]. Mas, e se o fizermos de outra maneira? O resultado, naturalmente, deve ser o mesmo. Note que todo subconjunto que nós podemos formar com esses elementos, obviamente, possui um elemento máximo, isto é, um elemento de maior valor. Assim, nós podemos contar a quantidade de subconjuntos de [tex3]A[/tex3] com [tex3](n+1)[/tex3] elementos de outra forma.
1) Se o maior elemento é [tex3](n+1):[/tex3]
Nesse caso, resta-nos [tex3]n[/tex3] elementos e podemos escolher [tex3]n[/tex3] elementos dentre eles de [tex3]\binom{n}{n}[/tex3] maneiras.
2) Se o maior elemento é [tex3](n+2):[/tex3]
Nesse caso, resta-nos [tex3](n+1)[/tex3] elementos e podemos escolher [tex3]n[/tex3] elementos dentre eles de [tex3]\binom{n+1}{n}[/tex3] maneiras.
3) Se o maior elemento é [tex3](n+3):[/tex3]
Nesse caso, resta-nos [tex3](n+2)[/tex3] elementos e podemos escolher [tex3]n[/tex3] elementos dentre eles de [tex3]\binom{n+2}{n}[/tex3] maneiras.
Acho que já deu para pegar o padrão.
Podemos fazer isso até o caso em que o maior elemento é [tex3](n+k+1)[/tex3], o que nos dá [tex3]\binom{n+k}{n}[/tex3] maneiras.
Somando as maneiras de todos os casos, temos, então, a quantidade de subconjuntos de [tex3]A[/tex3] com [tex3](n+1)[/tex3] elementos, o que já sabemos que vale [tex3]\binom{n+k+1}{n+1}.[/tex3]
Portanto, está provado que
[tex3]\binom{n}{n}+\binom{n+1}{n}+...+\binom{n+k}{n}=\binom{n+k+1}{n+1}\tag*{}[/tex3]
[tex3]\text{QED}\\\blacksquare[/tex3]
Prove que
[tex3]\binom{n}{n}+\binom{n+1}{n}+...+\binom{n+k}{n}=\binom{n+k+1}{n+1}\tag*{}[/tex3]
Podemos mostrar esse teorema de diferentes formas. Hoje vou fazer uma demostração que usa argumentos da Análise Combinatória. Vamos lá!
Seja o conjunto [tex3]A=\{1,2,...,n+k+1\}[/tex3]. Vamos calcular a quantidade de subconjuntos de [tex3]A[/tex3] com [tex3](n+1)[/tex3] elementos.
A maneira mais direta de fazermos isso é através de [tex3]\binom{n+k+1}{n+1}[/tex3]. Mas, e se o fizermos de outra maneira? O resultado, naturalmente, deve ser o mesmo. Note que todo subconjunto que nós podemos formar com esses elementos, obviamente, possui um elemento máximo, isto é, um elemento de maior valor. Assim, nós podemos contar a quantidade de subconjuntos de [tex3]A[/tex3] com [tex3](n+1)[/tex3] elementos de outra forma.
1) Se o maior elemento é [tex3](n+1):[/tex3]
Nesse caso, resta-nos [tex3]n[/tex3] elementos e podemos escolher [tex3]n[/tex3] elementos dentre eles de [tex3]\binom{n}{n}[/tex3] maneiras.
2) Se o maior elemento é [tex3](n+2):[/tex3]
Nesse caso, resta-nos [tex3](n+1)[/tex3] elementos e podemos escolher [tex3]n[/tex3] elementos dentre eles de [tex3]\binom{n+1}{n}[/tex3] maneiras.
3) Se o maior elemento é [tex3](n+3):[/tex3]
Nesse caso, resta-nos [tex3](n+2)[/tex3] elementos e podemos escolher [tex3]n[/tex3] elementos dentre eles de [tex3]\binom{n+2}{n}[/tex3] maneiras.
Acho que já deu para pegar o padrão.
Podemos fazer isso até o caso em que o maior elemento é [tex3](n+k+1)[/tex3], o que nos dá [tex3]\binom{n+k}{n}[/tex3] maneiras.
Somando as maneiras de todos os casos, temos, então, a quantidade de subconjuntos de [tex3]A[/tex3] com [tex3](n+1)[/tex3] elementos, o que já sabemos que vale [tex3]\binom{n+k+1}{n+1}.[/tex3]
Portanto, está provado que
[tex3]\binom{n}{n}+\binom{n+1}{n}+...+\binom{n+k}{n}=\binom{n+k+1}{n+1}\tag*{}[/tex3]
[tex3]\text{QED}\\\blacksquare[/tex3]