Mathematical induction on binomial coefficients

Question

I need to prove the following statement (Pascals Identity) on binomial coefficients using mathematical induction only

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

My doubt is

Whether I need to prove the following two statements or only the first one?

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

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

Your question is unclear, the answer depends on the initial definition you are given of $\binom nr$. — Nicolas FRANCOIS, Aug 09 '18 at 12:12
Induction has a starting point, which affects the inductive step. Possibilities here include (a) ${0 \choose 0}=1$ and ${n \choose 0}=0$ for $n \not = 0$ or (b) ${n \choose 0}={n \choose n} = 1$ for non-negative integers $n$. — Henry, Aug 09 '18 at 12:20
How would you show $\binom{n+1}{n+1} = \binom{n}{n+1}+\binom{n}{n}$ or $\binom{n}{n} = \binom{n-1}{n}+\binom{n-1}{n-1}$ when you do not have a definition for $\binom{n}{n+1}$ or $\binom{n-1}{n}$? — Henry, Aug 09 '18 at 12:28
If your definition is that, you don't need induction. Just don't make any hypothesis on $n$ or $r$ (other than $n\ge1$ and $1\le r\le n-1$). — Nicolas FRANCOIS, Aug 09 '18 at 12:29

score 1 · Answer 1 · answered Aug 09 '18 at 12:29

For Mathematical induction, you prove $$\binom{n}{r} = \binom{n-1}{r}+\binom{n-1}{r-1}$$

for $n=1$.

Then assume that $$\binom{n}{r} = \binom{n-1}{r}+\binom{n-1}{r-1}$$ is true for $n=k$, and prove it for $n=k+1$

You do not need to change $r$ to $r+1$

This problem may be easier to solve without Mathematical Induction, but it is your choice.

1 Answers1