Os termos \binom{n}{k} são os coeficientes binomiais (devem ser entendidos e manipulados).
Devemos usar indução matemática: verificar um caso base e mostrar que, se a propriedade vale para n, então vale para n+1.
O enunciado pede ainda para mostrar a aplicação da regra da adição na relação de Stifel (ou seja, usar a identidade de Stifel \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k} de forma explícita).
Passo 2
Primeiro, entenda o que é \binom{n}{k}. Definição e significado:
Definição algébrica: para inteiros n\ge 0 e 0\le k\le n,
\binom{n}{k}=\dfrac{n!}{k!(n-k)!},
onde m! (fatorial) é m!=m\cdot(m-1)\cdots 2\cdot1 e por convenção 0!=1.
Interpretação combinatória: \binom{n}{k} é o número de maneiras de escolher k elementos dentre n sem ordem (combinações).
Exemplo rápido: \binom{4}{1}=4 e \binom{4}{2}=6.
Passo 3
Apresentar e provar a relação de Stifel (regra da adição):
A relação de Stifel é
\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k},
válida para n\ge 1 e 1\le k\le n-1. Vou mostrar duas ideias (combinatória e algébrica) — escolha a que preferir na prova de indução.
Combinatória (intuição da regra da adição):
Considere escolher k elementos dentre n marcados. Pegue um elemento especial x.
Todas as escolhas de k elementos se dividem em duas classes disjuntas:
As escolhas que incluem x. Para essas, além de x escolhe-se k-1 entre os n-1 restantes: total \binom{n-1}{k-1}.
As escolhas que não incluem x. Para essas, escolhe-se k entre os n-1 restantes: total \binom{n-1}{k}.
Como as duas classes cobrem todas as escolhas e são disjuntas, o total é a soma, obtendo a identidade.
Repare que a primeira soma \sum_{k=1}^{n}\binom{n}{k-1} é, com mudança de índice j=k-1, exatamente \sum_{j=0}^{n-1}\binom{n}{j}; e a segunda soma \sum_{k=1}^{n}\binom{n}{k} é \sum_{j=1}^{n}\binom{n}{j}. Assim, juntando tudo de maneira clara:
Ou seja, a soma dos coeficientes na linha n+1 se transformou em duas cópias da soma dos coeficientes na linha n. Usando a hipótese de indução \sum_{j=0}^{n}\binom{n}{j}=2^{n}, obtemos
Como a igualdade vale para n=0 (caso base) e mostramos que, sempre que vale para um n, vale para n+1, segue por princípio da indução matemática que a igualdade vale para todo n\in\mathbb{N}.
Comentário final sobre a “aplicação da regra da adição na relação de Stifel”: a identidade de Stifel foi aplicada explicitamente na transformação de cada \binom{n+1}{k} (com 1\le k\le n) em \binom{n}{k-1}+\binom{n}{k}, o que permitiu reescrever a soma na forma de duas somas iguais sobre a linha n.