Dimostrare che ogni numero intero positivo si può scrivere come la somma di numeri di Fibonacci distinti.
Io ho proceduto per induzione. Il passo base è verificato banalmente per $n=1$, quindi supponiamo che la tesi sia valida per tutti gli interi positivi da $1$ ad un certo $n$ fissato, allora possiamo distinguere 2 casi:
$n+1$ è un numero di Fibonacci, allora la tesi è banalmente vera;
$n+1$ non è un numero di Fibonacci, dunque sia $a$ il numero di fibonacci, quindi $n+1-a=b$, con $1 \leq b \leq n$ che per ipotesi induttiva è scrivibile come somma di numeri di Fibonacci, questa equazione è equivalente a $a+b=n+1$. In definitiva, essendo $a$ un numero di Fibonacci e $b$ una somma di numeri di Fibonacci diversi da $a$, la tesi è verificata.
Riflettendo sulla dimostrazione ho anche pensato che per ipotesi induttiva $n$ è un numero di Fibonacci, e $1$ lo è evidentemente, quindi $n+1$ è banalmente un numero di Fibonacci. È valido anche questo ragionamento?
