Bounding

In one sentence

n^{2} < n^{2} + n + 1 < (n + 1)^{2} (n \geq 1)

Some quantities are hard to work out exactly, but you can squeeze them between two quantities that are easy to compute. With real numbers, squeezing only tells you “roughly”; with integers, a tight enough squeeze tells you “exactly”. There is no square between two consecutive squares, and between $2$ and $4$ there is only $3$ .

Example: n is a positive integer. Can n² + n + 1 be a perfect square?

Step 1 / 6

Try one
$n = 3$ : $n^{2} + n + 1 = 13$ , which lies between $9$ and $16$ .

$9 < 13 < 16$
Try another
Why the left side holds
Why the right side holds
Conclusion
Do not forget n = 0

Predict first

Positive integers $x \leq y \leq z$ satisfy $\frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 1$ . What is the largest possible value of $x$ ?

Choose an answer first; then you can see the result.

Stop 1 · Integer solutions of equations (Vol. 2)

Example: find all positive integers x ≤ y ≤ z with 1/x + 1/y + 1/z = 1

Step 1 / 6

x cannot be too big
Try $x = 4$ : none of the three fractions is more than $\frac{1}{4}$ , so together they are at most $\frac{3}{4}$ , which never reaches $1$ . So $x \leq 3$ .

$1 \leq \frac{3}{x} \Rightarrow x \leq 3$
x = 2
x = 2, y = 3
x = 2, y = 4
x = 3
All of them

Stop 2 · Maxima and minima of quadratic functions (Vol. 3)

After completing the square, throwing away a non-negative square is the simplest kind of bounding: $- (x - 2)^{2} \leq 0$ .

Example: two positive numbers add up to 4. What is the largest their product can be?

Step 1 / 4

Use one letter
Let one number be $x$ ; the other is $4 - x$ ( $0 < x < 4$ ). The product is $x (4 - x)$ .

$P = x (4 - x) = - x^{2} + 4 x$
Complete the square
Throw the square away
Can equality happen?

Stop 3 · Diophantine equations (Vol. 6)

When the squeezed range does contain squares, bounding turns the equation into a few linear equations.

Example: find positive integers x, y with y² = x² + x + 7

Step 1 / 5

Lower bound
$x^{2} + x + 7$ is clearly bigger than $x^{2}$ .

$x^{2} < x^{2} + x + 7$
Upper bound
Only two squares in between
y = x + 1
y = x + 2

Stop 4 · Extremal problems in combinatorics (Vol. 7)

“What is the most you can place?” is also answered by squeezing: an argument presses down from above (it cannot be more than this), and a construction pushes up from below (this many really can be done). Where the two meet is the answer.

Example: place pieces on a 5×5 board so that no two are in cells sharing a side. What is the most you can place?

Step 1 / 4

Try it yourself
Tap cells to place pieces; two neighboring cells (sharing a side) cannot both have one. How many can you place?
Upper bound: cut the board into pieces
Lower bound: really place 13
The two sides meet

Practice

Exercise 1Basic

Positive integers $x \leq y$ satisfy $\frac{1}{x} + \frac{1}{y} = \frac{1}{2}$ . How many such pairs $(x, y)$ are there?

Exercise 2Advanced

$n$ is a positive integer and $n^{2} + 3 n + 5$ is a perfect square. Find $n$ .

Exercise 3Challenge

Positive integers $x \leq y \leq z$ satisfy $x + y + z = x y z$ . Find $z$ .

Mistake Museum · Exhibits from this stop

Before you leave, look at the traps other people fell into here.See every exhibit in the museum →

Exhibit

Bounding too generously

To prove

\frac{1}{2 ^{2}} + \frac{1}{3 ^{2}} + \dots + \frac{1}{n ^{2}} < \frac{3}{4}

: since

\frac{1}{k ^{2}} < \frac{1}{( k - 1 ) k} = \frac{1}{k - 1} - \frac{1}{k}

, the left side is

< 1 - \frac{1}{n} < 1

. Done.

What went wrong? Think first, then open

Diagnosis What you proved is “less than $1$ ”, but the problem asks for “less than $\frac{3}{4}$ ”. $1$ is bigger than $\frac{3}{4}$ , so this bound is too loose and proves nothing. The trouble is the first term: enlarging $\frac{1}{4}$ to $\frac{1}{2}$ throws away $\frac{1}{4}$ in one go.

Keep the first term as it is and start bounding from the second: the left side is

< \frac{1}{4} + (\frac{1}{2} - \frac{1}{n}) < \frac{3}{4}

“If a bound is too loose, bound fewer terms”

Exhibit

Forgetting the small cases the bounds do not cover

Since

n^{2} < n^{2} + n + 1 < (n + 1)^{2}

n^{2} + n + 1

is not a perfect square for any non-negative integer

n

What went wrong? Think first, then open

Diagnosis The right-hand inequality is equivalent to $n > 0$ . When $n = 0$ , $n^{2} + n + 1 = 1 = (n + 1)^{2}$ , so it is not squeezed at all, and $1$ is in fact a perfect square.

For

n \geq 1

it lies strictly between two consecutive squares, so it is not a square; check

n = 0

separately: it gives

1 = 1^{2}

“Use an inequality only from where it starts to hold”

In one sentence

Stop 1 · Integer solutions of equations (Vol. 2)

Stop 2 · Maxima and minima of quadratic functions (Vol. 3)

Stop 3 · Diophantine equations (Vol. 6)

Stop 4 · Extremal problems in combinatorics (Vol. 7)

Practice

Mistake Museum · Exhibits from this stop

Stops on this line