Kezdőlap


Feladat:	Pontversenyen kívüli P.162	Korcsoport: 18-	Nehézségi fok: -
Megoldó(k):	Bara Tamás , Gáncs István , Kiss Emil , Pócsi György
Füzet:	1974/december, 216 - 217. oldal		PDF \| MathML
Témakör(ök):	Összefüggések binomiális együtthatókra, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1973/január: Pontversenyen kívüli P.162

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.

Rendezzük az $(\binom{a}{b})$ , $a > b > 0$ binomiális együtthatókat sorokba és oszlopokba úgy, hogy $(\binom{a}{b})$ az $(a - b)$ -edik sor $b$ -edik oszlopába kerüljön. Akkor az

\begin{matrix} (\binom{a}{b}) = (\binom{a - 1}{b - 1}) + (\binom{a - 1}{b}) \end{matrix}

azonosság miatt minden együttható a felette levő és az előtte levő számok összegével egyenlő. Az (1) előállítás bal oldalán minden oszlopból egy szám található meg, és ha az összeget visszafelé olvassuk, akkor jobbról bal felé haladva a fenti sémában határozottan felfelé is kell haladnunk. Előfordulhat, hogy lesodródunk a sémáról, akkor van szükségünk az

a < b

párhoz tartozó

(\binom{a}{b})

együtthatókra.

\begin{matrix} 1 & 1 & 1 & 1... \\ 2 & 3 & 4 & 5... \\ 3 & 6 & 10 & 15... \\ 4 & 10 & 20 & 35... \\ 5 & 15 & 35 & 70... \\ 6 & 21 & 56 & 126... \\ ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}

A feladat állítását

k

szerinti teljes indukcióval látjuk be. Ha

k = 1

, az állítás nyilvánvaló, hiszen

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

Tegyük fel, hogy már beláttuk az állítást, minden

k

-nál kisebb tagszámra. Legyen

a_{k}

az a legnagyobb természetes szám, amelyre

\begin{matrix} (\binom{a_{k}}{k}) ≦ n, \end{matrix}

és tekintsük az

m = n - (\binom{a_{k}}{k})

szám

(k - 1)

tagú előállítását. Ha

m = 0

, akkor megfelel a következő összeg:

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

m > 0

, akkor feltevésünk szerint van (1) szerinti előállítása:

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

Elég megmutatni, hogy itt

a_{k - 1} < a_{k}

. Ha ugyanis

a_{k - 1} ≧ a_{k}

volna, akkor

\begin{matrix} (\binom{a_{k} + 1}{k}) = (\binom{a_{k}}{k - 1}) + (\binom{a_{k}}{k}) ≦ (\binom{a_{k - 1}}{k - 1}) + (\binom{a_{k}}{k}) ≦ m + (\binom{a_{n}}{k}) = n \end{matrix}

volna, ami nem lehet, hiszen

(\binom{a_{k}}{k})

volt a legnagyobb,

n

-nél nem nagyobb szám a

k

-adik oszlopban. Feladatunk állítását ezzel bebizonyítottuk.