Un término común para $a_n=\begin{cases} 2a_{n-1} & \text{if } n\ \text{ is even, }\\ 2a_{n-1}+1 & \text{if } n\ \text{ is odd. } \end{cases}$

Question

Cuando estaba respondiendo a una pregunta aquí, me encontré con una secuencia como una recursiva uno tal como se indica a continuación.

$a_1=1$ y $n>1$,

$$ a_n =\begin{cases} 2a_{n-1} & \text{if } n\ \text{ is even, }\\ 2a_{n-1}+1 & \text{if } n\ \text{ is odd. } \end{casos} $$

Necesito encontrar un término común para esta secuencia. Por ejemplo, la secuencia $a_1=2$ y $a_n=2a_{n-1}$, $n>1$, el término común es $a_n=2^n$.

Agradezco de antemano cualquier respuesta o sugerencia.

Answer 1

Tenga en cuenta que en binario tenemos

$$\begin{align*} a_1&=1\\ a_2&=10\\ a_3&=101\\ a_4&=1010\\ a_5&=10101\;, \end{align*}$$

mostrar un patrón fácilmente demostrado por inducción a ser real. Ahora tenga en cuenta que el binario de expansión de $\frac23$$\frac23=0.\overline{10}_{\text{two}}$, por lo que

$$\begin{align*} 2\cdot\frac23&=1.\overline{01}_{\text{two}}\\ 2^2\cdot\frac23&=10.\overline{10}_{\text{two}}\\ 2^3\cdot\frac23&=101.\overline{01}_{\text{two}}\\ 2^4\cdot\frac23&=1010.\overline{10}_{\text{two}}\\ 2^5\cdot\frac23&=10101.\overline{01}_{\text{two}}\;, \end{align*}$$

y por lo tanto

$$a_n=\left\lfloor 2^n\cdot\frac23\right\rfloor=\left\lfloor\frac{2^{n+1}}3\right\rfloor\;.$$

Si usted realmente quiere deshacerse de la función del suelo, se observa que la $2^{n+1}\equiv 1\pmod3$ al $n$ es impar, y $2^{n+1}\equiv2\pmod3$ al $n$ es par, entonces

$$\left\lfloor\frac{2^{n+1}}3\right\rfloor=\begin{cases} \dfrac{2^{n+1}-1}3,&\text{if }n\text{ is odd}\\ \dfrac{2^{n+1}-2}3,&\text{if }n\text{ is even}\;. \end{casos}$$

Ahora

$$\frac12\big(1+(-1)^n\big)=\begin{cases} 0,&\text{if }n\text{ is odd}\\ 1,&\text{if }n\text{ is even}\;, \end{casos}$$

así

$$\begin{align*} \left\lfloor\frac{2^{n+1}}3\right\rfloor&=\frac13\left(2^{n+1}-1-\frac12\big(1+(-1)^n\big)\right)\\ &=\frac13\left(2^{n+1}-\frac12\left(3+(-1)^n\right)\right)\\ &=\frac16\left(2^{n+2}-3-(-1)^n\right)\;. \end{align*}$$

Answer 2

Esta respuesta se ocupa de cómo se puede resolver la recursividad mediante el estándar (libro de texto) método. Podemos escribir su recursividad en el formulario $$a_n - 2a_{n-1} = f(n)$$

donde $f(n) = 1$ al $n$ es impar y cero en caso contrario. En esta forma es fácil ver que la solución homogénea es $a_n^{\rm h} = c\cdot2^n$ como la ecuación característica es, simplemente,$\lambda-2 = 0$. Para encontrar una solución particular observe que podemos escribir $f(n)$

$$f(n) = \frac{1 - (-1)^n}{2}$$

lo que motiva el ansatz $a_n^{\rm p} = A + B(-1)^n$ (siempre trate de una prueba de solución en una forma similar como el lado derecho). La inserción de esta en la recursividad y resolviendo $A,B$ nos da la solución particular $a_n^{\rm p} = -\frac{1}{2} - \frac{(-1)^n}{6}$. Finalmente imponer $a_1=1$ determina la $c = \frac{2}{3}$ y nos da la solución final $a_n = a_n^{\rm h} + a_n^{\rm p} = \frac{2^{n+2} - (-1)^{n} - 3}{6}$.

Answer 3

A menudo puede ser útil escribir sólo los dos primeros términos: $$\begin{align} a_1 &= 1 \\ a_2 &= 2 \\ a_3 &= 5 = 2^2 + 1\\ a_4 &= 10 = 2^3 + 2 \\ a_5 &= 21 = 2^4 + 5 = 2^4 + 2^2 + 1\\ a_6 &= 42 = 2^5 + 10 = 2^5 + 2^3 + 2\\ a_7 &= 85 = 2^6 + 21 = 2^6 + 2^4 + 5 = 2^6 + 2^4 + 2^2 + 1\\ a_8 &= 170 = 2^7 + 42 = 2^7 + 2^5 + 10 = 2^7 + 42 = 2^7 + 2^5 + 2^3 + 2 \end {Alinee el} $$ ¿ves un patrón? Básicamente solo necesitas encontrar una expresión cambiando entre $1$y $2$.