I know that there are similar questions here solving 2 variable recurrence and combinations recurrence equation, but both of them use generating functions to solve this. Is there any other way to solve this problem:

$$\Psi(n,k) = \begin{cases} 0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{ if } n = 0 \text{ and } k > 0\\ 1 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{ if } n \geq 0 \text{ and } k=0\\ \Psi(n-1,k) + \Psi(n-1,k-1)\;\;\text{ if } n > 0 \text{ and } k > 0\\ 0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{ otherwise} \end{cases}$$

I know the solution is $\binom{n}{k}$, but I would like to know a way to solve this without generating functions.


The most natural way to solve this is the following: I'd start by making a table up to $n=5$ or so and then say "Ah, these are just the binomial coefficients". Then I'd set up an induction proof that this is indeed the case.

  • $\begingroup$ I like your approach, but I would like one where the mathematician didn't know what are binomial coefficients $\endgroup$ – pedroth Jul 20 '18 at 9:59

Following the idea of @Christian Blatter, I find $\Psi$ for $k=0\dots 2$: $$\Psi(n,0) = 1$$ $$\Psi(n,1) = n = n[1]$$ $$\Psi(n,2) = \frac{n(n-1)}{2} = \frac{n-1}{2}[n][1]$$

My guess for $\Psi(n,3)$ will be:

$$\Psi(n,3) = \frac{(n-2)}{3}\left [\frac{n(n-1)}{2} \right]$$

The pattern seems to be: $$\Psi(n, k) = \frac {n -(k-1)}{k} \Psi(n, k-1)\;\;\;(1)$$

From (1) recursion is easy to get the combinatorial formula: $$\Psi(n, k) = \binom{n}{k}$$

Then make the proof by induction as @Christian Blatter said.

I wrote more details for this answer here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.