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

Prove this!

  1. Jan 7, 2005 #1

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    I thought up this little problem last night (hopefully it's not too easy):


    If n,m,p,q are postive integers and:

    [tex]\frac{(n+m-1)^2 +n -m +1}{2} = \frac{(p+q-1)^2 +p -q +1}{2}[/tex]

    Prove that n=p and m=q
     
  2. jcsd
  3. Jan 8, 2005 #2

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    Isn't anyone going to have a go at it?

    Is it too easy? Too difficult? Just boring?
     
  4. Jan 8, 2005 #3

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Too scary ! :eek: What background is needed to crack this (who is it accessible to) ?
     
  5. Jan 8, 2005 #4

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    The maths is all fairly simple, you can solve it without expanding the brackets.
     
  6. Jan 8, 2005 #5

    Curious3141

    User Avatar
    Homework Helper

    I think I've got it, although it's not the most elegant proof in the world. Let :

    [tex]a = n + m - 1[/tex]

    Note that since we're given that n and m are both positive integers, [itex]n+m \geq 2[/itex] giving [itex]a \geq 1[/itex]

    Then the expression on the LHS reduces to :

    [tex]\frac{1}{2}(a^2 -a) + n = n + \frac{1}{2}a(a-1)[/tex]

    Let [itex]f(a) = \frac{1}{2}a(a-1)[/itex]Sketching the graph of [itex]f(a)[/itex] over [itex]a[/itex] reveals that for the domain of [itex]a \geq 1[/itex], the function is injective.

    Now the original LHS (let that be represented by [itex]g(a,n)[/itex]) is :

    [tex]g(a,n) = n + f(a)[/tex]

    Note that if [itex]n[/itex] changes, [itex]f(a)[/itex] will change in the same direction, implying that for a given value of [itex]g(a,n)[/itex] there can be only one particular pair of values [itex]n[/itex] and [itex]f(a)[/itex].

    We've already established that [itex]f(a)[/itex] is injective for the domain under consideration, so for a particular value of [itex]f(a)[/itex], there is only one value of [itex]a[/itex].

    For a particular value of [itex]a[/itex], there is only one particular value of the expression [itex](n+m)[/itex], further implying that given a value for [itex]n[/itex], the value for [itex]m[/itex] is fixed.

    Connecting up the chain of reasoning above,

    One value of the LHS in the original identity implies one value of [itex]m[/itex] and one value of [itex]n[/itex] giving the required proof.
     
    Last edited: Jan 8, 2005
  7. Jan 8, 2005 #6
    Well, that's a lot better than my attempt! But I don't think you're done because there is still the possibility that there exist distinct values for m and n such that if you swap the values it comes out the same.
     
  8. Jan 8, 2005 #7

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It's trivial to show that the eqaulity holds on switching n,m only if n=m.
     
  9. Jan 8, 2005 #8
    Sure, but you do have to do it.
     
  10. Jan 8, 2005 #9

    Curious3141

    User Avatar
    Homework Helper

    No, I don't think there's a need for it. For one thing the case m = n = p = q is implicit in my proof. For another, the original identity is obviously asymmetrical in m and n, which will mean the LHS will change if you switch, and if you follow the rest of the proof through, those will come out to be the only distinct values that will give that particular LHS.
     
  11. Jan 9, 2005 #10
    I'm just saying there should be a mention of it; it shouldn't be ignored completely.
     
  12. Jan 9, 2005 #11

    Curious3141

    User Avatar
    Homework Helper

    I'm afraid I still don't see the point of singling out that one case in the proof. :confused: I don't know exactly what you're looking for, but let me make a stab at it.

    Let m = X and n = Y and let the function g(a,n) have a value of G in this case. Let the corresponding value of f(a) be F.

    Then G = F + Y

    Now let us say that the same value of g(a,n) is obtained by letting m = Y and n = X. Let the value of f(a) corresponding to this case be F'.

    Then G = F' + X

    Since f(a) is symmetric in m and n, F = F'. Which implies that X = Y.

    Was that what you were looking for ? Because such a situation is already clearly covered by my proof as I've demonstrated above.

    PS : Excuse the lack of LaTEX, I'm rushing. :smile:
     
  13. Jan 9, 2005 #12
    Oh, sorry, I didn't read it thoroughly enough. That was included in the original proof.
     
    Last edited: Jan 9, 2005
  14. Jan 9, 2005 #13

    Curious3141

    User Avatar
    Homework Helper

    No problem. I thought I had covered all the bases. :smile:
     
  15. Jan 9, 2005 #14

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    Seeing as it has been solved this is what I think is pobably the esiest way to see that n = p and m = q.

    If you make the subsitution [itex]a = m + n -1[/itex], given that m and n are strictly natural numbers you can re-write the LHS as:

    [tex]n + \sum^a_{i=1} i[/tex]

    Given that [itex] n \le a[/itex], it follows that:

    [tex]n + \sum^a_{i=1} i \le \sum^{a+1}_{i=1} i[/tex]

    Therefore the function (where the domain is NxN):

    [tex]g(n,a) = n + \sum^a_{i=1} i[/tex]

    is injective as is the function:

    [tex]f(n,m) = \frac{(n+m-1)^2 +n -m +1}{2}[/tex]

    as the function is injective f(n,m) = f(p,q) implies that n=p and m = q

    QED

    For a little background the function f is infact a bijection from NxN->N and it is is simply my go at defiing such a function a non-piecewise manner. The easiets way to see thta it is bijecive is to think of the usual proof (i.e. the proof thta invoves an infite array of numbers) that there is a bijection between N and NxN.
     
  16. Jan 9, 2005 #15

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Very pretty !

    This is just cosmetic (no pun...) but don't you mean :

    [tex]LHS = n + \sum^{a-1}_{i=1} i ~~ ?[/tex]

    From which it follows that:

    [tex]n + \sum^{a-1}_{i=1} i \le \sum^{a}_{i=1} i= \sum^{a-1}_{i=1} i + a[/tex]

    only if [itex] n \le a [/itex], which is true.
     
  17. Jan 9, 2005 #16

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    yes that's much better.

    That's the problem with proving things in my head rather than writing them down, I tend to make silly little mistakes.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Prove this!
  1. Prove existence. (Replies: 11)

  2. Prove Addition (Replies: 137)

  3. Prove perfection (Replies: 22)

  4. Prove existence (Replies: 80)

  5. Proving a negative (Replies: 31)

Loading...