Show that for each $x ∈ \mathbb{N}$, $x ≥ 2$, there exists a unique $t ∈ \mathbb{N}$ such that $1 + 2 + \dots + t < x ≤ 1 + 2 +\dots + t + (t + 1)$

Question

Show that for each $x ∈ \mathbb{N}$, $x ≥ 2$, there exists a unique $t ∈ \mathbb{N}$ such that $1 + 2 + \dots + t < x ≤ 1 + 2 +\dots + t + (t + 1)$

I was studying the applications of the Principle of Mathematical Induction and this question came up.

I took the base case for $x = 2$ and showed that it holds. Then, I assumed that it is true for some $x ∈ \mathbb{N}$ and added $1$ to both sides.

I get this:

$$\frac{t^2 + t + 2}{2} < x + 1 \le \frac{t^2 + 3t + 4}{2}$$

These expressions have imaginary roots so I can't possibly factorise them and try something along those lines.

So, I tried this: basically, took sum up to $(t+1)$ on the left and $(t+2) $on the right. This is what I get:

$$\frac{t^2 + 3t + 2}{2} < y \le \frac{t^2 + 5t + 6}{2}$$

I first thought of doing some comparisons but it doesn't seem possible. How do I prove it?

Even when it is proved using induction, how do we prove the uniqueness of $t$?

Answer 1

The inequalities to prove are the same as $$ \dfrac{t(t+1)}{2}<x\le\dfrac{(t+1)(t+2)}{2} $$ Take, for instance, $t=3$; then you get $$ 6<x\le 10 $$ Thus you see that the same $t$ is good for several values of $x$.

Let's tackle existence first. For $x=2$, we can take $t=1$, so the base case is OK.

Suppose we know the result for $x$ and a value of $t$. There are two cases: if $x+1\le (t+1)(t+2)/2$, we are done. Otherwise, we have $$ \frac{(t+1)(t+2)}{2}<x+1 $$ Noting that, for every $t$, $$ \dfrac{(t+1)(t+2)}{2}-\dfrac{t(t+1)}{2}=t+1 $$ we can also state that $$ x+1\le\dfrac{(t+2)(t+3)}{2} $$ and the proof of existence is finished.

Uniqueness is rather easy and you should be able to supply a proof.

Answer 2

Fix $x\geq 2$ and consider the set $S$ consisting of all $t\geq 1$ such that $1+2+\ldots+ t<x$. Note that $S$ is nonempty since it contains $1$. Also, any $t\in S$ is strictly less than $x$. So $S$ is a nonempty set of integers that is bounded above. It follows that $S$ contains a maximal element $t$. This is the $t$ you are looking for.

The uniqueness property is not hard to verify directly. Suppose you have distinct $s$ and $t$ such that $1+\ldots+ s<x\leq 1+\ldots +s+(s+1)$ and $1+\ldots+ t<x\leq 1+\ldots +t+(t+1)$. Without loss of generality, we can assume $s<t$. So $s+1\leq t$. Now compare the upper bound on $x$ from the first set of inequalities to the lower bound on $x$ from the second. Can you see the problem?