Funzione definita a tratti (credo)

[lewis1]

Ciao a tutti!
Volevo chiedervi se potreste aiutarmi nel risolvere quest'esercizio...
L'ho trovato in un esame di matematica all'università, ma non ho idea di come risolverlo.

Sia f: N-->N un'applicazione così definita:

1 se n=0
f(x)= MCD(f(n-1), n) se n pari, n >=2
mcm(f(n-1), n) se n dispari


a) si provi per induzione che per ogni n pari si ha f(n)=1
b) si dimostri che per ogni n dispari si ha f(n)=n

Grazie mille.
Lew

[clrscr]

"lewis":Ciao a tutti!
Volevo chiedervi se potreste aiutarmi nel risolvere quest'esercizio...
L'ho trovato in un esame di matematica all'università, ma non ho idea di come risolverlo.

Sia f: N-->N un'applicazione così definita:

1 se n=0
f(x)= MCD(f(n-1), n) se n pari, n >=2
mcm(f(n-1), n) se n dispari


a) si provi per induzione che per ogni n pari si ha f(n)=1
b) si dimostri che per ogni n dispari si ha f(n)=n

Grazie mille.
Lew

Dunque, io ho ragionato così:
Per $n=0$ la dimostrazione è banale.
Ora assumendo vera la condizione $f(n)=1$ bisogna dimostrare che $f(n+2)=1$ (ho scritto n+2 perchè devo verificare se il successivo numero pari verifica la condizione).
Dalla definizione di questa funzione si osserva che $f(n+2)=M.C.D. {f(n+1),n+2}=M.C.D.{m.c.m.{f(n),n+1},n+2}$, sfruttando l'ipotesi induttiva si ottiene:
$f(n+2)=M.C.D. {1,n+2}=1$.

Per la seconda si verifica immediatamente che $f(1)=1$.
Ora l'ipotesi induttiva consiste in $f(n)=n$ e l'obiettivo è dimostrare che $f(n+2)=n+2$ per ogni "n" dispari.
Procedendo in modo analogo al caso precedente otteniamo:
$f(n+2)=m.c.m.{f(n+1),n+2}=m.c.m.{M.C.D.{f(n),n+1},n+2}$ sfruttando l'ipotesi induttiva si arriva alla conclusione:
$f(n+2)=m.c.m.{1,n+2}=n+2$.