Matematické Fórum

Krokzakrokem

Chtěla bych prosím požádat o pomoc s příkladem, u kterého se nedokáží vyjádřit, tápu, jak zformulovat indukční krok a dekompozici:

V tomto příkladu [m,n] značí množinu všech funkcí definovaných na množině {1, ..., m} s hodnotami v množině {1,…,n}, tj. f $\in$ [m,n] <—> f : {1,…,m} —-> {1,…,n}.
Matematickou indukcí dokažte, že množina [m,n] má $n^{m}$ prvků, kde $m,n \in N^{+}$ .

(a) Jasně definujte výrok, který dokazujete.
Pro f $\in$ [m,n] <—> f : {1,…,m} —-> {1,…,n}, [m,n] má $n^{m}$ prvků, kde $m,n \in N^{+}$ .

(b) Podle jaké proměnné indukci provádíte?
podle n

(c) Jasně vyznačte a dokažte základní krok matematické indukce.
f $\in$ [m,n] <—> f : {1} —-> {1}, kde $m,n \in N^{+}$
[m,n] má $1^{1} = 1$ prvek. To platí.

(d) Jasně zformulujte výrok zvaný indukční krok.
Pro f $\in$ [m,n+1] <—> f : {1,…,m} —-> {1,…,n+1}, [m,n+1] má $n+1^{m}$ prvků, kde $m,n \in N^{+}$ .

(e) Jasně zformulujte indukční předpoklad a dokažte indukční krok. V důkazu vyznačte dekompozici problému a použití indukčního předpokladu.
Tady netuším, jak dál... :-( Je třeba řešit indukci podle n, i m?

f) Jaký princip matematické indukce používate? (Tento pnncip nemusite definovat.)
podle mě stačí slabý princip

-------------------------------------

Předem děkuji za jakékoliv rady.

Rumburak

↑ Krokzakrokem:

Označme A = {1, ..., m}, B = {1,…,n}, F nechť je množina všech funkcí s definičním oborem A a s hodnotami v B.
Máme dokázat, že počet prvků množiny F je $n^{m}$ .

I. Když m = 1, tedy A = {1} , pak funkci $f$ patřící do F můžeme definovat právě n způsoby, a to tak, žë
prvku 1 přiřadíme některý z n prvků množiny B. Počet prvků množiny F je tedy n neboli $n^{1}$ , tj. $n^{m}$ ,
protože zde m= 1, jak předpokládáme.

II. Předpokládejme, že dokazovaná věta platí pro nějaká přípustná m, n a máme dokázat, že platí i pro dvojici
m', n, kde m' = m+1.

Ponechme v platnosti dosavadní označení a označme ještě A' = {1, ..., m, m+1}. Funkci g s definičním oborem A'
a s hodnotami v B můžeme sestrojit následovně:

1. zvolíme některou funkci f s def. oborem A , k čemuž máme k disposici $n^{m}$ možností (dle indukčního předpokladu)

2. zvolíme některý prvek y v množině B, k čemuž máme n možností, neboť množina B je n-prvková.

3. Definujeme

g(x) := f(x) , pokud x patří do A', g(m+1) := y .

Tímto způsobem můžeme sestrojit KAŽDOU z uvažovaných funkcí g, při čemž volby 1, 2 jsou navzájem
nezávslé. Počet všech možností, jak sestrojit uvažovanou funkci g, je tedy $n^{m} \cdot n = n^{m+1}$ .

Matematické Fórum

#1 25. 02. 2016 15:25 — Editoval Krokzakrokem (25. 02. 2016 20:00)

Matematická indukce - množina všech funkcí [m,n]

#2 26. 02. 2016 12:20 — Editoval Rumburak (26. 02. 2016 14:06)

Re: Matematická indukce - množina všech funkcí [m,n]

Zápatí