Inductive proof of symmetric identity of binomial coefficients

Question

I'm trying to proof the symmetric identity ${n \choose k} = {n \choose n-k}$ using induction.

I have the base case $${0 \choose 0} = 1 = {0 \choose 0-0}$$ for k=0 and $${0 \choose k} = 0 = {0 \choose n-k}$$ for every other k>0. My hypothesis is ${n \choose k} = {n \choose n-k}$ for any natural number, and I need to show that ${n+1 \choose k} = {n+1 \choose n-k+1}$. I used Pascal's Identity to show that $${n+1 \choose k} = {n \choose k} + {n \choose k-1}$$ which is equal to $${n! \over (n-k)!k!} = {n! \over (n-k+1)!(k-1)!} $$. At this point I don't know how to go on. I am generally not sure if I have done the induction steps correctly (I am a biology student), and would be very appreciating of any help.

Answer 1

It is more complicated than necessary, but your induction argument can be completed. Starting from $$\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$$ apply the induction hypothesis to both terms on the right side (remember the induction hypothesis applies when the top is $n$ with any value on the bottom), which gives $$\binom{n+1}{k} = \binom{n}{n-k} + \binom{n}{n-k+1}$$ Now apply the Pascal identity once more on the right side, to get what you want: $$\binom{n+1}{k} = \binom{n+1}{n-k+1}.$$

Answer 2

${n \choose k}= \frac{n!}{(n-k)! k!}=\frac{n!}{k! (n-k)!}={n\choose {n-k}}$

Did I misunderstand the purpose of this question?

Answer 3

As k99731 has pointed out, this result follows immediately from the definition.

Instead consider the following recurrence relation $A_{n,k}$ where we define $$ A_{n,k} = A_{n-1,k} + A_{n-1,k-1}$$ for all integers $n$ and integers $k$ such that $1\leq k\leq n$ and set the boundary conditions $A_{n,n}=A_{n,0}=1$ for every integer $n$.

Can you use induction to prove that $A_{n,k}=A_{n,n-k}$ for all $n,k$?

Hint: Let $S(n)$ be the statement that $A_{n,k}=A_{n,n-k}$ for all $1\leq k\leq n$. Can you prove that $S(n+1)$ will be true if $S(n)$ is true?