Combinatorial proof for $n > k > 0$:
$$\sum_{j=0}^n {{k}\choose{j}} {{n-k}\choose{j}} = {{n}\choose{k}}$$
I don't get why would that work. On the RHS I just choose $k$ elements from $n$ avaliable. I know that $n > k$ so thats valid.
On the LHS I choose $j$ elements from $k$ avaliable and that j $\in [0, n]$, but $n>k$ so at some point that doesn't make sense.
Also the whole meaning of LHS: I choose $j$ elements from $k$ avaliable, then $j$ elements from $n- k$ avaliable (because $k$ are already chosen). So I end up with $2 \times j$ elements chosen from $n$ avaliable separated by some "inner group border" so to say (namely, $k$).
Does anybody understand any of that? Thanks in advance!
In the name of God
Let me explain you with an example. Let n = 5, k =2. For example you have five letters A,B,C,D,E and you want to choose two letters from them . One way is choosing 2 from 5. (RHS)
Another way, is dividing these five letters into two groups randomly.( in a way that first group has n-k elements and second group has k elements).
For example A,B,C is the first group and D,E is the second group. By choosing n letters from first group and n letters from the second group, you choose the letters that are going to relocate with each other. when you choose 0 from first group and 0 from second group, the groups remain unchanged. when you choose 1 from first group and 1 from second group, there are $\binom{3}{1}$ $\binom{2}{1}$ = 6 ways that the groups can exchange one of their letters, and so on.
And of course, the second group that has k elements gives you the combinations. which equals LHS.
I hope you've understood. Algebraic proof should be easier, BTW.