0

We observe from Pascal's triangle that

$$\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$$

We prove this statement correct by expanding the right side:

$$\frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{(k)!(n-k)!}\rightarrow\frac{(n+1)!}{k!(n-k+1)!} $$

Next we assume that it is also true for some number $n+1$:

$$\binom{n+1}{k-1}+\binom{n+1}{k}$$

This is equivalent to:

$$\binom{n+1}{k-1}+\binom{n}{k-1}+\binom{n}{k}$$

Expanding we get:

$$\binom{n+1}{k-1}+\binom{n}{k-1}+\binom{n}{k}\rightarrow\binom{n+2}{k}$$

Which should make the proof complete since we can assert that because of this condition: $0\le k\le n$, and by proving the equality below, all other numbers, being recursively defined, are also natural numbers.

$$\binom{1}{0}=\binom{1}{1}=1$$

Misha.P
  • 221
  • your proof looks correct to me – Guy Fsone Jan 24 '18 at 20:00
  • 2
    You can prove that $\binom{n}{k}$ is an integer by proving it counts something, namely, the $k$-subset of an $n$-element set. How you do this is up to you, however. For example, you can show that if $B(n,k)$ is such number, then both $\binom{n}{k}$ satisfy the rule you use above, and agree at initial values, hence showing they are the same number. This is essentially what you are proving, but it sheds some light on why they should be integers to begin with, and generalizes quite nicely. – Pedro Jan 24 '18 at 20:03
  • The original statement is obvious just by counting $k$-element subsets... –  Jan 24 '18 at 20:03

0 Answers0