Si consideri la successione di Fibonacci definita mediante la funzione $F: N \rightarrow N$ nel seguente modo:
$$
F(0)=1, \quad F(1)=1, \quad F(n)=F(n-1)+F(n-2) \quad \text { per } n>1 .
$$
Determinare le immagini dei primi 6 numeri naturali e dimostrare per induzione forte su $n$ che la funzione $F$ è crescente, ossia
$$
F(n) \leq F(n+1) \text { per ogni } n \in N .
$$
127
punti
Livello 1
F(2) = 1 + 1 = 2
F(3) = 2 + 1 = 3
F(4) = 3 + 2 = 5
F(5) = 5 + 3 = 8
F(6) = 8 + 5 = 13
F(1) >= F(0) vale per uguaglianza : sono entrambi 1
Se F(k+1) >= F(k) fino a n
F(n+1) = F(n) + F(n-1) >= F(n) + F(0) = F(n) + 1 > F(n)
perché F(n-1) >= F(0) per ipotesi di induzione se n >= 1
36714
punti
Livello 6
La funzione é iniettiva perché strettamente crescente come abbiamo visto. Non é suriettiva da N a N perché ad esempio 20 non é un numero di Fibonacci, ovvero non esiste alcun m : F(m) = 20.
Quindi non é biiettiva e non ammette inversa.
