Isso é conteúdo de combinatória, mais especificamente coeficientes binomiais e a famosa identidade de Pascal.
O que vamos precisar:
Entender o que é .
Usar a identidade de Pascal
Passo 2
Primeiro, lembra que é o número de jeitos de escolher itens de um total de .
A identidade de Pascal se explica assim: pra escolher de , ou você inclui um certo elemento “extra” (e aí escolhe dos outros ), ou não inclui (e aí escolhe dos ). Isso dá
Passo 3
Agora aplica Pascal pra cima de binomn+2k+2 = binom(n+1)+1k+2 = binomn+1(k+2)-1 + binomn+1k+2 = binomn+1k+1 + binomn+1k+2 .
Tomamos e . Assim
Passo 4
Agora expandimos cada termo de novo com Pascal:
Para binomn+1k+1 = binomnk + binomnk+1 , use binomn+1k+2 = binomnk+1 + binomnk+2 , :