Is this proof rigorous enough? - Math Proof Critique

[PFStudent]

Is this proof rigorous enough?

Homework Statement

This problem is from my College Problem Solving Seminar Course.

Book: The Art and Craft of Problem Solving, 2nd Edition by Paul Zeitz.

Ex. 1.2.1

Prove that the product of four consecutive natural numbers cannot be the square of an integer.

Homework Equations

Number Theory

The Attempt at a Solution

What I need help with is just critique of my proof. I want to make sure it is very rigorous (and ofcourse correct).

Attempt at a Solution:

Let,

<br /> {n \in \mathbb{N}}<br />

<br /> {\mathbb{N} = \{1, 2, 3, . . . ,\infty\}<br />

<br /> {m \in \mathbb{Z}}<br />

<br /> {\mathbb{Z} = \{ - \infty, . . . , - 1, 0, 1, . . . , \infty\}<br />

Prove that:

<br /> {n(n + 1)(n + 2)(n + 3)} \neq {{m}^{2}}<br />

(Proof by Contradiction)

Assume the Contrary:

<br /> {n(n + 1)(n + 2)(n + 3)} = {{m}^{2}}<br />

<br /> {{n}^{4} + 6{n}^{3} + 11{n}^{2} + 6{n}} = {{m}^{2}}<br />

Let,

<br /> f(n) = {{n}^{4} + 6{n}^{3} + 11{n}^{2} + 6{n}}<br />

Then, since f(n) is a fourth degree polynomial. Then for,

<br /> {{n}^{4} + 6{n}^{3} + 11{n}^{2} + 6{n}} = {{m}^{2}}<br />

there must exist some g(n) such that,

<br /> {f(n)} = {[g(n)]}^{2}<br />

If g(n) exists, then it must be a second degree polynomial--since f(n) is a fourth degree polynomial--fitting one of the following forms:

<br /> {(1) g(n) = a{n}^{2}}<br />

<br /> {(2) g(n) = a{n}^{2}} + c<br />

<br /> {(3) g(n) = a{n}^{2}} + b{n}<br />

<br /> {(4) g(n) = a{n}^{2}} + b{n} + c<br />

Consider case (1), this is not possible for g(n) since f(n) would lack a term of degree three.

Consider case (2), this is not possible for g(n) since f(n) would also lack a term of degree three.

Consider case (3), this is not possible for g(n) since f(n) would lack a term of degree one.

Consider case (4), this is the only possibility for g(n) since f(n) would contain terms of degrees: four, three, two, and one.

However, in order for,

<br /> g(n) = a{n}^{2}} + b{n} + c<br />

It must satisfy,

<br /> f(n) = {(a{n}^{2}} + b{n} + c)}^{2}<br />

Which when expanded is,

<br /> f(n) = {{a^2}{n}^{4} + {2ab}{n}^{3} + {(2ac + b^2)}{n}^{2} + {2bc}{n} + {c^2}}<br />

Where,

<br /> f(n) = {{n}^{4} + 6{n}^{3} + 11{n}^{2} + 6{n} + 0}<br />

Must match as follows,

<br /> a^2 = 1<br />

<br /> 2ab = 6<br />

<br /> 2ac + b^2 = 11<br />

<br /> 2bc = 6<br />

<br /> c^2 = 0<br />

However if,

<br /> c^2 = 0<br />

Then,

<br /> 2bc \neq 6<br />

Contradiction.

However, here is my question...

Is there anything I missed in this proof? Anything I should have done more rigorously?

Anything I left unaddressed?

Thanks,

-PFStudent

 

[StatusX]

there must exist some g(n) such that,

<br /> {f(n)} = {[g(n)]}^{2}<br />

If g(n) exists, then it must be a second degree polynomial--since f(n) is a fourth degree polynomial--fitting one of the following forms:

This does not follow. All you are assuming is that f(n) is the square of an integer for some n, not for all n. And even if g(n) was an integer for all n, it would take some more work to show it's a second degree polynomial (for example, \sqrt{x^4-1} squares to a fourth degree polynomial, but is not itself a second degree polynomial.)

 

[PFStudent]

Hey,

This does not follow. All you are assuming is that f(n) is the square of an integer for some n, not for all n. And even if g(n) was an integer for all n, it would take some more work to show it's a second degree polynomial (for example, \sqrt{x^4-1} squares to a fourth degree polynomial, but is not itself a second degree polynomial.)

Thanks for the reply.

Your point of showing that, f(n) does not neccesarily equal [g(n)]^{2} is interesting. This would imply that (in order to complete the proof) that there must exist some other way of showing that,

<br /> f(n) \neq m^2 <br />

