Prueba por inducción de que si $n \in \mathbb N$ entonces se puede escribir como la suma de diferentes números de Fibonacci

Question

Prueba de que todo número natural $n\in \mathbb N$ se puede escribir como la suma de diferentes números de Fibonacci entre $F_2,F_3,\ldots,F_k,\ldots$ .

Por ejemplo: $32 = 21 + 8+3 = F_8+F_6+F_4$

Esfuerzo de investigación:

El paso base es sencillo:

Dejemos que $k=1$ puede ser quebrada como $k=1=F_2$

Para el paso inductivo consideré:

Dejemos que $k = k F_2 =F_2+F_2+\cdots+F_2 = \sum_{i=2}^w a_iF_i, a_i =\{0,1\} $

Entonces, si $k$ basta con que quiera ver si $k+1$ también es suficiente... Pero no estoy viendo realmente cómo usar la hipótesis inductiva, así que asumo que está mal.

¿Alguna idea sobre cuál puede ser el paso inductivo?

Answer 1

Tienes que usar la inducción generalizada:

Si $$ \text{$ P_k $ is true for all $ k\in \mathbb N $ with $ k<n $} \implies P_n $$ entonces $$ \text{$ P_n $ is true for all $ n\in \mathbb N $} $$

Luego aplica la idea sugerida en las otras respuestas. Para representar el número $n$ se toma el más grande $F_i$ tal que $F_i\le n$ . A continuación, aplique las hipótesis de inducción sobre $n-F_i$ . La cuestión es notar que $n - F_i< F_i$ porque $F_i < 2 F_{i-1}$ .

Answer 2

Sugerencia: Deja que $F_\ell$ sea el mayor número de Fibonacci $\le k$ . Aplicar la hipótesis de inducción a $k-F_\ell$ . Observa que todavía tienes que asegurarte de que todos los números de Fibonacci utilizados serán diferentes.

Answer 3

Ni siquiera hace falta la inducción para demostrarlo.

En primer lugar, hay que tener en cuenta que para cualquier $n>0$ siempre hay $F_k$ tal que $\frac n2<F_k\leq n$ . Es válido para $n=1$ si no, toma el más alto $F_k\leq\frac n2$ entonces $F_k\geq1$ Así que $\frac n2<F_{k+1}\leq2F_k\leq n$ .

Ahora supongamos que no todos los números se pueden escribir así y tomemos el más bajo $n$ . Pero según el resultado anterior, hay $F_k$ tal que $\frac n2<F_k\leq n$ .

Ahora $n-F_k$ puede escribirse como una suma de diferentes números de Fibonacci según nuestra elección de $n$ pero esto significa que $n$ también se puede escribir, porque $n-F_k>n-\frac n2=\frac n2$ , por lo que los otros números de Fibonacci eran menores o iguales a $\frac n2$ y por lo tanto menos que $F_k$ Así que tenemos una contradicción.

Answer 4

(Demostración de Zeckendorf:) Supongamos que es cierto para todos los enteros hasta e incluyendo $F_n$ y que $F_{n+1} \ge N > F_n$ . Ahora, $N = F_n +(N−F_n)$ y $N \le F_{n+1} < 2F_n$ es decir, $N−F_n < F_n$ . Así, $N − F_n$ puede escribirse de la forma $F_{t_1} +\ldots+ F_{t_r}$ ,

$N − F_n < t_{i+1} \le t_{i}−2$ , $t_r \ge 2$ ,

y $N = F_n + F_{t_1} + F_{t_2} +\ldots+F_{t_r}$ .

Podemos estar seguros de que $n \ge t_1 + 2$ porque, si tuviéramos $n = t_1 + 1$ entonces $F_n=F_{t_1+1}+2F_n$ . Pero esto es más grande que N. De hecho, $F_n$ debe aparecer en la representación de $N$ porque no hay suma de números de Fibonacci más pequeños, obedeciendo a $k_{i+1} \le k_i − 2$ , $(i=1,2,\ldots,r − 1)$ y $k_r ≥ 2$ , podría sumar $N$ .

De ello se desprende que, si $n$ es incluso, digamos $2k$ , de $F_{2k−1} + F_{2k−3} +\ldots+ F_3= (F_{2k} − F_{2k−2}) + (F_{2k−2} − F_{2k−4}) +\ldots+ (F_4 − F_2)$ , que es $F_{2k}−1$ y si $n$ es impar, digamos $2k − 1$ se deduce de $F_{2k} + F_{2k−2} +\ldots+ F_2=(F_{2k+1} − F_{2k−1}) +\ldots+(F_3−F_1)=F_{2k−1} − 1$ .

De nuevo, el mayor $F_i$ sin exceder $N − F_n$ debe aparecer en la representación de $N − F_n$ y no puede ser $F_{n−1}$ . Nótese que esto demuestra la unicidad por inducción.