Inductivo en demostrar que cualquier número natural $\ge 12$ puede escribirse como la suma de 4s y 5s

Question

Yo de manera intuitiva se puede ver por qué esto es cierto:

1. Supongamos $n = \alpha \times 4 + \beta \times 5$$\alpha,\beta \in \mathbb{N} \cup \{0\}$.
2. $\forall n \in \mathbb{N} \cup \{0\}$: $n \div 4$ producirá un resto $r \in \mathbb{N} \cup \{0\}$, $0 \le r \lt 4$.
3. $r$ se puede "dividir" en 1s, y cada uno de los 1s puede ser añadido a una el 4s que ir a $n$ a convertirlos en 5s. Por lo tanto, si $n = un\times4 + r \Rightarrow n = (a-r)\times4 + r\times5$ with $\in \mathbb{N}\cup\{0\}$.
4. Esa es la razón por la que esto funciona sólo para $n \ge 12=3\times4$: es fácilmente obvio por el principio del palomar, y si $a \lt 3 \Rightarrow \exists \ r \ | \ (a-r) \lt 0 \Rightarrow \alpha \lt 0$ lo que contradice la hipótesis inicial.

Podría darme un inicio para la aplicación de la prueba? No sé si la inducción sería el más sencillo o elegante manera de probarlo, pero tengo que hacerlo como un ejercicio (mi Primaria la Teoría del Número de libros de texto sugiere probar individualmente para $n\in[12,16]$ y, a continuación, utilizando 16 $n_0$). Entiendo cómo funciona la inducción, pero no puedo pensar en una manera de traducir este problema en ella. También me gustaría un poco de ayuda con formalmente que expresan el paso 3 de mi prueba.

Answer 1

Creo que su enfoque puede ser fácilmente utilizado para la inducción y es al menos tan buena como el libro de texto de la sugerencia de varios casos de base (lo que también es perfectamente adecuada la prueba).

Así que para construir sobre sus ideas, tenemos:

Caso Base
$12=4+4+4$

Paso inductivo
Asumir cierto para $k\ge 12$. Tenga en cuenta que tenemos, al menos, $3$ términos en la descomposición de la $k$. Por lo tanto, debemos tener ya sea (a) de tres a $5$s o (b) al menos uno de los $4$.

Para un $4$-$5$ la descomposición de la $k+1$: en el caso (a) sustituto cuatro $4$s de los tres $5$s en la descomposición de la $k$, y en el caso (b) sustituir a un $5$$4$.

---

Nota cómo esto se vincula con las ideas de la pregunta: el mayor valor de resto es $3$ - que es el caso que da tres $5$s en la descomposición. La posterior entero tiene resto $0$, dando no $5$s en la descomposición - de modo que los tres $5$s será sustituido por cuatro $4$s. El caso base se elige de modo que hay una partición válida que tiene (al menos) tres componentes. $12$ es el más pequeño de tales.

---

Para mayor claridad, el libro de texto fue (creo) esperando que demuestran la existencia de una tarjeta de particiones de$12$$15$, y, a continuación, utilizar la inducción de $k\ge 16$ con el inductivo suposición de que hay una solución para $k-4$, y a continuación, añadir otra $4$ a que la descomposición.

Answer 2

$12=4+4+4$

$13=4+4+5$

$14=4+5+5$

$15=5+5+5$

Ahora, supongamos $n>15$; como el inductivo hipótesis se puede asumir que cualquier número $m$ $12\le m<n$ puede ser escrito como la suma de los cuatros y cincos. A continuación, $n-4>11$ puede ser escrito como la suma de los cuatros y cincos, lo que implica la tesis también para $n$.

---

Este es de hecho un enfoque constructivo: se divide $n\ge12$$4$, con el resto $r$, $n=4q+r$,$0\le r<4$. A continuación,$q\ge3$$n\ge12$.

Si $r=0$ hemos terminado.

Si $r=1$, $n=4(q-1)+5$

Si $r=2$, $n=4(q-2)+5+5$

Si $r=3$, $n=4(q-3)+5+5+5$

Answer 3

Solo para ver el patrón: $12=4+4+4$. $13=4+4+5$. $14=4+5+5$. $15=5+5+5$. $16=4+4+4+4$.

Base caja: $12$.

Tenga en cuenta que $12=4+4+4$.

Inductivo caso.

Asumir que $n$ puede ser escrito como $n=4x+5y$ $x,y \in \mathbb{N}_0$.

Si $x>0$, entonces el $n=4(x-1)+4+5y$ % que $n+1=4(x-1)+5(y+1)$.

Si $x=0$, entonces el $n=5y$ % que $n+1=5y+1$. Nota $y\geq4$ (manejamos el caso $n=15$). Así, $n+1=5(y-3+3)+1=5(y-3)+16=5(y-3)+4+4+4+4$.

Answer 4

En general, el pollo McNugget teorema dice que cualquier % de enteros coprimos $p, q$, el más grande entero que no es de la forma $px + qy$ $pq - p - q$. Así que en este caso, $11$ es el más grande entero que no se puede expresar como así, para cada entero $\geq 12$ puede.

Answer 5

Inducción de 'fuerte' trivial.

$f(n):\space n$ es la suma de $4s$ y $5s$

$1)$base casos: $12/n_0,13,14,15,16/n_1$

$2)f(n)$

$3)f(n-4)\space\space 2)$

$4)(n-4)+5=n+1$

$5)f(n+1)\space\space 3),4)$

$6)f(n-4)\rightarrow f(n+1)\space\space 5)$

$7)f(n),n\ge 12\space\space 1),6)$ y de forma alternativa de inducción matemática