How to know the statement on natural numbers is univariate or bivariate for induction

Question

In order to prove the following recurrence

$$\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}$$

It is enough to prove induction on only $n$, not needed to do induction on $r$. That is

1. $P(0,0)$
2. $P(n,r) \implies P(n+1, r)$

But by seeing the equation, $P(n,r)$ appears to be like statement over two variables . That is we need to do induction on two variables as follows

1. $P(0,0)$
2. $P(n,r) \implies P(n+1,r)$
3. $P(n,r) \implies P(n, r+1)$

How to decide univariate or bivariate unambiguously?

Answer 1

There are (at least) four ways to prove a bivariate statement $P(n,r)$:

• Prove $P(n,r)$ for arbitrary $n$ and $r$ (no induction)
• Prove $P(0,r)$ for arbitrary $r$, and then prove $P(n,r) \implies P(n+1,r)$ again for arbitrary $r$ (univariate induction on $n$)
• Prove $P(n,0)$ for arbitrary $n$, and then prove $P(n,r) \implies P(n,r+1)$ again for arbitrary $n$ (univariate induction on $r$)
• Prove $P(0,0)$, prove $P(n,r) \implies P(n+1,r)$, and prove $P(n,r) \implies P(n,r+1)$ (bivariate induction)

Which one you use depends on what can be proven in the particular problem, and in many cases more than one method will work.