# Induction with more than one variable

1. Nov 16, 2008

### µ³

Suppose we have a statement (say an equation) P(n, m), and we want to prove it works for arbitrary n and m.

Either

(1) It is sufficient to define Q(n) = P(n,m) or R(m) = P(n,m) and prove either Q(n) or R(m) by induction

(2) It is necessary to prove that P(n,m) => P(n+1,m) and P(n, m) => P(n, m+1), in addition to the base cases, to show that it works for arbitrary n and m.

Which one is correct !?

2. Nov 16, 2008

### HallsofIvy

If in (1) you prove Q(n) for ALL n or prove R(n) for ALL m, that would be sufficient. That would, in most cases involve proving P(n,m)=> P(n+1, m) to prove R(m) for a specific m, and then do another induction, proving R(m)=> R(m+1) to prove it true for ALL m. In other words, the two are really the same!

3. Nov 16, 2008

### µ³

The thing that confuses me is that for example to prove the binomial theorem, which is a statement P(x,y,n), we can simply prove that P(x,y,n) => P(x,y, n+1) and we don't have to prove it for all x and y, as we can just leave them arbitrary. Similarly why can't we prove, P(n,m) by proving P(n,m) => P(n, m+1), leaving n arbitrary and then assuming since we left n arbitrary that it will work for all n?

4. Nov 16, 2008

### HallsofIvy

??But x and y are not integers so you wouldn't use "induction" on them anyway! Leaving x and y arbitrary- so that they can be any real numbers- does prove it for all x and y.

5. Nov 17, 2008

### µ³

So what if P(n, 1) is trivially true for arbitrary n, then surely we can prove P(n, m) by showing P(n, m) => P(n, m+1) without having to do induction on n?

6. Nov 17, 2008

### HallsofIvy

IF you can prove it for arbitrary n, yes.