Prueba de inducción y divisibilidad por $2^n$

Question

Estoy tratando de usar la inducción para demostrar que para cada número entero $n > 0$ existe un $n$ -A(n) que es divisible por $2^n$ y que consiste enteramente en los dígitos "1" y "2".

¿Alguien tiene una idea de por dónde empezar?

He encontrado ejemplos que funcionan con números pequeños y el paso inicial de la prueba de inducción no es un problema. Necesito demostrarlo para $n+1$ ahora.

Gracias por cualquier consejo.

Answer 1

Definir el $n$ -de la siguiente manera. Sea $f(1)=2$ . Supongamos que hemos definido $f(n)$ y $2^n$ divide $f(n)$ . Entonces defina $f(n+1)$ de la siguiente manera.

Si $2^{n+1}$ divide $f(n)$ entonces $f(n+1)$ se obtiene poniendo un $2$ delante de la expansión decimal de $f(n)$ . O, por decirlo de otra manera, $f(n+1)=2\cdot 10^n+f(n)$ . Si $2^{n+1}$ no divide $f(n)$ entonces $f(n+1)$ se obtiene poniendo un $1$ delante de la expansión decimal de $f(n)$ Es decir, $f(n+1)=10^n+f(n)$ . Demostramos que $2^{n+1}$ divide $f(n+1)$ .

Supongamos primero que $2^{n+1}$ divide $f(n)$ . Entonces $f(n+1)=2\cdot 10^n+f(n)$ . Tenga en cuenta que $2\cdot 10^n$ es divisible por $2^{n+1}$ lo que demuestra que $f(n+1)$ es divisible por $2^{n+1}$ .

Supongamos a continuación que $2^{n+1}$ no divide $f(n)$ . Entonces $f(n)\equiv 2^n\pmod{2^{n+1}}$ (el resto cuando dividimos $10^n$ por $2^{n+1}$ es $2^n$ ). Pero tenemos $10^n \equiv 2^n \pmod{2^{n+1}}$ . De ello se desprende que $f(n+1)=10^n+f(n)\equiv 2^n+2^n\equiv 2^{n+1}\equiv 0\pmod{2^{n+1}}$ .

Answer 2

Mira los primeros $A(n)$ :

$$\begin{array}{c|r} n&A(n)\quad\\ \hline 1&2\\ 2&12\\ 3&112\\ 4&2112\\ 5&22112\\ 6&122112\\ 7&2122112\\ 8&12122112\\ 9&212122112 \end{array}$$

Obsérvese que cada $A(n)$ amplía el anterior añadiendo un $1$ o un $2$ en el extremo izquierdo. Esto significa que en cada caso hasta ahora tenemos $A(n+1)=a_n+10^n$ o $A(n+1)=a_n+2\cdot10^n$ . Esto sugiere tratar de probar que si $A(n)=k2^n$ para algún número entero $k$ , entonces uno de los números $a_n+10^n$ y $a_n+2\cdot10^n$ es un múltiplo de $2^{n+1}$ Si puedes hacerlo, ya tienes tu paso de inducción. CONSEJO: Considera por separado los casos $k$ incluso y $k$ impar, y observa que $10^n=2^n5^n$ .

Answer 3

Sugerencia $\ $ En general, si $\rm\:a_n = e\!\:c^n\:$ tiene $\rm\:n\:$ dígitos todos $\rm\in [1,c]\:$ en el radix $\rm\:bc,\ (b,c)=1, \:$ entonces

$$\rm\ c^{n+1}\:|\: d\:\!(bc)^n+e\!\:c^n \iff c\:|\: d\:\!b^n + e\iff d\equiv -e/b^n\ (mod\ c)$$

La elección de este tipo de $\rm\:d\in [1,c],\:$ obtenemos un $\rm\:a_{n+1}\:$ divisible por $\rm\:c^{n+1}$ teniendo $\rm\:n\!+\!1\:$ dígitos todos $\rm\in [1,c],\:$ porque $\rm\:a_{n+1}\:$ se construye a partir de $\rm\:a_n\:$ anteponiendo el nuevo dígito inicial $\rm\:d.$