Without assuming g(n) can only be a degree two polynomial and proving by contradiction that,

<br /> f(n) \neq [g(n)]^2<br />

If I understand what you said correctly, your saying that basically,

<br /> \sqrt{n^4-1}<br />

Is indeed not a polynomial of degree two, but when squared is a polynomial of degree four (contradicting my proof where I stated that g(n) must be a polynomial of degree two)--where additionally, this polynomial when factored is,

<br /> (n^2-1)(n^2+1)<br />

Where cleary we see that,

<br /> (n^2-1)(n^2+1) \neq m^2<br />

This is interesting,...as my proof is true for some n, but as you pointed out not rigorous and comprehensive for all n...hmm.

OK, well my question is how would I prove this for all n then?

More specifically which approach do I take now?

Thanks,

-APSStudent

 

[Vid]

Take different values for n and plug them into the polynomial and see what you get. It should be obvious from there where to go.

 

[PFStudent]

This does not follow. All you are assuming is that f(n) is the square of an integer for some n, not for all n. And even if g(n) was an integer for all n, it would take some more work to show it's a second degree polynomial (for example, \sqrt{x^4-1} squares to a fourth degree polynomial, but is not itself a second degree polynomial.)

Hmm, I was thinking over again what you said for a while.

However, I realized that I disagree.

Consider your example,

I begin with,

<br /> {n(n + 1)(n + 2)(n + 3)} \neq {{m}^{2}}<br />

(Proof by Contradiction)

Assume the Contrary:

<br /> {n(n + 1)(n + 2)(n + 3)} = {{m}^{2}}<br />

<br /> {{n}^{4} + 6{n}^{3} + 11{n}^{2} + 6{n}} = {{m}^{2}}<br />

Let,

<br /> {{n}^{4} + 6{n}^{3} + 11{n}^{2} + 6{n}} = {{[g(n)]}^{2}}<br />

However you introduce the possibility of,

<br /> g(n) = \sqrt{h(n)}<br />

Where, {h(n)} could be something like,

<br /> {{n}^{4}-1}<br />

Which would make,

<br /> g(n) = {\sqrt{{n}^{4}-1}}<br />

Since,

<br /> {f(n)} = {[g(n)]}^{2}<br />

Where,

<br /> {[g(n)]}^{2} = {[(\sqrt{h(n)})]}^{2}<br />

Following that,

<br /> f(n) = h(n)<br />

Which cleary does not since,

<br /> {{n}^{4} + 6{n}^{3} + 11{n}^{2} + 6{n}} \neq {{n}^{4} - 1}<br />

Now, to be rigorous let me consider your point on a more general level,

Let there exist some j(n) such that,

<br /> j(n) = \sqrt{{a}{n}^{4} + {b}{n}^{3} + {c}{n}^{2} + {d}{n} + {e}}}<br />

Does there exist some {j(n)} such that,

<br /> g(n) = \sqrt{j(n)}<br />

Where,

<br /> f(n) = {[g(n)]}^{2}<br />

Yes. Since,

<br /> f(n) = {[(\sqrt{j(n)})]}^{2}<br />

<br /> f(n) = j(n)<br />

Where,

<br /> f(n) = {{n}^{4} + 6{n}^{3} + 11{n}^{2} + 6{n}}<br />

In other words,

<br /> j(n) = {{n}^{4} + 6{n}^{3} + 11{n}^{2} + 6{n}} = f(n)<br />

So, there is no fourth degree polynomial under the square root that when squared gives back f(n) other than f(n). The reason being is that f(n) has already been defined as follows,

<br /> {f(n)} = {{n}^{4} + 6{n}^{3} + 11{n}^{2} + 6{n}}<br />

However, I would agree that for some unknown f(n) in the following equation,

<br /> {f(n)} = {m^2}<br />

Let,

<br /> {f(n)} = {[g(n)]}^{2}<br />

It does not follow (as you have pointed out) that g(n) must be a polynomial of degree two. However, in this case (my original proof) it must be since, {f(n)} is known and is,

<br /> {f(n)} = {{n}^{4} + 6{n}^{3} + 11{n}^{2} + 6{n}}<br />

================================================================================================

Take different values for n and plug them into the polynomial and see what you get. It should be obvious from there where to go.

Thanks for the tip. While I do already realize that,

<br /> {{f(n)} \neq {{m}^{2}}}<br />

And instead always equals,

<br /> {{f(n)} = {{m}^{2}} - 1}<br />

I did not like starting the proof from this statement. Since in order to have reached the above conjecture one would have had to create a table showing that for several terms of {n} the yield is always some perfect square minice one. Which I thought was not the most rigorous approach to take, since you had to have assumed it was true for all natural numbers, n.

