kozmoforum.hu

Szerző: **G.Á** » 2022.03.12. 15:22

Szerző: **G.Á** » 2022.03.12. 16:12

Felmerült, hogy a házik megoldását konzultáció keretében beszéljük meg, de a megfelelő időpont megszavazásának nehézségei, plusz kényelmi okokból érdemesebb és egyszerűbb itt, írásban elvégezni ezt.

Az 1.HF:

1. Teljes indukcióval igazolja az alábbi összefüggéseket!
a) \sum_{k=1}^n k(k+1)(k+2)= \dfrac{n(n+1)(n+2)(n+3)}{4}
d) 1^2 \cdot 2 + 2^2 \cdot 3 + 3^2 \cdot 4 + \dots + n^2(n+1) = \dfrac{n(n+1)(3n^2+7n+2)}{12}

A teljes indukció első lépése megmutatni, hogy a bizonyítandó összefüggés legalább egy (jelen esetben n=1) esetben igaz. Ezután azt kell megmutatni, hogy ha adott "n" értékre igaz az összefüggés, akkor "n+1"-re is igaz. Ezen két lépésből együtt már következik hogy minden "n" természetes számra is igaz lesz.

1/a)
"n=1"-re igaz, mert

1\cdot2\cdot3 = \dfrac{1\cdot2\cdot3 \cdot4}{4} = 6
Ezután írjuk fel, hogy:

\sum_{k=1}^{n+1} k(k+1)(k+2)= \sum_{k=1}^{n} k(k+1)(k+2) + (n+1)(n+2)(n+3)
Ha adott "n"-re igaz az összefüggés, akkor a fenti sor úgy írható, hogy:

\sum_{k=1}^{n+1} k(k+1)(k+2)= \frac{n(n+1)(n+2)(n+3)}{4} + (n+1)(n+2)(n+3) = \frac{(n+1)(n+2)(n+3)(n+4)}{4}
ami kielégíti a formulát.

1/d)
"n=1"-re igaz, mert

1\cdot2 = \frac{1\cdot2\cdot12}{12} = 2
Ezután:

\sum_{k=1}^{n+1} k^2(k+1)= \sum_{k=1}^{n} k^2(k+1) + (n+1)^2(n+2)
Ha adott "n"-re igaz az összefüggés, akkor a fenti sor úgy írható, hogy:

\sum_{k=1}^{n+1} k^2(k+1)= \frac{n(n+1)(3n^2+7n+2)}{12} + (n+1)^2(n+2) = \frac{n(n+1)(3n^2+7n+2) + 12(n+1)^2(n+2)}{12}
= \frac{(n+1)\big[n(3n^2+7n+2) + 12(n+1)(n+2)\big]}{12}
A másodrendű polinom felbontásával, majd ekvivalens átalakításokkal

\sum_{k=1}^{n+1} k^2(k+1)
= \frac{(n+1)\big[n(n+2)(3n+1) + 12(n+1)(n+2)\big]}{12}= \frac{(n+1)(n+2)\big[n(3n+1) + 12(n+1)\big]}{12}= \frac{(n+1)(n+2)\big[3n^2 + 13n + 12 \big]}{12}
Ami már átírható úgy, hogy:

= \frac{(n+1)(n+2)\big[3(n+1)^2 + 7(n+1) + 2 \big]}{12}
amely éppen a formulának megfelelő.

3. Skatulya-elv segítségével oldja meg az alábbi feladatokat!
c) Tegyük fel, hogy m db labdát elhelyezünk n db dobozban, és m < n(n − 1)/2. Mutassa meg, hogy ekkor legalább 2 dobozban ugyanolyan számú labda van!

3/c)
Definiáljuk a 0 darab, 1 darab, 2 darab,...j darab... "m" darab labdát tartalmazó dobozok (diszjunkt)

I_j halmazait. Mivel "n" darab doboz van, ezért

\sum_{j=0}^m|I_j|=n.

A skatulya-elv definíciószerű alkalmazásával az írható, hogy (mivel összesen "m+1" darab halmaz van):

\exists i,k : |I_i|\geq \lceil{\frac{n}{m+1}} \rceil , |I_k|\leq \lfloor{\frac{n}{m+1}} \rfloor
Ez azonban nem elegendő az állítás bizonyításához, így meg kell próbálnunk a nemüres halmazok számára vonatkozó, "m+1"-nél alacsonyabb felső becslést adni.

Felírható, hogy

\sum_{j=0}^m|I_j|j=m<n(n-1)/2, és ez alapján belátható, hogy legfeljebb "n" db (pontosabban "n"-nél kevesebb) nemüres

I_j halmaz van.
Ebben az esetben ("n" db dobozt "n*<n" halmazba rendelünk) a skatulyaelv szerint:

\exists i : |I_i|\geq \lceil{\frac{n}{n*}} \rceil=2

vagyis létezik olyan

I_j halmaz, mely elemszáma legalább kettő, vagyis legalább 2 dobozban ugyanannyi labda van.

kozmoforum.hu

Diszkrét matematika - házifeladatok

Diszkrét matematika - házifeladatok

Re: Diszkrét matematika - házifeladatok

Ki van itt