# Proving upper bounds? [closed]

This is a relatively simple question. Say you are given a set that exists in the reals. How would you go about formulating a proof to prove that some number that is not given is in fact an upper bound?

-

## closed as too broad by ᴡᴏʀᴅs, Antonio Vargas, Tomás, Omnomnomnom, PVALAug 3 '14 at 16:36

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

By showing that none of th elements in the set is bigger than that number? Seriously, your question is not very concrete ... – Hagen von Eitzen Feb 12 '13 at 16:51
Obviously. The question asked was how you would formulate a proof. Best to use contradiction, PMI, it was a question asked about an opinion as there are many ways to go about this proof. Don't bother posting on questions if you're going to act like the world around you isn't as superior as yourself. – Math Student Feb 12 '13 at 17:10

One way to do it is this. By observation, one makes a guess what an upper bound would be. Then by using algebraic maipulations and properties, one proves that it indeed is an upper bound.

For example, consider the set $\{1-\frac1n:n=1,2,3,\ldots\}$. Visualising this set on the real line leads us to conjecture that $1$ is an upper bound. One then verifies that for any positive integer $n$, $1-\frac1n<1$ holds.

-

This is a very broad question and therefore the answer can hardly be anything but: "It depends" So here are a few examples that should illustrate that various ideas may be needed to show that a certain number is a bound.

Let $A=\{x\in \mathbb R\mid x^6<40+2x^3\}$. Show that $A$ is bounded.

Direct computation: Note that $x^6<40+2x^3$ implies $(x^3-1)^2=x^6-2x^3+1<41<7^2$, hence $|x^3-1|<7$, i.e. $x^3<8$ and finally $x<2$. Therefore $2$ is an upper bound for $A$.

Let $B=\{\frac {F_{n+1}}{F_{n}}\mid n\in\mathbb N\}$, where $F_n$ is the $n$th Fibonacchi number, i.e. $F_1=1, F_2=2$ and $F_n=F_{n-1}+F_{n-2}$ otherwise.

We have (by induction, if necessary) $F_n>0$ for $n\in\mathbb N$. Therefore $F_{n+1}=F_{n}+F_{n-1}>F_{n}$ for $n>1$ (but trivially also for $n=1$), i.e. the sequence is strictly increasing. Therefore $F_{n+1}=F_n+F_{n-1}<2F_n$ for $n>1$. Together with $F_2\le 2F_1$, which makes $2$ an upper bound for $B$.

Let $c\in \mathbb R$ and $C$ a bounded (from above) set with $0\in C$ and for all $x\in C$, also $x^2+c\in C$. Show that $2$ is an upper bound.

Assume $2$ is not an upper bound. Let $x_0$ be an element of $C$ that is $>2$ and define recursively $x_n=x_{n-1}^2+c$ so that $x_n\in C$. Note that $$\tag1x^2+c\ge x^2-x=x(x-1)>x\quad\text{if }x\ge-c\text{ and }x>2$$

• If $c\ge-2$, then the sequence $(x_n)$ is strictly increasing because of $(1)$.

• If $c<-2$, $0\in C$ implies $c\in C$ implies $c^2+c\in C$. As $c^2+c=(-c)\cdot(-1-c)>(-c)\cdot 1=-c>2$, we may assume that we have chosen $x_0=c^2+c$ above and again see from $(1)$ that $(x_n)$ is strictly increasing.

As $C$ is bounded, the strictly increasing sequence $(x_n)$ converges against some limit $\xi$ (not necessarily in $C$), for which $\xi^2+c=\xi$ holds. As already $x_0\ge -c$ and $x_0>2$, this hold even more so for $\xi$ and we get a contradiction to $(1)$. Therefore, $2$ is an upper bound for $C$.

Let $D=\{\sin(p)+3\cos(p^2)|p\text{ is a Fermat prime}\}$.

We need not know anything about Fermat primes to show that $4$ is an upper bound, simply because $\sin x\le 1$ and $\cos x\le 1$ for all $x$.

Let $E=\left\{\frac{1}{(x-u)^2+(y-v)^2}\;\bigg|\; x,y,u,v\in \mathbb R, xy=uv=1, xu<0\right\}$. Show that $\frac18$ is an upper bound for $E$

How would you proceed?

Let $F = \left\{n\in\mathbb N\;\bigg|\; \exists \frac ab\in\mathbb Q\setminus \mathbb Z\colon\left|\frac ab-\sqrt 5\right|<\frac1{q^n}\right\}$

Any idea if there is a bound? What the bound could be? How to prove it?

Let $G=\{n\in\mathbb N\mid$ There exists a binary twelve state Turing machine that halts after writing $n$ "1"s$\}$.

Finding and proving an upper bound is only for the brave.

-
In your second to last colored box, I think you want to change $k$ to $n$, (or vice versa). – Jason DeVito Feb 12 '13 at 19:07
@JasonDeVito Thanks. This happens if one changes the mind which statement about approximation to refer to in the middle of writing :) – Hagen von Eitzen Feb 12 '13 at 19:40
@HagenvonEitzen Wow!! – Jayesh Badwaik Feb 12 '13 at 20:15

How to structure a proof that there is an upper bound depends completely on what you already know about the set. There is no general procedure that will work no matter how the set is defined, or even most of the time.

So you're not giving enough information for a useful answer.

-