# Prove this!

1. Jan 7, 2005

### 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

2. Jan 8, 2005

### jcsd

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

Is it too easy? Too difficult? Just boring?

3. Jan 8, 2005

### Gokul43201

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

4. Jan 8, 2005

### jcsd

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

5. Jan 8, 2005

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

Last edited: Jan 8, 2005
6. Jan 8, 2005

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

7. Jan 8, 2005

### Gokul43201

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

8. Jan 8, 2005

### Bartholomew

Sure, but you do have to do it.

9. Jan 8, 2005

### Curious3141

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.

10. Jan 9, 2005

### Bartholomew

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

11. Jan 9, 2005

### Curious3141

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.

12. Jan 9, 2005

### Bartholomew

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

Last edited: Jan 9, 2005
13. Jan 9, 2005

### Curious3141

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

14. Jan 9, 2005

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

15. Jan 9, 2005

### Gokul43201

Staff Emeritus
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.

16. Jan 9, 2005

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