Kezdőlap


Feladat:	807. matematika feladat	Korcsoport: 16-17	Nehézségi fok: átlagos
Füzet:	1957/október, 54 - 56. oldal		PDF \| MathML
Témakör(ök):	Összefüggések binomiális együtthatókra, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1957/február: 807. matematika feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. megoldás: Induljunk ki a következő ismert azonosságból ¹

\begin{matrix} (\binom{n + 1}{k - 1}) + (\binom{n + 1}{k}) = (\binom{n + 2}{k}) . \end{matrix}

(1)

k = 1

esetén

\begin{matrix} (\binom{n + 1}{0}) + (\binom{n + 1}{1}) = (\binom{n + 2}{1}) . \end{matrix}

Adjunk mindkét oldalhoz

(\binom{n + 2}{2})

-t:

\begin{matrix} (\binom{n + 1}{0}) + (\binom{n + 1}{1}) + (\binom{n + 2}{2}) = (\binom{n + 2}{1}) + (\binom{n + 2}{2}) = (\binom{n + 3}{2}) . \end{matrix}

Mindkét esetben az első tag 1, és ez írható

(\binom{n}{0})

alakban is, így a következő azonosság látszik kialakulni:

\begin{matrix} (\binom{n}{0}) + (\binom{n + 1}{1}) + (\binom{n + 2}{2}) + ... + (\binom{n + k}{k}) = (\binom{n + k + 1}{k}) \end{matrix}

(2)

Ennek helyességét

k = 1

-re és 2-re már igazoltuk. Teljes indukcióval bizonyítjuk, hogy ez minden

k

-ra fennáll.
Tegyük fel, hogy valamilyen

k

-ra igaz (2). Adjunk mindkét oldalhoz

(\binom{n + k + 1}{k + 1})

-t:

\begin{matrix} (\binom{n}{0}) + (\binom{n + 1}{1}) + (\binom{n + 2}{2}) + ... + (\binom{n + k}{k}) + (\binom{n + k + 1}{k + 1}) = \\ = (\binom{n + k + 1}{k}) + (\binom{n + k + 1}{k + 1}) . \end{matrix}

De (1) alapján a jobb oldal

(\binom{n + k + 2}{k + 1})

, vagyis a (2) képlet

(k + 1)

-re is igaz, az adott

S_{k}

sor összege tehát

\begin{matrix} S_{k} = (\binom{n + k + 1}{k}) . \end{matrix}

Feladatkitűző megoldása

II. megoldás: Felhasználva, hogy

(\binom{m}{k})

m

elemből alkotható

k

-ad osztályú kombinációk száma, bebizonyítjuk az

\begin{matrix} (\binom{n + k + 1}{k}) = (\binom{n + k}{k}) + (\binom{n + k - 1}{k - 1}) + ... + (\binom{n}{0}) \end{matrix}

azonosság helyességét. A bal oldal az

n + k + 1

elemből pl. az

1,2, ..., n + k + 1

számokból kiválasztható

k + 1

elemű kombinációk száma, vagyis a kiválasztható

k + 1

elemű csoportoké, ha az elemek sorrendjére nem vagyunk tekintettel, pl. mindig nagyság szerint növekvő sorrendben rendezzük az elemeket. Ezeket a csoportokat soroljuk osztályokba aszerint, hogy hány egymás utáni szám szerepel bennük a számsor elejéről. Az első csoportba az 1-et nem tartalmazó kombinációk száma nyilván

\begin{matrix} (\binom{n + k}{k}) . \end{matrix}

Ezután jönnek azok a kombinációk, amelyek az 1-et tartalmazzák, de a 2-t nem, majd azok, amelyek az 1-et, 2-t tartalmazzák, de a 3-at nem s. i. t. Általában az

1, 2, ..., i

-t tartalmazó, de

i + 1

-et nem tartalmazó kombinációkban az

i + 2, ..., n + k + 1

elemek, vagyis

n + k - i

elem közül kell a már kiválasztott

1, ..., i

elemek mellé még

k - i

elemet kiválasztani. Az ilyen kombinációk száma tehát

\begin{matrix} (\binom{n + k - i}{k - i}) . \end{matrix}

(Ez

i = 0

-ra az 1-et nem tartalmazó kombinációk számát is kiadja, és helyes eredményt ad

i = k

-ra is.) Ezt

i = 0,1, ..., k

-ra összegezve valóban megkapjuk az

n + k + 1

elemből kiválasztható összes

k

-elemű kombinációk számát. Ezzel igazoltuk a fenti azonosságot.

III. megoldás: Ismeretes,² hogy

(\binom{m}{l})

l = 0, 1, ..., m

értékekre az

{(a + b)}^{m}

polinom alakjában fellépő együtthatók:

\begin{matrix} {(a + b)}^{m} = (\binom{m}{0}) a^{m} + (\binom{m}{1}) a^{m - 1} b + ... + (\binom{m}{l}) a^{m - l} b^{l} + ... + (\binom{m}{m}) b^{m} . \end{matrix}

Ezt figyelembe véve a feladatban szereplő összeg lesz az

a^{n}

tag együtthatója az

\begin{matrix} 1 + (a + 1) + {(a + 1)}^{2} + ... + {(a + 1)}^{n + k} \end{matrix}

összegben, ha ezt a hatványai szerint rendezzük. Ez az összeg egy

n + k + 1

tagú mértani sor, melynek hányadosa

a + 1

, s így a következő zárt alakban írható:

\begin{matrix} \frac{{(a + 1)}^{n + k + 1} - 1}{(a + 1) - 1} = \frac{1}{a} {(\binom{n + k + 1}{0}) a^{n + k + 1} + (\binom{n + k + 1}{1}) a^{n + k} + ... + \\ + (\binom{n + k + 1}{i}) a^{n + k + 1 - i} + ... + (\binom{n + k + 1}{n + k}) a + (\binom{n + k + 1}{n + k + 1}) - 1} \end{matrix}

A zárójelben az utolsó pozitív tag értéke 1, így

a

-val tagonként elvégezhető az osztás. Az

n

-edfokú tagot úgy kapjuk, hogy a zárójelben az

n + 1

-edfokú tagot osztjuk

a

-val; az

n + 1

-edfokú tag együtthatója pedig

(\binom{n + k + 1}{k})

. Így a következő azonossághoz jutottunk:

\begin{matrix} (\binom{n}{0}) + (\binom{n + 1}{1}) + ... + (\binom{n + k}{k}) = (\binom{n + k + 1}{k}) . \end{matrix}

¹Lásd a Matematikai Versenytételek I. rész 28. old. vagy a K. M. L. IV. kötet 1952. május‐június, 121. old:

²Lásd a Matematikai Versenytételek I. rész 64. old. vagy K. M. L. IV. kötet, 1952. május‐június, 117. old.