Školsko natjecanje 2010., 4. razred SŠ, A varijanta, 1. Zadatak
Dokaži da za svaki vrijedi
Rješenje
Prvo rješenje.
Identitet dokazujemo matematičkom indukcijom po .
Baza: za imamo .
Pretpostavka: pretpostavimo da tvrdnja vrijedi za neki prirodni broj .
Korak: za imamo Dakle, koristeći pretpostavku da tvrdnja vrijedi za dokazali smo da tvrdnja vrijedi i za pa stoga i za sve prirodne brojeve.
Napomena. Posljednji bod se ne dodjeljuje ako učenik nije pravilno zapisao dokaz metodom matematičke indukcije.
Drugo rješenje.
Dokaz kombinatornim argumentom. Dvije strane jednakosti prebrojavaju isti skup na različite načine. S desne strane je broj permutacija skupa pri čemu isključujemo mogućnost da se svaki broj preslikava u samog sebe.
S druge strane prebrojavamo isti skup (permutacije bez identitete) tako da promatramo slučajeve ovisno o najvećem broju koji se ne preslikava u samog sebe. Ako je najveći broj koji se ne preslikava u samog sebe , onda između brojeva manjih od možemo izabrati jedan koji se preslikava u , a preostale brojeve manje od zajedno s brojem preslikavamo u . To možemo učiniti na načina.
Budući da smo isključili mogućnost da se svaki broj preslikava u samog sebe, a s smo označili najveći broj koji se ne preslikava u samog sebe, slijedi da može biti bilo koji broj između 1 i pa je zaista rezultat .