How do I build a combinatorial proof of the following recursion:
$$\binom {n}{k} = (k+1)\binom {n-1}{k}+(n-k)\binom {n-1}{k-1}$$
I'm having really big difficulties in finding the right way to realize the solution...I'm not even sure if the problem is solvable by the means of combinatorial reasoning...
Professor reminded us to use similar way of thinking as applied in the case of Stirling numbers of first and second kind...
This is not a combinatorial identity! For example $$\binom{7}{6}=7 \neq 7\binom{6}{6}+1\binom{6}{5}=7+6=13$$ Then, you have $$(k+1)\binom {n-1}{k}+(n-k)\binom {n-1}{k-1} = (k+1)\left(\frac{n-2k}{n}\binom{n}{k}+ \binom {n-1}{k-1}\right)+(n-k)\binom {n-1}{k-1}=\frac{k(n-2k)}{n}\binom{n}{k}+k\binom {n-1}{k-1}+\frac{n-2k}{n}\binom{n}{k}+ \binom {n-1}{k-1}+n\binom {n-1}{k-1}-k\binom {n-1}{k-1}=(n-2k)\binom{n-1}{k-1}+\frac{n-2k}{k}\binom{n-1}{k-1}+(n+1)\binom{n-1}{k-1}=\left(n-2k+\frac{n-2k}{k}+n+1\right)\binom{n-1}{k-1}=\frac{2nk+n-k-2k^2}{k}\binom{n-1}{k-1}=\frac{2nk+n-k-2k^2}{n}\binom{n}{k}=\binom{n}{k}\Rightarrow 2nk+n-k-2k^2=n \Rightarrow k=0 \text{ or } k = \frac{2n-1}{2}=n-\frac12$$ The last solution is not valid, as $n \in \Bbb{N} \Rightarrow n-\frac12=k \notin \Bbb{N}$ so $k!$ is not defined. The solution $k=0$ is not acceptable too, as $-1!$ doesn't exist $\to$ there are no solutions $\in \Bbb{N}$