Question

Let an be the nth term of the sequence

$1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,\dots$constructed by including the integer exactly times. Show that${\mathrm{a}}_{\mathrm{n}}=\left[\sqrt{2\mathrm{n}}+\frac{1}{2}\right.⌋$

Short answer

Ceiling function [x] : smallest integer that is greater than or equal to x.

Floor function [x] : largest integer that is less than or equal to x.

Step-by-step solution

Step 1:

Given:$a_n$ represents the term of the sequence constructed by including the integer k exactly k times.

To Proof:$a_n=⌊\sqrt{2n}+\frac{1}{2}⌋$

Let n be a positive integer.

$a_n=k=\left[\sqrt{2n}+\frac{1}{2}\right.⌋$will be true when $\mathrm{k}=⌊\sqrt{2\mathrm{n}}+\frac{1}{2}⌋$implies $\sum _{i=1}^{k-1} \mathrm{i}<\mathrm{n}\le \sum _{\mathrm{i}=1}^{\mathrm{k}}$and that there are terms that have image (namely, all terms $⌊\sqrt{2j}+\frac{1}{2}⌋$that have property

$\left.\sum _{i=1}^{k-1} i<j\le \sum _{i=1}^k \right)$

Step 2:

First part: $\sum _{i=1}^{k-1} \mathrm{i}<\mathrm{n}\le \sum _{\mathrm{i}=1}^{\mathrm{k}}$

$\mathrm{k}\le \sqrt{2\mathrm{n}}+\frac{1}{2}<\mathrm{k}+1$

Subtract $\frac{1}{2}$from each side:

$k-\frac{1}{2}\le \sqrt{2n}<k+\frac{1}{2}$

Square each side:

${\left(k-\frac{1}{2}\right)}^2\le 2n<{\left(k+\frac{1}{2}\right)}^2$

Step 3:

Use the property $(a+b{)}^2=a^2+2ab+b^2$

${\mathrm{k}}^2-\mathrm{k}+\frac{1}{4}\le 2\mathrm{n}<{\mathrm{k}}^2+\mathrm{k}+\frac{1}{4}$

Rewrite sums/differences as a single fraction:

$\frac{4{\mathrm{k}}^2-4\mathrm{k}+1}{4}\le 2\mathrm{n}<\frac{4{\mathrm{k}}^2+4\mathrm{k}+1}{4}$

Divide each side by :

$\frac{4{\mathrm{k}}^2-4\mathrm{k}+1}{8}\le \mathrm{n}<\frac{4{\mathrm{k}}^2+4\mathrm{k}+1}{8}$

Next, we note using $\sum _{i=1}^n i=\frac{n(n+1)}{2}$

$\begin{array}{r}n\ge \frac{4{\mathrm{k}}^2-4\mathrm{k}+1}{8}>\frac{4{\mathrm{k}}^2-4\mathrm{k}}{8}=\frac{{\mathrm{k}}^2-\mathrm{k}}{2}\\ =\frac{(\mathrm{k}-1)\mathrm{k}}{2}=\sum _{\mathrm{i}=1}^{\mathrm{n}} \mathrm{i}\end{array}$

Using that and are integers on$\mathrm{n}<\frac{4{\mathrm{k}}^2-4\mathrm{k}+1}{8}\text{and using}\sum _{\mathrm{i}=1}^{\mathrm{n}} \mathrm{i}=\frac{\mathrm{n}(\mathrm{n}+1)}{2}$

$\mathrm{n}\le \frac{4{\mathrm{k}}^2+4\mathrm{k}}{8}=\frac{{\mathrm{k}}^2+\mathrm{k}}{2}=\frac{(\mathrm{k}+1)\mathrm{k}}{2}=\sum _{\mathrm{i}=1}^{\mathrm{n}} \mathrm{i}$

Thus, we have the show$\underset{\mathrm{i}=1}{\overset{\mathrm{k}-1}{\mathrm{n}\sum }} \mathrm{i}<\mathrm{n}\le \sum _{\mathrm{i}=1}^{\mathrm{k}}$

Step 4:

Second part terms that have as image.

By the first part, we know that $\left|\sqrt{2n}+\frac{1}{2}\right|=k\text{when}\sum _{i=1}^{k-1} i<j\le \sum _{i=1}^k$

The number of integers that have as image are then:

$\sum _{i=1}^k i-\sum _{i=1}^{k-1} i=k+\sum _{i=1}^{k-1} i-\sum _{i=1}^{k-1} i=k$

Hence, we proved that$a_n=⌊\sqrt{2n}+\frac{1}{2}⌋$ by showing that and showing that$\sum _{\mathrm{i}=1}^{\mathrm{k}-1} \mathrm{i}<\mathrm{n}\le \sum _{\mathrm{i}=1}^{\mathrm{k}}$ there are k terms that have k as image.