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 &gt; 0\\
                1 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{ if } n \geq 0 \text{ and
                } k=0\\
                \Psi(n-1,k) + \Psi(n-1,k-1)\;\;\text{ if } n &gt; 0 \text{ and } k &gt; 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.
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.