Dubbio sulle generalizzazioni

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Dubbio sulle generalizzazioni

Messaggio da Gerald Lambeau »

Solitamente in combinatoria o TdN, abbiamo $n$ intero positivo e vogliamo trovare $f(n)$ intero positivo tale che sia minimo (o massimo) a fare qualche cosa, per ogni $n$.
Supponiamo di aver dimostrato che con un certo $f(n)$ ci si fa. Vale, per dire che effettivamente è il minimo (prendiamo come esempio il minimo), dire che siccome questa formula generale deve valere per ogni $n$ allora deve valere anche per un certo $h$ intero positivo fissato (cioè un numero, che so, 2) e mostrare che per $f(h)-1$ non ci si fa?
In altre parole: io so che per ogni $n$ $f(n)$ ce la fa, ma c'è quella simpatica canaglia di $h$ per la quale $f(h)-1$ non ce la fa. Se $f(n)-1$ ce la facesse per ogni altro $n$, $f(n)$ è ancora valida o dobbiamo trovare una $g(n)$ che faccia $f(n)$ in $h$ e $f(n)-1$ in ogni altro $n$?

Insomma: $f(n)-1$ deve essere fallace per ogni $n$?
"If only I could be so grossly incandescent!"
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Dubbio sulle generalizzazioni

Messaggio da karlosson_sul_tetto »

Si, per avere una dimostrazione rigorosa devi verificare che per ogni $n$, $f(n)-1$ non funziona (e quindi $f(n)$ si).

Nei casi particolari, potrebbe accadere che $f(n)$ abbia delle caratteristiche che permettano una scorciatoia: per esempio una sua qualche monotonia/gradiente (cioé quanto vale al max $f(n+1)-f(n)$) oppure il poter essere ottenuta per induzione (se da $f(n)$ posso ottenere $f(n+1)$, allora magari se per $h$ vale $f(h)-1$ per $h+1$ vale $f(h+1)-1$).
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Dubbio sulle generalizzazioni

Messaggio da Gerald Lambeau »

Immaginavo, grazie mille.
"If only I could be so grossly incandescent!"
Rispondi