Aloha :)
Die Formel kann man nicht beweisen, weil sie falsch ist. Du meinst vermutlich:$$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$$
Das kannst du durch direkte Rechnung zeigen:$$\binom{n-1}{k}+\binom{n-1}{k-1}=\frac{(n-1)!}{k!\cdot((n-1)-k)!}+\frac{(n-1)!}{(k-1)!\cdot(\underbrace{(n-1)-(k-1)}_{=n-k})!}$$$$\qquad=\frac{(n-1)!}{k!\cdot(n-k-1)!}+\frac{(n-1)!}{(k-1)!\cdot(n-k)!}$$$$\qquad=\frac{(n-1)!\cdot(n-k)}{k!\cdot\underbrace{(n-k-1)!\cdot(n-k)}_{=(n-k)!}}+\frac{(n-1)!\cdot k}{\underbrace{(k-1)!\cdot k}_{=k!}\cdot(n-k)!}$$$$\qquad=\frac{(n-1)!\cdot(n-k)}{k!\cdot(n-k)!}+\frac{(n-1)!\cdot k}{k!\cdot(n-k)!}=\frac{(n-1)!\cdot n-(n-1)!\cdot k}{k!\cdot(n-k)!}+\frac{(n-1)!\cdot k}{k!\cdot(n-k)!}$$$$\qquad=\frac{(n-1)!\cdot n}{k!\cdot(n-k)!}=\frac{n!}{k!(n-k)!}=\binom{n}{k}$$
