Kezdőlap


Feladat:	B.4237	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Ágoston Tamás , Cséke Balázs , Damásdi Gábor , Dolgos Tamás , Éles András , Énekes Péter , Janzer Olivér , Karl Erik Holter , Kiss Melinda Flóra , Kovács Áron , Márkus Bence , Mester Márton , Mészáros András , Perjési Gábor , Szabó Attila , Weimann Richárd , Weisz Gellért , Weisz Ágoston
Füzet:	2010/december, 537 - 538. oldal		PDF \| MathML
Témakör(ök):	Feladat, Számsorozatok, Teljes indukció módszere
Hivatkozás(ok):	Feladatok: 2010/január: B.4237

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.

Megoldás. Vizsgáljuk meg néhány $n$ számra a $\sum \frac{1}{x y}$ összeget. $n = 1$ -re csak egy számpár van: $\frac{1}{1 \cdot 1} = 1$ . Ha $n = 2$ , akkor két számpár van $(1; 2)$ és $(2; 1)$ , az összeg $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 1} = 1$ . Ha $n = 3$ , akkor 4 számpár van, $(1; 3)$ , $(3; 1)$ , $(2; 3)$ és $(3; 2)$ , az összeg

\begin{matrix} \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 1} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 2} = 1. \end{matrix}

Azt sejtjük, hogy tetszőleges

n

-re a

\sum \frac{1}{x y}

összeg 1. Az állítást teljes indukcióval bizonyítjuk. Tegyük fel, hogy

n = k

-ra igaz az indukciós feltétel. Azt kell belátnunk, hogy

n = (k + 1)

-re is igaz az állítás. Az összeg olyan

\frac{1}{x y}

törtek összegével csökken, amelyekre

x + y = k + 1

, ugyanis ezekre még teljesül az

x + y > k

, de nem teljesül az

x + y > k + 1

feltétel. Ugyanakkor nő az összeg az olyan

\frac{1}{x y}

törtek összegével, amelyekre

x = k + 1

és

y

relatív prímek, illetve azokkal, amelyekre

y = k + 1

és

x

relatív prímek. Ezek a párok eddig nem szerepeltek, hiszen mindegyik szám kisebb volt, mint

k + 1

.
Ismert, hogy ha

x

és

y

relatív prímek, akkor

(x + y; x) = 1

és

(x + y; y) = 1

. Ha ugyanis lenne

(x + y)

-nak és

x

-nek egynél nagyobb közös osztója, akkor az osztaná a két szám különbségét, vagyis

y

-t is, ez viszont ellentmondana annak a ténynek, hogy

x

és

y

relatív prímek. Ennek ismeretében fogjuk belátni, hogy az összeg pontosan annyival csökken, mint amennyivel nő. Az előbb láttuk, hogy minden

x

y

számpárhoz hozzárendelhető két számpár,

(x + y; x)

és

(x + y; y)

, melyekre

\begin{matrix} \frac{1}{(x + y) x} + \frac{1}{(x + y) y} = \frac{1}{x + y} (\frac{1}{x} + \frac{1}{y}) = \frac{1}{x + y} \cdot \frac{x + y}{x y} = \frac{1}{x y} . \end{matrix}

Azt is látjuk, hogy az összeget növelő tagok mindegyikének megadható az

(x; y)

párja: ha

x + y = k + 1

és

x

relatív prímek, akkor

x

és

y

is relatív prímek. A fenti megfeleltetés tehát kölcsönösen egyértelmű. Ezzel beláttuk, hogy ha

k

-ról

(k + 1)

-re változik az

n

, akkor az összeg 1 marad.
Tehát a feladatban szereplő törtek összege minden pozitív egész

n

esetén 1.