Encontrar el elemento nth de una secuencia

Question

Supongamos que tenemos la secuencia dada por

$$ (1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,...) $$

Necesito demostrar que $a_n = \lfloor{ \sqrt{2n} + \frac{1}{2} \rfloor} $.

Probar:

Me doy cuenta de la siguiente. La última aparición de la 1 se produce en $a_1$, la última aparición de $2$ se produce en $a_3$, la última aparición de $3$ se produce en $a_6$. Por lo tanto, si definimos $F(n)$ a ser la última aparición de dos dígitos $n$, entonces supongo que

$$ P(n) = \frac{n(n+1)}{2} $$

Que demostrar por inducción. el caso base es clara. Supongamos que la fórmula es verdadera para algunos $k$, que se supone $P(k) = \frac{ k(k+1) }{2}$.

Nota: $P(k+1) = P(k) + k+1$

desde la (k+1)th última entrada es k+1 posiciones después de la kth entrada. Por lo tanto,

$$ P(k+1) = \frac{k(k+1)}{2} + k+1 = \frac{(k+1)(k+2)}{2} $$

y supongo que es cierto por inducción.

Ahora, vamos a $a_n = m$. Desde $a_n$ debe estar entre $P(m-1)$ $P(m)$ hemos

$$ P(m-1) < n \leq P(m) \implies \frac{ (m-1)m}{2} < n \leq \frac{m(m+1)}{2} \implies m^2 - m < 2n \leq m^2 + m $$

ahora, desde la $m^2 + m + 1/4 > m^2 + m$ y ya que la adición de $1/4$ $m^2-m$aún sería menos de $2n$, luego

$$ m^2 - m + \frac{1}{4} < 2n < m^2 +m + \frac{1}{4} \iff (m-1/2)^2 <2n < (m+1/2)^2 $$

Por lo tanto,

$$ m - 1/2 < \sqrt{2n} < m + 1/2 \implies m < \sqrt{2n} < m + 1$$

Por lo tanto, $m = a_n = \lfloor{ \sqrt{2n} + \frac{1}{2} \rfloor}$.

Es este un argumento correcto? Cualquier comentario sería muy apreciada. Hay un método mejor para solucionar este problema?

Answer 1

En su secuencia, la primera aparición de$m\in\{1,2,\ldots\}$ aparece en la posición$1+2+\ldots+(m-1)+1 = \frac{m^2-m}{2}+1$ y la última en la posición$1+2+\ldots+m=\frac{m^2+m}{2}$. Para probar el reclamo, es suficiente demostrar que la función$f:x\mapsto\left\lfloor\sqrt{2x}+\frac{1}{2}\right\rfloor$ asigna cada elemento del intervalo$\left[\frac{m^2-m}{2}+1,\frac{m^2+m}{2}\right]$ a$m$.
Dado que$f$ es una función que aumenta débilmente, es suficiente para mostrar que ambos puntos finales del intervalo anterior se asignan a$m$. Tenemos

$$\left(m-\frac{1}{2}\right)^2 = m^2-m+\frac{1}{4} < m^2-m+2 < m^2+m+2 \leq (m+1)^2 $ $ y la reclamación sigue fácilmente.