# Combinations - Solving recurrence relation in 2 variables without using generating functions

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.

• I like your approach, but I would like one where the mathematician didn't know what are binomial coefficients – 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.