1

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?

hanugm
  • 2,353
  • 1
  • 13
  • 34
  • 2
    I believe a better statement would be: $$\begin{align}\text{1. } & P(0,0) \ \text{2. } & \forall r, P(n,r) \Longrightarrow \forall r, P(n+1,r)\end{align}$$ or something to that effect. – SlipEternal Aug 09 '18 at 13:45

1 Answers1

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.

BallBoy
  • 14,472