Un poco tarde, pero estaba trabajando en este problema para una tarea y creo que esta prueba no fue mencionada antes.
Una prueba alternativa puede lograrse mediante el doble conteo. En primer lugar, tenemos que demostrar que Fn es el número de formas en que se puede escribir n como la suma de 1's o 2's (por ejemplo F3=|{1+2,1+1+1,2+1}| ). Para ello basta con demostrar que esto es cierto para n=1 y n=2 y para n≥3 Obsérvese que si el primer término es 1, los siguientes deben sumar n−1 el número de formas de hacerlo es Fn−1 y si el primer término es 2, entonces los siguientes términos deben sumar n−2 el número de formas de hacerlo es Fn−2 . Con estos hechos, podemos concluir que la secuencia que definimos es efectivamente la secuencia de fibonacci (si no estás convencido puedes demostrarlo inductivamente).
Teniendo esto en cuenta, consideremos el número de formas en que podemos escribir 2k como la suma de 1's o 2's. Como mostramos anteriormente esto es F2k . Ahora vamos a contar esto de una manera diferente. Si sumando término a término, pasamos por k entonces dividimos la suma en dos sumas de k por el principio del producto esto es F2k . Si es imposible pasar por k entonces debemos tener la situación, números que suman k−1 , luego un 2, luego números que suman k−1 . De nuevo, por el principio del producto, esto es F2k−1 . Por lo tanto, por el principio de la suma, tenemos que F2k=F2k−1+F2k
Remark El argumento de la doble contabilidad puede tener algunos problemas en el caso n=1 por lo que hay que demostrarlo. Pero este caso es trivial porque es un resultado directo de la definición de los números de Fibonacci.