Demostrar que todo entero positivo se puede escribir como una suma finita de potencias enteras distintas del número de oro $\varphi=\frac{1+\sqrt{5}}{2}$. Aquí, una potencia entera de $\varphi$ es de la forma $\varphi ^i$, donde $i$ es un entero (no necesariamente positivo).
Vamos a demostrar por inducción que todo entero positivo $n$ se puede expresar de la forma
$n=\varphi^{a_1}+\varphi^{a_2}+...+\varphi^{a_k}$
Donde $a_1<a_2<...<a_k$ y $a_{i+1}-a_i\geq 2$.
Para $n=1$ tenemos que $1=\varphi^{0}$, supongamos que para $n$ lo podemos construir, veamos que pasa para $n+1$.
Si $n=\varphi^{a_1}+\varphi^{a_2}+...+\varphi^{a_k}$ entonces $n+1=\varphi^{0}+\varphi^{a_1}+\varphi^{a_2}+...+\varphi^{a_k}$
Ahora vamos a realizar dos algoritmos, si existe $i$ tal que $a_i=0$ hacemos el algoritmo 1 y el 2, si no existe tal $i$ vamos directo al algoritmo 2.
En ambos algoritmos se va a utilizar que $\varphi^{n+2}=\varphi^{n+1}+\varphi^{n}$ lo cual es cierto ya que al multiplicar por $\varphi^{-n}$ obtenemos $\varphi^{2}=\varphi^{1}+1$.
Algoritmo 1
Si existe $i$ tal que $\varphi^{a_i}$ aparece dos veces en la suma reemplazamos uno de estos por $\varphi^{a_i-1}+\varphi^{a_1-2}$, si ahora existe un nuevo $i'$ tal que $\varphi^{a_{i'}}$ aparece dos veces en la suma entonces repetimos el algoritmo en caso contrario pasamos al algoritmo 2.
Veamos que este algoritmo termina, primero notemos que si antes de aplicarlo solo había una potencia de $\varphi$ que se repetía dos veces y su exponente se podía expresar como $a_i$ entonces luego de aplicar el algoritmo hay dos opciones, ya no se repite ninguna potencia de $\varphi$ por lo que el algoritmo termina o hay una nueva potencia de $\varphi$ que se repite dos veces, esta puede ser $\varphi^{a_i-1}$ ó/y $\varphi^{a_i-2}$, de esto sabemos que $i$ va decreciendo.
Si $\varphi^{a_i-1}$ es la que se repite entonces la otra copia es un $a_j$ ó apareció de aplicar el algoritmo en $a_{i}+1$ ó en $a_i$ (en $a_i$ es imposible porque $i$ va decreciendo), en el primer caso tenemos que $a_i-1=a_j\Rightarrow a_i-a_j=1$ contradicción, en el segundo caso como se aplico el algoritmo en $a_i+1$ existe un $j$ tal que $a_j=a_i+1\Rightarrow a_j-a_i=1$ contradicción por lo tanto $\varphi^{a_i-1}$ no se repite.
Si $\varphi^{a_i-2}$ es la que se repite entonces la otra copia es un $a_j$ ó apareció de aplicar el algoritmo en $a_{i}$ ó en $a_{i-1}$, en el primer caso volvemos a aplicar el algoritmo y el segundo caso contradice que $i$ decrece.
Como cada vez que se aplica el algoritmo $i>i'>0$ (en el caso de haber un $i'$) tenemos que este termina.
Algoritmo 2
Si en la suma están $\varphi^{m}$ y $\varphi^{m-1}$ y no esta $\varphi^{m+1}$ reemplazamos $\varphi^{m}+\varphi^{m-1}$ por $\varphi^{m+1}$, si esta situación sigue sucediendo aplicamos de vuelta el algoritmo en caso contrario finalizamos.
Este algoritmo termina ya que la cantidad de potencias de $\varphi$ se reduce en cada paso.
Una vez terminados ambos algoritmos nos queda $n+1=\varphi^{b_1}+\varphi^{b_2}+...+\varphi^{b_q}$, por el algoritmo 1 sabemos que todas las potencias son distintas, así que $b_1<b_2<...<b_q$, también se cumple que $b_{i+1}-b_i\geq 2$ ya que en caso contrario si $j$ es el mayor entero positivo que no cumple entonces $b_{j+1}-b_j=1$ y $b_{j+2}>b_{j+1}+1$ pero esto contradice que el algoritmo 2 haya terminado y con esto concluimos la inducción.