Dimostrazione algebrica

[UmbertoM1]

Sia $n$ un numero naturale. Sappiamo che $f(n)=n-f(f(n-1))$ e sia $f(1)=1$
Come si dimostra che $f(n+f(n))=n$ per ogni valore valore di $n>1$

[UmbertoM1]

Anche se non riuscite a risolverlo, qualche spunto è gradito, perchè io non so davvero che pesci pigliare

[milizia96]

Una cosa che si nota (e si dimostra) è che $f(n+1)-f(n) in {0,1}, AA n>=1$
Tra l'altro una conseguenza di questo fatto è che $f(n)<=n, AAn in NN$
Dimostrazione:

Dimostriamolo per induzione.
PASSO BASE:
si verifica la validità per $n=1$.

PASSO INDUTTIVO:
supponiamo che sia valido per tutti gli $n$ che vanno da $1$ a $k-1$ : dimostreremo che vale anche per $n=k$.
$f(k+1)-f(k)=$
$=k+1-f(f(k))-k+f(f(k-1))=$
$=1-(f(f(k))-f(f(k-1)))$
Adesso abbiamo due casi:
caso A) $f(k)=f(k-1)$ quindi l'espressione è uguale a $1$
caso B) $f(k)=f(k-1)+1$ quindi l'espressione diventa $1-[f(f(k-1)+1)-f(f(k-1))] $
Ora gli argomenti $f(k-1)+1$ e $f(k-1)$ sono due numeri consecutivi e sono minori o uguali a $k$ (questo perché l'ipotesi induttiva che abbiamo posto garantisce che $f(n)<=n$, con $n<=k$). Quindi la differenza dentro la parentesi quadra è uguale a $0$ oppure a $1$, e l'espressione assume valore $1$ oppure $0$.

Un'altra conseguenza importante: dato un numero naturale $n$, esiste sempre $m in NN$ tale che $f(m)=n$
E allora si può procedere così:

$f(n+f(n))=f(f(m)+f(f(m)))$
da come è definita la funzione si ricava che $f(f(n-1))=n-f(n)$
che possiamo applicare alla doppia $f$ presente nell'espressione.
$f(f(m)+m+1-f(m+1))$
ora si presentano due casi:
A) $f(m)=f(m+1)$ quindi l'espressione diventa $f(m+1)=f(m)=n$
B) $f(m+1)=f(m)+1$ e l'espressione diventa direttamente $f(m)=n$

in ogni caso otteniamo $f(n+f(n))=n$ che è quello che volevamo dimostrare.