Feladat: 3.11.
Bizonyítsuk be, hogy
a)
r
(
n
,
k
)
≤
r
(
n
,
k
-
1
)
+
r
(
n
-
1
,
k
)
;
b)
r
(
n
,
k
)
≤
(
n
+
k
-
2
k
-
1
)
, ha
n
,
k
≥
2
. (Erdős Pál és Szekeres György tétele.)
Segítség, útmutatás: 3.11
a) Alkalmazzuk ebben az esetben is az előző (a
3.10
.) feladat gondolatmenetét.
a)-ból b) teljes indukcióval következik.
[
Megoldás
]