Esercizi induzione

[domx]

Ciao ragazzi, non so se posto nella sezione giusta, in caso chiedo gentilmente ai moderatori di spostare
Nonostante lo scarso risultato alle olimpiadi di febbraio, ho deciso comunque che proverò per la Normale (dopo un periodo di titubanze ed uno passato a studiare in maniera pessima). Sto quindi riprendendo tutti gli argomenti, anche quelli che dovrei sapere, partendo da un livello molto basso e cercando di rendere ferma la mia conoscenza in proposito. Sto quindi cercando, per ora, degli esercizi sull'induzione, in modo da esercitarmi molto e da assimilare la cosa come si deve. Magari anche qualcosa sul pigeonhole non mi dispiacerebbe
mi sapreste indicare qualcosa?
Vi ringrazio in anticipo
P.S. @i mod: è possibile che in futuro abbia altre richieste simili da fare, in tal posso usare questo topic o ne devo aprire uno ogni volta? Grazie

[SkZ]

cerca qui
viewforum.php?f=26
che se ne' parlato varie volte

[domx]

cerca qui
viewforum.php?f=26
che se ne' parlato varie volte

in effetti sì, me ne accorgo solo ora...
comunque se conoscete qualche pdf con u nbel po' di esercizi me lo postereste comunque? Lì ci sono parecchi problemi, ma un pdf organico con gli esercizi non l'ho trovato (ma ora comunque cerco meglio)

[SkZ]

le lezioni di Gobbino? non ne hanno?

[domx]

le lezioni di Gobbino? non ne hanno?

sull'induzione no, sotto esercizi dice "Saltata!"...

[domx]

ho trovato qualcosa su google, posto i pdf, magari potrebbero servire a qualcuno
http://www.dima.unige.it/~baratter/foglio1_induz.pdf
http://www.dima.unige.it/~baratter/md08 ... 2_md08.pdf
http://www.dm.uniba.it/Members/farinola ... nload/file
ma sostanzialmente basta cercare "esercizi sull'induzione" su google per trovare parecchia roba (perché non ci ho pensato prima? )

[domx]

ragazzi, ho un dubbio sul pigeonhole e lo posto qui dato che comunque induzione e pigeonhole sono cose simili
Allora, si dice sempre che se ho nk+1 oggetti e n cassetti, ci sarà almeno un cassetto che conterrà k+1 oggetti.Non riesco a spiegarmi la cosa, faccio un esempio:
n= 10 k=2 => 21 oggetti e 10 cassetti. Anche se un cassetto conterrà 3 oggetti non riusciremo comunque a disporre tutto gli oggetti. Dove sbaglio?
Scusate se è una domanda stupida, ma preferisco farlo e togliermi il dubbio piuttosto che tenermi la lacuna
grazie

[max tre]

guarda che è giusto così...
il pigoeonhole si usa per dimostrare che almeno un cassetto ha almeno un tot di oggetti dentro (nel caso più semplice, dove un cassetto può contenere un oggetto, se hai n cassetti e n+k oggetti, almeno un cassetto deve contenere più di 1 oggetto)
nel caso in questione hai 10 cassetti e 21 oggetti, il pigeonhole lo usi per dimostrare che almeno un cassetto contiene più di 2 oggetti: infatti, al massimo, dopo aver messo 2 oggetti per cassetto, il 21° dovrai metterlo in un cassetto dove ci sono già 2 oggetti, ritrovandoti quindi con 9 cassetti con k=2 oggetti e 1 cassetto con k+1=3 oggetti ($ 9\cdot2+1\cdot3=21 $)

[max tre]

ci sarà almeno un cassetto che conterrà k+1 oggetti.

qua preciserei "ci sarà almeno un cassetto che conterrà almeno k+1 oggetti"
(volendo, nel tuo esempio, avresti potuto avere 1 cassetto con 1 oggetto, 1 con 4 oggetti e 8 con 2 cassetti; quindi nessuno con esattamente k+1=3 oggetti)
magari è una sottigliezza (è anche vero che un cassetto contiene 4 oggetti ovviamente ne contiene pure 3), ma è sempre meglio precisare

[domx]

Ah, ho capito, almeno uno deve averne tre vuol dire che gli altri possono averne due (chissà perché io pensavo necessariamente ad uno). Grazie, mi hai tolto un dubbio!

[max tre]

niente, probabilmente stavi mescolando l'esempio più classico con un caso leggermente più complesso

[amatrix92]

Sull' Engel trovi degli esercizi sull'induzione "veri" cioè che non sono la mera applicazione della regola. Per farti un esempio: sia $ a $ un reale tale che $ a + \frac{1}{a} \in \mathbb Z $. Dimostra che $ a^n + \frac{1}{a^n} \in \mathbb Z $ per $ n $ naturale.

[domx]

Sull' Engel trovi degli esercizi sull'induzione "veri" cioè che non sono la mera applicazione della regola. Per farti un esempio: sia $ a $ un reale tale che $ a + \frac{1}{a} \in \mathbb Z $. Dimostra che $ a^n + \frac{1}{a^n} \in \mathbb Z $ per $ n $ naturale.

ah grazie , sembra interessante. Ci penso meglio più tardi, ora così su due piedi non riesco a rispondere...
P.S.: ho trovato questi esercizi sul pigeonhole, dite che vanno bene? Secondo me non sono niente male, ieri ho fatto i primi (più semplici), oggi ho intenzione di finirli tutti...

[domx]

Ciao amatrix, ho avuto modo di pensarci solo ora (non troppo in verità), e non sono riuscito a cavarci un ragno dal buco. mi aiuteresti? E magari mi linkeresti dove scaricare/acquistare questo libro?
ciao e grazie

[amatrix92]

Sinceramente non saprei indicarti dove scaricarlo/acquistarlo a me lo passo un mio amico ma credo che il link su cui me lo uppo su megaupload sia scaduto e non saprei come rintracciarlo.. se qualcun 'altro sa dove trovarlo... però il livello è alto.. è di preparazione alle IMO. Per la soluzione prova a usare la doppia ipotesi induttiva sia su n che su n-1 e poi prova a dimostrare n+1 scomponendolo...