Kezdőlap


Feladat:	F.2872	Korcsoport: 18-	Nehézségi fok: könnyű
Megoldó(k):	Barát János , Faragó Gergely , Futó Gábor , Imreh Csanád , Kerekes Balázs , Németh Ákos , Párniczky Benedek , Szeidl Ádám , Tóth Csaba D. , Ungár György
Füzet:	1992/május, 200 - 202. oldal		PDF \| MathML
Témakör(ök):	Összefüggések binomiális együtthatókra, Egészrész, törtrész függvények, Oszthatóság, Számelméleti függvények, Feladat
Hivatkozás(ok):	Feladatok: 1991/november: F.2872

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. Ha $n = 0,$ akkor az állítás az $(\binom{n}{k})$ együtthatónak $k = 0$ -ra való, ismert kiterjesztéséből következik.
Legyen $n \geq 1.$ Ekkor $(\binom{2 n}{n}) = \frac{(2 n)!}{n! \cdot n!}$ és $(\binom{2 n}{n - 1}) = \frac{(2 n)!}{(n - 1)! (n + 1)!},$ amiből

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

(1)

Mivel

n és n + 1

relatív prímek, a bal oldalon álló

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

szorzat csak úgy lehet osztható

(n + 1)

-gyel, ha

(\binom{2 n}{n})

osztható

(n + 1)

-gyel.
Megjegyzések 1. Az (1) azonosságot

n = 0

esetén nem írhatjuk fel, ezért kellett ezt az esetet külön megvizsgálni.
2. (1)-et a következőképpen is átrendezhetjük:

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

Eszerint

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

két egész szám különbsége.
Megjegyzés. A

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

számot az

n

-edik Catalan-számnak nevezik. Többféle kombinatorikai jelentése van: ennyiféleképpen lehet zárójelezni egy

(n + 1)

-tagú összeget, ennyiféleképpen lehet egy konvex

(n + 2)

-szöget

(n - 1)

átló behúzásával háromszögekre bontani stb.
Ha bevezetjük a

C_{n} = \frac{(\binom{2 n}{n})}{n + 1}

jelölést, akkor teljesül a következő rekurzió:

\begin{matrix} C_{n + 1} = C_{0} C_{n} + C_{1} C_{n - 1} + C_{2} C_{n - 2} + ... + C_{n} C_{0} . \end{matrix}

Az állítás ebből is következik, bár már a rekurzió bizonyítása is hosszabb, mint maga a megoldás.
II. megoldás. Bebizonyítjuk, hogy tetszőleges

p

prímszámra

(\binom{2 n}{n}) = \frac{(2 n)!}{n! \cdot n!}

prímtényezős felbontásában a

p

kitevője legalább akkora, mint az

(n + 1)

prímtényezős felbontásában. (Ez ekvivalens az állítással.)
Legyen

α a p

kitevője az

(n + 1)

felbontásában. Ismeretes, hogy

p

kitevője

(2 n)!,

illetve

{(n!)}^{2}

prímtényezős felbontásában

\begin{matrix} S = \sum_{i = 1}^{\infty} [\frac{2 n}{p^{i}}], illetve D = 2 \sum_{i = 1}^{\infty} [\frac{n}{p^{i}}] . \end{matrix}

([x]

x

egész részét jelöli.) Azt kell igazolnunk, hogy

\begin{matrix} S \geq α + D . \end{matrix}

(2)

Ehhez megmutatjuk, hogy

\begin{matrix} [\frac{2 n}{p^{i}}] = 1 + 2 [\frac{n}{p^{i}}], ha 1 \leq i \leq α, és & (3) \\ [\frac{2 n}{p^{i}}] \geq 2 [\frac{n}{p^{i}}], ha i > α . & (4) \end{matrix}

Ha ezeket az egyenlőtlenségeket összeadjuk (

i

mindazon értékeire, amelyekre

[\frac{2 n}{p^{i}}] > 0),

éppen

(2)

-t kapjuk.
Legyen

1 \leq i \leq α .

Mivel

p^{α}

osztója

(n + 1)

-nek,

p^{i}

is osztója

(n + 1)

-nek. Legyen

k = \frac{n + 1}{p^{i}},

azaz

n = p^{i} k - 1.

Az előbbiek szerint

k

egész szám, ezért

\begin{matrix} [\frac{2 n}{p^{i}}] = [\frac{2 p^{i} k - 2}{p^{i}}] = [2 k - \frac{2}{p^{i}}] = 2 k - 1 és \\ 2 [\frac{n}{p^{i}}] = 2 [\frac{p^{i} k - 1}{p^{i}}] = 2 [k - \frac{1}{p^{i}}] = 2 (k - 1) = 2 k - 2. \end{matrix}

Ezzel (3)-at igazoltuk. Mivel pedig

[2 x] \geq 2 [x]

tetszőleges

x

valós számra, (4) is igaz.
Ezzel az állítást bebizonyítottuk.

Szeidl Ádám (Miskolc, Földes F. Gimn., II. o. t.)