.Problema: Explorando o coeficiente binomial

Problema
(Indicado a partir do 2º ano do E. M.)

(BENJAMIN, A.T; QUINN, J.J. Proofs that Really Count: The Art of Combinatorial Proof)
Prove que, para quaisquer números naturais

$n\;$ e

$\;k$ , com

$1 \leq k \leq n$ , vale a seguinte igualdade:

$k {\left( \begin{array}{c} n \\ k \end{array} \right)} = n {\left( \begin{array}{c} n-1 \\ k-1 \end{array} \right)}$ .

Lembrete para Solução 1

explicador_p (1) Se $m$ e $p$ são números naturais tais que $p \leqslant m\,$ , definimos o número binomial denotado por $\dbinom{m}{p}$ da seguinte maneira:

$\qquad \boxed{\dbinom{m}{p}=\dfrac{m!}{\left(m-p\right)!\, p!}}\, .$

Solução 1

Sejam

$n\;$ e

$\;k$ números naturais tais que

$1 \leq k \leq n$ .
Usando o Lembrete 1, segue que:

$\qquad k \left(\begin{array}{c} n \\ k \end{array} \right) = k \cdot \dfrac{n!}{k!(n-k)!}\\ \qquad k \left(\begin{array}{c} n \\ k \end{array} \right) = \dfrac{k \cdot n \cdot (n-1)!}{k \cdot (k-1)! \cdot (n-k)!}\\ \qquad k \left(\begin{array}{c} n \\ k \end{array} \right) = n \cdot \dfrac{(n-1)!}{(k-1!) \cdot (n-k)!}\\ \qquad \boxed{k \left(\begin{array}{c} n \\ k \end{array} \right) = n\left( \begin{array}{c} n-1 \\ k-1 \end{array} \right)} \,.$

Solução elaborada pelos Moderadores do Blog.

Lembretes para Solução 2

explicador_p (2) Uma das maneiras de agruparmos elementos de um dado conjunto é escolhê-los levando-se em consideração apenas a sua natureza, sem se importar em que ordem eles foram escolhidos ou apresentados. Esse tipo de agrupamento de elementos é denominado uma Combinação simples. Particularmente, quando escolhemos $p$ dentre $m$ elementos de um conjunto dessa forma, dizemos que estamos definindo uma Combinação simples de $m$ elementos tomados $p$ a $p$ . A quantidade desse tipo de agrupamentos é denotada por $C_{m,\,p}$ ou $C_m^p\,$ e equivale ao número binomial ${\left( \begin{array}{c} m \\ p \end{array} \right)}$ :
$\qquad C_{m,\,p}=C_m^p={\left( \begin{array}{c} m \\ p \end{array} \right)}=\dfrac{m!}{(m-p)!\,p!} \text{ , com } m,p\in\mathbb{N} \text{ e }p\leqslant m$ .

(3) Princípio Fundamental da Contagem, ou Princípio Multiplicativo, para duas decisões:
Se uma decisão A pode ser tomada de $m$ maneiras distintas e, tomada essa decisão A, uma decisão B puder ser tomada de $n$ maneiras distintas, então a quantidade de maneiras de se tomar sucessivamente as decisões A e B é igual a $~\boxed{ m \times n}\, .$
(Se você não se lembra desse Princípio, seria interessante dar uma passadinha nesta Sala de Estudo.)

Solução 2

Diferente da prova algébrica da Solução 1, procuraremos oferecer agora uma resolução combinatória mais intuitiva. Imagine que, em uma sala de aula, há

$n$ alunos e queremos formar um Clube com

$k$ alunos, dentre os quais um será o líder.
Podemos pensar de duas formas diferentes; vejamos:

Dos $n$ alunos, vamos escolher $k$ alunos para o Clube, o que podemos fazer de $C_n^k\,={\left( \begin{array}{c} n \\ k \end{array} \right)}$ maneiras. Em seguida, escolhemos o líder, o que pode ser feito de $k$ formas distintas.
Logo, segue do Princípio Multiplicativo que podemos formar o Clube com líder de
$\qquad \qquad k {\left( \begin{array}{c} n \\ k \end{array} \right)}$ maneiras distintas. $\qquad \textcolor{#800000}{(i)}$
Por outro lado, podemos primeiro escolher um dentre os $n$ alunos para ser o líder do Clube que será formado. Daí, sobram $n-1$ alunos e precisamos escolher dentre eles $k-1$ para completar a formação do Clube.
Segue do Princípio Multiplicativo que há
$\qquad \qquad n\, C_{n-1}^{k-1}\,=n{\left( \begin{array}{c} n-1 \\ k-1 \end{array} \right)}$ possibilidades de montar o Clube. $\qquad \textcolor{#800000}{(ii)}$

Portanto, por $\textcolor{#800000}{(i)}$ e $\textcolor{#800000}{(ii)}$ , segue que $\boxed{k {\left( \begin{array}{c} n \\ k \end{array} \right)} = n {\left( \begin{array}{c} n-1 \\ k-1 \end{array} \right)}}$ .

Solução elaborada pelos Moderadores do Blog.