Deje $n$ ser un entero positivo arbitrario, y $p(n)$ el número de $n$-números de dos dígitos que consiste sólo de los dígitos $1,2,3,4,5$, y en el que cada dos prójimo dígitos se diferencian por $2$ o más.
Mi tarea es demostrar que esta desigualdad se cumple para cualquier número entero positivo $n$:
$$\ 5 \cdot (2,4)^{n-1} ≤ p(n) ≤ 5 \cdot (2,5)^{n-1} $$
Alguna idea?
Podemos expresar exactamente el recuento $p(n)$ de %de $n$- dígitos de la $\{1,2,3,4,5\}$ donde los dedos adyacentes no difieren en menos de dos, como WimC describe anteriormente. Si $p_k(n)$ indica el recuento de dichos números con el primer dígito $k$, entonces para $n \ge 1$:
$$p(n) = p_1(n) + p_2(n) + p_3(n) + p_4(n) + p_5(n)$$
Además desde un $n+1$ número de dígitos de la clase consiste en un $n$ dígitos de dicho número compatible con un nuevo primer dígito (que se diferencia por al menos dos de los anteriores dígitos), tenemos por inducción de la expresión de la matriz:
$$p(n) = u A^{n-1} u'$$
donde la fila $u = \begin{pmatrix} 1&1&1&1&1 \end{pmatrix}$, e $A$ es WimC s $5\times5$ matriz de Toeplitz. Por ejemplo, $p(1) = 5$, $p(2) = 12$, $p(3) = 30$, $p(4) = 74$, y $p(5) = 184$.
El deseado de límites puede ser formulada en términos de cocientes de Rayleigh $R_n = \frac{u A^n u'}{u u'}$:
$$2.4^n \le R_n \le 2.5^n$$
debido a que el denominador $u u' = 5$, por lo que el $p(n) = 5 R_{n-1}$. El límite superior está implícita en el cálculo de la autovalor dominante de la real simétrica $A^n$, que es el $n$th poder de la autovalor dominante de $A$.
Como WimC señaló, $A$ tiene un autovalor dominante $\lambda_{max} \approx 2.4812 \lt 2.5$. De hecho, $A$'s polinomio característico es $(\lambda^3 -2\lambda^2 -2\lambda + 2)(\lambda + 2)\lambda$ y hay cinco distintos real de los autovalores. En virtud de $A$ real simétrica, estos corresponden mutuamente ortogonal de vectores propios.
Los dos "fácil" autovalores $\lambda = -2,0$ corresponden a la unidad (a la izquierda) vectores propios $\frac{1}{2}\begin{pmatrix} 1&1&0&-1&-1 \end{pmatrix}$ e $\frac{1}{2}\begin{pmatrix} 1&-1&0&1&-1 \end{pmatrix}$ respectivamente. Estos pasan a ser ortogonal a $u$, y así no se utilizan a continuación para expresar $u$ en términos de la base ortonormales de $A$-vectores propios.
$$ \lambda_{max} \approx 2.4812, v_{max} \approx \begin{pmatrix} 0.52990 & 0.35775 & 0.42713 & 0.35775 & 0.52990 \end{pmatrix}$$
$$ \lambda_{med} \approx 0.68889, v_{med} \approx \begin{pmatrix} 0.17934 & -0.57645 & 0.52066 & -0.57645 & 0.17934 \end{pmatrix}$$
$$ \lambda_{min} \approx -1.17009, v_{min} \approx \begin{pmatrix} 0.43249 & -0.19929 & -0.73924 & -0.19929 & 0.43249 \end{pmatrix}$$
Tomando el punto-producto de $u$ con cada uno de estos vectores nos da la los coeficientes de la base de expansión:
$$ u \approx 2.20243 v_{max} - 0.27356 v_{mid} - 0.27284 v_{min} $$
Así, el cociente de Rayleigh $R_n$ puede ser calculada a partir de la expansión:
$$ A^n u' \aprox 2.20243 \lambda_{max}^n v_{max} - 0.27356 \lambda_{med}^n v_{mediados} - 0.27284 \lambda_{min}^n v_{min} $$
$$ R_n \aprox (2.20243^2 \lambda_{max}^n + 0.27356^2 \lambda_{med}^n + 0.27284^2 \lambda_{min}^n)/5 $$
El límite inferior $R_n \ge 2.4^n$ puede ser establecido por señalar que es sostiene con la igualdad de la $n=0,1$ y, a continuación, mostrando que $2.4^{-n} R_n$ aumenta a partir de entonces:
$$ 2.4^{-n} R_n \approx 0.97014 (\frac{\lambda_{max}}{2.4})^n + 0.01497 (\frac{\lambda_{med}}{2.4})^n + 0.01489 (\frac{\lambda_{min}}{2.4})^n $$
La creciente líder plazo, cuya base $\frac{\lambda_{max}}{2.4}$ supera los 1, será, por supuesto, eventualmente dominante de los otros dos términos, uno de los cuales es positivo pero la reducción y el otro se alternan en signo (pero también de la reducción).
El tratamiento de esta como una función continua de la exponente n (más de positivos reales) y diferenciar da una prueba concreta de que los aumentos de $n \gt 1$, lo que de acuerdo con los varios valores iniciales ya tabulados:
$$2.4^{-1} R_1 = 1$$
$$2.4^{-2} R_2 = 1.041666...$$
$$2.4^{-3} R_3 = 1.07060185...$$
$$2.4^{-4} R_4 = 1.109182098765432...$$
Es solo una idea (no es una respuesta completa). Deje $p_k(n)$ el número de $n$-números de dos dígitos de la información solicitada de forma que termina en el dígito $k$. A continuación, $p_k(1) = 1$ para todos los $k \in \{1, \dotsc, 5\}$ e $p_k(n+1)$ puede ser calculada de forma recursiva por
$$ \begin{pmatrix} p_1(n+1) \\ p_2(n+1) \\ p_3(n+1) \\ p_4(n+1) \\ p_5(n+1) \end{pmatrix} = \begin{pmatrix} 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} p_1(n) \\ p_2(n) \\ p_3(n) \\ p_4(n) \\ p_5(n) \end{pmatrix} $$
El mayor autovalor de la matriz de la izquierda es $\approx 2.48$ para una estrictamente positivo autovector. No todos los demás valores propios tienen la norma de menos de $1$ a pesar de que, de modo más refinado argumento sigue siendo necesaria.
He aquí un segundo enfoque, que depende más del álgebra y menos en el análisis.
Recordemos que $p(n)$ cuenta la cantidad permitida $n$números que se pueden formar a partir de {1,2,3,4,5} tal que los dedos adyacentes difieren en por lo menos dos. Tenga en cuenta que $p(n)$ es un entero positivo para cada entero positivo $n$.
En primer lugar vamos a mostrar que $p(n)$ satisface las siguientes lineal de la relación de recurrencia:
$$p(n+1) = 2p(n) + 2p(n-1) - 2p(n-2)$$
A continuación, vamos a utilizar la inducción para demostrar por $n = 1,2,3,\dots$ :
$$ 2.4 \le p(n+1)/p(n) \le 2.5 $$
De $p(1) = 5$ se sigue que $5 \cdot 2.4^{n-1} \le p(n) \le 5 \cdot 2.5^{n-1}$.
La recurrencia de la relación:
Considere la posibilidad de expresar $p(n) = (p_1(n)+p_5(n)) + (p_2(n)+p_4(n)) + p_3(n)$ cuando, antes de $p_d(n)$ indica el conteo de número permitido con el primer dígito $d$.
El punto de inscribir $p_1(n)$ e $p_5(n)$ juntos (resp. $p_2(n)$ e $p_4(n)$) es que las reglas de transición son simplificado cuando los números son así agrupados. En lugar de una $5 \times 5$ de la matriz de transición, sólo necesitamos un $3 \times 3$ matriz:
$$ p(n) = (1\;1\;1) \begin{pmatrix} 1&1&2\\1&1&0\\1&0&0 \end{pmatrix}^{n-1} \begin{pmatrix} 2\\2\\1 \end{pmatrix} $$
Permítanme decodificar la matriz de transición $A$ se muestra aquí. De cuántas maneras existen para obtener un permitidos $n$número de un dígito con un líder 1 o 5? Para cada permitido $n-1$número de un dígito, hay una manera para así extender si se comenzó con 1 o 5 (con el prefijo de la alternativa), una manera de extender si se inició con 2 o 4, y dos maneras de extender si se comenzó con 3. Del mismo modo para obtener un permitidos $n$número de un dígito con un líder 2 o 4, hay una manera de extender un antes dígito 1 o 5, una manera de extender un 2 o 4, y no hay manera de extender un 3. Por último sólo hay una manera de extender a un número permitido con los principales 3, y que requiere la previa dígito a 1 o 5.
El lineal de la recurrencia de la relación es ahora una fácil consecuencia de $A$ satisfactorio polinomio característico $| \lambda I - A| = \lambda^3 - 2 \lambda^2 - 2 \lambda +2 $.
Límites por Inducción:
Comencemos por señalar algunas de las proporciones iniciales $p(n+1)/p(n)$.
$$ \begin{array}{cl} \underline{ n } & p(n+1)/p(n) \\ 1 & 2.4 \\ 2 & 2.5 \\ 3 & 2.4\overline{6} \\ 4 & 2.4\overline{864} \\ 5 & 2.47826086956522\ldots \\ 6 & 2.48245614035088\ldots \\ 7 & 2.4\overline{814} \end{array} $$
Ciertamente, las proporciones parecen asentarse en el intervalo de $[2.4,2.5]$. En cualquier caso, los valores que se muestran servirá como base el paso de inducción.
Supongamos que por el bien de la generalidad que sabemos límites:
$$a \le p(n)/p(n-1), p(n-1)/p(n-2) \le b$$
para constantes positivas $a,b$. La evidente manipulación de la desigualdad de los rendimientos:
$$ b^{-1} \le p(n-1)/p(n) \le a^{-1} $$ $$ b^{-2} \le p(n-2)/p(n) \le a^{-2} $$
Aplicado a una consecuencia inmediata de la relación de recurrencia:
$$ p(n+1)/p(n) = 2(1 + p(n-1)/p(n) - p(n-2)/p(n)) $$
uno obtiene los sucesivos límites:
$$ 2(1 + b^{-1} - a^{-2}) \le p(n+1)/p(n) \le 2(1 + a^{-1} - b^{-2}) $$
Ahora bien, si establecemos $a = 2.47$ e $b = 2.49$, los límites de evaluar a:
$$ 2.475\ldots \le p(n+1)/p(n) \le 2.487\ldots $$
La combinación de las entradas de la tabla con esta inducción paso para$n \ge 6$, lo que demuestra el tratado de límites de $2.4 \le p(n+1)/p(n) \le 2.5$ para todos los enteros positivos.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