Thanks,

-PFStudent

 

[Dick]

No, StatusX is right. If you could factor the polynomial, then you've proved it's a square for ALL n. Definitely not true. And you are right on that, you can't factor the polynomial. But that doesn't prove that it isn't a square for any n. If it makes you feel better, I don't see the solution clearly either. I've been trying to prove that N(n)=n*(n+1)*(n+2)*(n+3) has a prime factorization (p1^k1)*(p2^k2)*...*(pk^kj) where the pi's are different and such that anyone of the ki's is odd. That would do it. I haven't come up with anything that makes me happy yet.

 

[StatusX]

Here's my point. You're trying to argue that there is no n such that f(n), as you've defined it, is a perfect square. You attempt to do this by assuming that f(n) is a perfect square for all n (specifically, of the form g(n)^2 where g(n) is some polynomial with integer coefficients) and deriving a contradiction. But the only thing you can conclude from this contradiction is that you're assumption "f(n) is a perfect square for all n" is false, ie, you can conclude that "there is at least one n such that f(n) is not a perfect square." You cannot, however, conclude that "there is no n such that f(n) is a perfect square".

 

[PFStudent]

Hey,

Thanks for the replies: Dick and StatusX.

No, StatusX is right. If you could factor the polynomial, then you've proved it's a square for ALL n. Definitely not true. And you are right on that, you can't factor the polynomial. But that doesn't prove that it isn't a square for any n. If it makes you feel better, I don't see the solution clearly either. I've been trying to prove that N(n)=n*(n+1)*(n+2)*(n+3) has a prime factorization (p1^k1)*(p2^k2)*...*(pk^kj) where the pi's are different and such that anyone of the ki's is odd. That would do it. I haven't come up with anything that makes me happy yet.

So, because I cannot factor the polynomial that does not prove that it isn't a square for any n?

I do not quite understand how that is true. I mean how could f(n) be a perfect square for a particular n without f(n) factoring into {{[g(n)]}^{2}}?

Here's my point. You're trying to argue that there is no n such that f(n), as you've defined it, is a perfect square. You attempt to do this by assuming that f(n) is a perfect square for all n (specifically, of the form g(n)^2 where g(n) is some polynomial with integer coefficients) and deriving a contradiction. But the only thing you can conclude from this contradiction is that you're assumption "f(n) is a perfect square for all n" is false, ie, you can conclude that "there is at least one n such that f(n) is not a perfect square." You cannot, however, conclude that "there is no n such that f(n) is a perfect square".

Yea, that is my question right there. Why is that I cannot conclude that there is no {n} such that f(n) is a perfect square since I have already proved f(n) cannot be factored into {[g(n)]}^{2}?

I guess I do not quite understand why I cannot conclude that "there is no n such that f(n) is a perfect square," if I have already shown f(n) cannot be factored into {[g(n)]}^{2}?

Thanks,

-PFStudent

 

[StatusX]

For example, n^2+9 is a perfect square for n=-4,0,4, but cannot be factored as the square of a polynomial.

 

[Dick]

Beep. Vid's got it. n(n+1)(n+2)(n+3)+1 CAN be factored into a perfect square for all n. Just try it. Nice job, Vid! That's going to make it hard for n(n+1)(n+2)(n+3) to also be a perfect square.

 

[PFStudent]

Hey,

Ok, I was thinking about this problem for a while.

So, I think my problem arose when I let f(n) be the square of some g(n). I think by assuming this was true--that was incorrect. Additionally, is it customary when someone in a proof takes a particular polynomial (of variable n) and sets it equal to a function, f(n)--then by doing this are they generalizing that f(n) could be any function of n and not just that particular polynomial?

Thanks,

-PFStudent

 

[Dick]

Hey,

Ok, I was thinking about this problem for a while.

So, I think my problem arose when I let f(n) be the square of some g(n). I think by assuming this was true--that was incorrect. Additionally, is it customary when someone in a proof takes a particular polynomial (of variable n) and sets it equal to a function, f(n)--then by doing this are they generalizing that f(n) could be any function of n and not just that particular polynomial?

Thanks,

-PFStudent

Exactly. sqrt(n^2+9) is not a polynomial. sqrt(n*(n+1)*(n+2)*(n+3)+1) is.

 

[morphism]

This is late, but we can use the following trick: (n-1)n(n+1)(n+2) = (n^2 + n - 2)(n^2 + n) = (n^2 + n - 1)^2 - 1.

 

[PFStudent]

Hey,

