Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction with more than one variable

  1. Nov 16, 2008 #1
    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. jcsd
  3. Nov 16, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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!
     
  4. Nov 16, 2008 #3
    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?
     
  5. Nov 16, 2008 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    ??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.
     
  6. Nov 17, 2008 #5
    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?
     
  7. Nov 17, 2008 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    IF you can prove it for arbitrary n, yes.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?