Can someone check if my proof is sufficient enough?

Question

I've just started my undergraduate mathematics degree, and I have to say, proving things isn't very intuitive. I used to be very good at proofs in high school, but only when it comes to algebraic and logical reasoning of the informal kind; now I just feel it's not sufficient enough. Anyway, I hope to get back on track and see if I've got the hang of things, hopefully with your help. I appreciate anyone's consideration. :)

1) Prove that the sequence $S(n) = (n^2)[(-1)^n]$ is unbounded for all natural numbers.

Answer: Consider $n=2k$ for all k in natural numbers, $\implies S(n)=n^2$

Suppose there exists M in natural numbers such that $S(n)<M$ for all n in natural numbers $\implies n^2<M$, therefore, $n<\sqrt{M}$. Consider the value $n(0)=(\mbox{ceilingfunction}:\sqrt{M}) + 1 > M$, which is in the natural numbers. This would imply that there exists a value in $S(n)$ which will always be greater than $M$. Therefore $S(n)$ is unbounded.

Consider $n=2k+1$ for all $k$ in natural numbers, $\implies S(n)=-(n^2)$

Suppose there exists $M$ in natural numbers such that $S(n)>M$ for all $n$ in natural numbers $\implies -n^2>M \implies n^2<M$, therefore $n<\sqrt{M}$. It has been shown above that in this situation, there exists no such value of $n$ such that $M>S(n)$ for all values $n,M$ in natural numbers.

END PROOF

Would it suffice to say that, since the set containing all natural numbers is unbounded then n^2 is unbounded, or are these steps necessary? And most importantly, am I doing it right? What are the things that I have to consider when conducting a proof? Any advice?

Thanks!

Answer 1

"What are the things that I have to consider when conducting a proof? Any advice?" is awfully open-ended. Pretty much the definition of rigour, though, is that the proof must establish the truth of the theorem given the truth of certain other statements (ie. axioms or other theorems derived from them). In other words, you need to be clear what truths you are starting with and exactly how your proof gets you from those truths to your destination.

Personally, I find questions like this one a little annoying. They tend to be posed as kind of "warm up" questions, as if they are particularly easy, since what you are being asked to prove is "obviously" true. However, to construct a real proof of such a statement would require that you start from something even more "basic", and in this case that presumably means some choice of a set of axioms for the natural numbers. However, the chances are that you haven't been introduced to, for example, the Peano Axioms. If you haven't, then it beats me what kind of "proof" you are expected to produce.

Anyway, rather than laboriously prove this from the Peano axioms or, say, the axioms of the real numbers, here's a proof based on the following statement (which is hardly more self-evident than the theorem itself):

If $N$ and $M$ are both natural numbers, $N \gt 1$ and $M \gt 0$ then $NM \gt M$.

We also need to know what $(-1)^n$ means, so negative numbers are involved. However, the theorem can be proved without reference to the negative terms so I'm going to ignore that except to assume that:

$(-1)^{2N} = 1$, for any natural number $N$.

Strictly speaking, you also need some other stuff about arithmetic operations and ordering on the natural numbers, but I've already almost lost the will to live.

Given this, you could prove that $S_n$ is unbounded using something like:

Take any natural number $N > 1$ and consider $S_{2N}$:

$S_{2N} = (2N)^2(-1)^{2N} = (2N)^2 = 4 \times N \times N \gt N \times N \gt N$.

So there is no natural number $N$ such $S_n \le N$ for all n, i.e. {S_n} is unbounded.

The problem with the question is that it's so simple that in your search to find something even more basic to prove it from you punch straight through the notion of "basic" itself and find yourself rummaging around in some vaguely foundations-of-maths stuff: Peano arithmetic and set theory. It's not that what's needed is necessarily difficult, it's just that a real, honest-to-goodness proof of something like this is a more tedious business than you might think. Perhaps realising that is the point of the question! :-)

I wouldn't worry about it, if I were you. I just tend to shrug at questions like this and move on to something more interesting. You'll get a better sense of what a proof entails from something a bit more meaty.

There's a lovely and relevant quote from Bertrand Russell's Principia Mathematica:

"From this proposition it will follow, when arithmetical addition has been defined, that 1+1=2." —Volume I, 1st edition, page 379 (page 362 in 2nd edition; page 360 in abridged version). (The proof is actually completed in Volume II, 1st edition, page 86, accompanied by the comment, "The above proposition is occasionally useful.") (wikipedia)

When you dig away at the "obvious" you find the rabbit hole goes very deep indeed. Infinitely deep, I guess...

Answer 2

The case $n=2k$ is almost correct but the case $n=2k+1$ not (of course the case $n=2k+1$ is unnecessary since from the case $n=2k$ you deduced that $S_n$ is unbounded).
In case $n=2k+1$ you want to assume that $S_n$ is bounded i.e. for some $M>0, \ |S_n|<M \Rightarrow n^2<M \ldots$
Instead you assumed that $S_n>M$.

Here is your proof corrected:

Assume that $S_n$ is bounded. Then exist an $M>0$ such that $|S_n|<M$ for all $n \in \mathbb{N}$. This mean that in the particular case $n=2k, \ |S_{2k}|=(2k)^2<M \Rightarrow k<\dfrac{\sqrt{M}}{2}, \ \forall k \in \mathbb{N}$. But for $k=\lceil \dfrac{\sqrt{M}}{2}\rceil +1 \in \mathbb{N}$ this is not true. Thus $S_n$ cannot be bounded. (Or as Hendrik Jan suggested there is no need to separate even or odd cases and instead of $k=\lceil \dfrac{\sqrt{M}}{2}\rceil +1 $ you can simply take $n=M$)