Exactly. sqrt(n^2+9) is not a polynomial. sqrt(n*(n+1)*(n+2)*(n+3)+1) is.

I just wanted to make sure I was clear on this. So, if I let a particular polynomial or any expression for that matter (say of one variable, n) be equal to say f(n) then by doing this am I implying the following:

That when writing a (rigorous) Proof, if we let a particular expression/polynomial be equal to f(n)--then in the proof any statements I make with reference to f(n) must be true for not only that particular expression/polynomial but must be true for all f(n). That is, when writing the proof any statements made about f(n) must be true for all: n and f(n).

Is that right?

Thanks,

-PFStudent

 

[Dick]

You are making that sound kind of mysterious. Just think about StatusX's example. If you want to prove n^2+9 is never a square, then just because you can't factor the polynomial into a perfect square doesn't prove that n^2+9 is never a square. Because it can be.

 

[PFStudent]

Hey,

You are making that sound kind of mysterious. Just think about StatusX's example. If you want to prove n^2+9 is never a square, then just because you can't factor the polynomial into a perfect square doesn't prove that n^2+9 is never a square. Because it can be.

Thanks for the reply Dick.

I agree, although I just want to make sure I understand this with respect to writing the proof. So, for example the only reason we could consider the example of,

<br /> {{f(n)} = {{n}^{2} + 9}}<br />

is because we wanted to show that,

<br /> {f(n) \neq {[g(n)]}^{2}}<br />

for all n.

In other words, the only reason we could introduce {{n}^{2} + 9}<br /> as an example to prove the above is because we had to show that any statement with reference to f(n) must be true for all: n and f(n); when writing a (rigorous) proof. Is that right?

Or otherwise if we could not then I could not consider: what if I let a particular function equal say {{n}^{2} + 9}<br />, if I have already let f(n) equal some specific polynomial/expression.

Thanks,

-PFStudent

 

[Dick]

The statement
<br /> {f(n) \neq {[g(n)]}^{2}}<br />
for any polynomial g(n) is perfectly true. And that conclusion doesn't have much to do with 'for all n' or not. That just doesn't prove that f(n) is never a square for any particular n. Sorry, I'm having trouble following the general lesson you are trying to describe.

 

[PFStudent]

The statement
<br /> {f(n) \neq {[g(n)]}^{2}}<br />
for any polynomial g(n) is perfectly true. And that conclusion doesn't have much to do with 'for all n' or not. That just doesn't prove that f(n) is never a square for any particular n. Sorry, I'm having trouble following the general lesson you are trying to describe.

Thanks for the quick reply. Now I understand why my proof was flawed so my question is really about convention in proof writing, so hopefully my question(s) is a little more clear.

I guess I was sort of surprised that in order for my original proof to be true,

<br /> {{f(n)} = {[g(n)]}^{2}}<br />

Now, I perfectly understand why the above is not true for all: n; since there does exist some: f(n), and g(n); that makes the above untrue. However, I thought that since I specifically wrote in my original proof: f(n) was equal (and I thought only equal) to {{n}^{4} + 6{n}^{3} + 11{n}^{2} + 6{n}}; that one could not consider other possible f(n)s (such as {{n}^{2} + {9}}).

In other words, I did not realize the difference between, for example the following statements:

<br /> {{{n}^{2}} + {2{n}} + {1}} = {{(n+1)}^{2}}<br />

and

<br /> {{f(n)} = {[g(n)]}^{2}}<br />

Where I let,

<br /> {f(n)} = {{{n}^{2}} + {2{n}} + {1}}<br />

For the first one it is clear that equation is true.

However, for the second one I know it is not true and (I believe) the reason it is not true is because although {{{n}^{2}} + {2{n}} + {1}} can be factored into {(n + 1)}^{2}, this does not neccesarily hold for all n since g(n) can be any function (such as {{n}^{2} + 9}). Is that right?

Now here is where my confusion comes in, how is that we can consider the possibility of,

<br /> {{f(n)} = {{{n}^{2} + 9}}}<br />

when I have stated,

<br /> {{f(n)} = {{{n}^{2}} + {2{n}} + {1}}}<br />

I guess that is where I am confused. Since, I thought that if I let a specific expression/polynomial equal a function, then whenever I refer to that function in a proof--I only refer to that expression/polynomial. However, it seems (perhaps I may be mistaken) that once I let a specific expression/polynomial be equal to some function in a rigorous proof--all statements in that proof must be true not only for that specific expression/polynomial but for all functions.

Following up on all the above, is this how rigorous proofs are written, that is if I let a specific polynomial/expression equal some function then all statements I make in my proof must not only be true for that specific function, but true for all functions?

Thanks,

-PFStudent