Induction with more than one variable

[µ³]

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 !?

 

[HallsofIvy]

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 !?

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!

 

[µ³]

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!

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?

 

[HallsofIvy]

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?

??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.

 

[µ³]

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?

 

[HallsofIvy]

IF you can prove it for arbitrary n, yes.