For $n \in {\mathbb{N}_{0}}$ and $k \in \mathbb{Z}$ let
$F(n,k) := \begin{cases} 1 \hspace{1cm} \text{if} \hspace{0.2cm} n=k=0, \\
0 \hspace{1cm} \text{if} \hspace{0.2cm} k < 0 \hspace{0.2cm} \text{or} \hspace{0.2cm} k > 0, \\
F(n-1,k-1) + F(n-1,k) \hspace{0.2cm} else \end{cases}$
Then show that $F(n,k)= F(n,n-k)$
So obviously this is the very definition of the binomial coefficent, however we should prove this without using the characteristics of the binomial coefficient. I thought maybe induction would be a good idea?
Start: $n=3, k=1$ (I am not using $n=2$ for obvious reasons)
$F(3,1) = F(2,0) + F(2,1)$
$F(2,0) = F(1,-1) + F(1,0)$
$F(1,-1) = 0$ per definition, then
$F(1,0) = F(0,-1) + F(0,0) (=1)$
so for $F(2,0) = 0 + 1 = 1$
now $F(2,1) = F(1,0) + F(1,1) = 1 +1$
$\vdots$
so to sum it up $F(3,1) = 3 = F(3,2)$
Induction hypothesis: $n \rightarrow n+1$
we need to show that $F(n+1,k) = F(n+1,n+1-k)$
we know that $F(n+1,k) = F(n,k-1) + F(n,k)$
for $F(n,k)$ we can use $F(n,n-k)$
so $F(n+1,k) = F(n,k-1) + F(n,n-k)$
However from there I do not know what to do?
Best Answer
Use it also for the other summand. i.e., $$F(n,k-1)=F(n,n-k+1),$$ you will end up with $$F(n,n-k+1)+F(n,n-k)=F(n+1,n-k+1)$$