Proof by induction (combinations): $\binom n1 =n$ and $\binom n{n-1}=n$

Question

We are supposed to prove this via induction. I originally solved it with simple algebra, showing that $n = n$ and $n+1 = n+1$, but a friend told me that wasn't really solving it by induction and said it could be solved via induction using ${n \choose k-1} + {n \choose k} = {n + 1 \choose k}$. But I don't remotely see how to use that?

The question:

14.) Prove by induction that for each $n \in \mathbb N$, ${n \choose 1} = n$ and ${n \choose n - 1} = n$

Thank you.

Answer 1

See http://en.wikipedia.org/wiki/Mathematical_induction

There are 2 steps in an inductive proof:

1. Demonstrate it is correct for the base case ($n=1$)
2. Show that if it is correct for $n=k$ then it is also true for $n=k+1$

It appears that you have carried out step 2 using algebra (by which I assume that you mean working from the definition of combinations) - this is perfectly sensible and correct. Your friend has suggested using a short-cut identity, however, you would probably need to prove the identity before you could use it.

Have you carried out step 1?

Answer 2

Base case, $n=1$: Since there is only one way to either choose or not choose an object from a set of size $1$, we have $$ \binom{1}{1}=\binom{1}{0}=1 $$

Induction hypothesis: For all $k\le n$ we have $$ \binom{k}{1}=\binom{k}{k-1}=k. $$

Induction: Consider the case $k=n+1$ then we have $$ \binom{n+1}{1}=\binom{n}{1}+\binom{n}{0}=n+1, $$ using the induction hypothesis on $\binom{n}{1}$. Similarly we have $$ \binom{n+1}{n}=\binom{n}{n}+\binom{n}{n-1}=1+n, $$ using the Induction hypothesis on $\binom{n}{n-1}$.