Proving n=p and m=q Given n,m,p,q

[jcsd]

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


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

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

Prove that n=p and m=q

 

[jcsd]

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

Is it too easy? Too difficult? Just boring?

 

[Gokul43201]

Too scary ! What background is needed to crack this (who is it accessible to) ?

 

[jcsd]

The maths is all fairly simple, you can solve it without expanding the brackets.

 

[Curious3141]

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

a = n + m - 1

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

Then the expression on the LHS reduces to :

\frac{1}{2}(a^2 -a) + n = n + \frac{1}{2}a(a-1)

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

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

g(a,n) = n + f(a)

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

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

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

Connecting up the chain of reasoning above,

One value of the LHS in the original identity implies one value of m and one value of n giving the required proof.

 

[Bartholomew]

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.

 

[Gokul43201]

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.

It's trivial to show that the eqaulity holds on switching n,m only if n=m.

 

[Bartholomew]

Sure, but you do have to do it.

 

[Curious3141]

Sure, but you do have to do it.

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.

 

[Bartholomew]

I'm just saying there should be a mention of it; it shouldn't be ignored completely.

 

[Curious3141]

I'm just saying there should be a mention of it; it shouldn't be ignored completely.

I'm afraid I still don't see the point of singling out that one case in the proof. 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.

 

[Bartholomew]

Oh, sorry, I didn't read it thoroughly enough. That was included in the original proof.

 

[Curious3141]

Oh, sorry, I didn't read it thoroughly enough. That was included in the original proof.

No problem. I thought I had covered all the bases.

 

[jcsd]

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 a = m + n -1, given that m and n are strictly natural numbers you can re-write the LHS as:

n + \sum^a_{i=1} i

Given that n \le a, it follows that:

n + \sum^a_{i=1} i \le \sum^{a+1}_{i=1} i

Therefore the function (where the domain is NxN):

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

is injective as is the function:

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

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.

 

[Gokul43201]

Very pretty !

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

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

From which it follows that:

n + \sum^{a-1}_{i=1} i \le \sum^{a}_{i=1} i= \sum^{a-1}_{i=1} i + a

only if n \le a, which is true.

 

[jcsd]

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.