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

Homework Help: Ramsey number inequality problem

  1. Jul 5, 2011 #1
    Prove that
    [itex]R(p,q) \leq \left(\stackrel{p+q-2}{p-1}\right) [/itex]
    where [itex]p [/itex] and [itex]q[/itex] are positive integers

    I'm supposed to use induction on the inequality [itex]R(p,q) \leq R(p-1,q) + R(p,q-1) [/itex], but I'm having difficulty there.

    How do I go about doing this? I can show it's true for [itex]p=q=1[/itex].
    But, I can't see how I get the combination in the first inequality from an induction on the second inequality (which doesn't contain a combination) ...
    1. The problem statement, all variables and given/known data

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Jul 5, 2011 #2
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook