A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
A
6. série Téma:
Korbeláøovy identity
Termín odeslání:
10. bøezna 2003
1. úloha
Ne h» (ak )1 k=1 je posloupnost pøirozený h èísel. Uka¾te, ¾e ka¾dé pøirozené n splòuje rovnost: n X n X
ai
j=
+
i=1 j =i
n X i X i=1 j =1
ai j : +
2. úloha
Uka¾te, ¾e pro ka¾dé pøirozené n je následují í rovnost splnìna: 1 [ nX 2 ℄
n
2k + 1
k=0
[2℄ X n n
=
k=0 2k
:
3. úloha
Uka¾te, ¾e pro libovolné n pøirozené je hodnota souètu n X
2n 4i 9n i 2i i=0
rovna výrazu
2n +1
5
2
.
4. úloha
Doka¾te, ¾e pro libovolná pøirozená èísla m; n taková, ¾e m n, platí m X n
k=0
n 2n : = m k m k
5. úloha
Doka¾te, ¾e pro libovolné pøirozené n je splnìna rovnost n X
( 1)k+1 n n = : k k + 1 n + 1 k=1 6. úloha
Pro obe né pøirozené n vyjádøete polynom v promìnné x
pn (x) = v o nejjednodu¹¹ím tvaru.
n X
( 1)k (x
k=0
i
k )n
n
k
A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
7. úloha
Pro libovolné pøirozené n uka¾te, ¾e [3℄ X n n
k=0
3k
=
1 n n 2 + 2 os : 3 3
8. úloha
Uka¾te, ¾e pro pøirozená èísla d; r taková, ¾e d > 2r, platí r dd X j =0
j
r j 1 2r = r j r!
ii
rY1 k=0
(d
2k
1):
A
A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
A
Øe¹ení 6. série
1. úloha
Ne h» (ak )1 k=1 je posloupnost pøirozený h èísel. Uka¾te, ¾e ka¾dé pøirozené n splòuje rovnost: n X n X i=1 j =i
ai
j=
+
n X i X i=1 j =1
ai j : +
Uva¾ujme ètver ovou tabulku o n sloup í h a n øád í h. Pole v k. øádku a l. sloup i znaème (k; l). Z tabulky vy¹krtejme ta pole (k; l), pro nì¾ je k l 1. Zbude nám tedy trojúhelníková tabulka. Do nevy¹krtaný h polí (k; l) napi¹me hodnotu ak+l . Spoèítejme souèet v¹e h hodnot napsaný h v tabul e. Nejprve tuto hodnotu poèítejme po øád í h. V i. øádku zùstala nevy¹krtána ta pole (i; j ), pro která je i j 0, neboli j i. Tedy (proto¾e j n) souèet hodnot v i. øádku je: n X j =i
ai j : +
Seèteme-li tyto hodnoty pøes v¹e hny øádky, dostáváme souèet hodnot v tabul e: n X n X i=1 j =i
ai j : +
Nadále poèítejme souèet v¹e h hodnot v tabul e po sloup í h. V i. øádku zùstala nevy¹krtána ta pole (j; i), pro která je j i 0, neboli j i. Tedy souèet hodnot v i. sloup i je: i X j =1
ai j : +
Seèteme-li tyto hodnoty pøes v¹e hny sloup e, dostáváme souèet hodnot v tabul e: i n X X i=1 j =1
ai j : +
Oba výrazy uvedené v zadání jsou tedy souètem v¹e h hodnot v tabul e, proto se musí rovnat. Poznámky k do¹lým øe¹ením: Myslím, ¾e øe¹itelé v¹e h ¹patný h øe¹ení ( elkem 5) si nezkusili rozepsat sumy pro nìjaká malá n. Napøíklad pro n = 4 vyjde 4 4 X X
i=1 j =i
ai
j = a2 + a3 + 2 a4 + 2 a5 + 2 a6 + a7 + a8 =
+
iii
i 4 X X i=1 j =1
ai j : +
A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
A
Pak je zøejmé, ¾e koe ient u a2n není n, u a5 není 3 a u an+1 není n. Zároveò nebudu tvrdit, ¾e rovnost obe nì neplatí, kdy¾ pro n = 4 platí. Toto je dobrý zpùsob, jak se vyhnout zbyteèným
hybám. Ostatní øe¹itelé dostali plný poèet bodù. 2. úloha
Uka¾te, ¾e pro ka¾dé pøirozené n je následují í rovnost splnìna: 1 [ nX 2 ℄
k=0
n
2k + 1
[2℄ X n n
=
k=0 2k
:
První mo¾nost, jak úlohu vyøe¹it, je vyu¾ít binomi kou vìtu. Je 2n = (1 + 1)n = 0 = (1
1)n =
n X n ; 1n i 1i =
n X n
i=0 i n X i=0
i=0
i
n X
n n n i 1 ( 1)i = : ( 1)i i i i =0
Nyní tyto rovnosti nejdøíve seèteme a potom odeèteme, èím¾ dostaneme rovnosti [2℄ X n n
2n = 2
k=0 2k
;
1
[X 2 ℄ n 2n = 2 : k=0 2k + 1 n
Proto¾e se rovnají levé strany, rovnají se i pravé strany a po vydìlení dvìma dostáváme po¾adovanou rovnost. Úlohu lze v¹ak øe¹it i názornìji bez binomi ké vìty. Nejprve si uvìdomme, ¾e na levé stranì rovnosti máme poèet v¹e h podmno¾in li hé velikosti n-prvkové mno¾iny a na pravé poèet v¹e h podmno¾in sudé velikosti té¾e mno¾iny. Vezmìme si jeden prvek, oznaème ho a. Nyní v¹e hny podmno¾iny þspárujemeÿ tak, ¾e do dvoji e dáme ty, které se li¹í právì o prvek a (tedy mají stejné prvky, jen jedna obsahuje naví prvek a). Vidíme, ¾e ka¾dé podmno¾inì jsme pøiøadili právì jedno þdvojèeÿ (nebo» jsme z ní buï ubrali nebo do ní pøidali a, èím¾ jsme jí jednoznaènì urèili þpartneraÿ), naví v ka¾dé dvoji i je jedna podmno¾ina sudé velikosti a jedna podmno¾ina li hé velikosti (nebo» se li¹í právì o jeden prvek), ukázali jsme tak, ¾e podmno¾in sudé velikosti je stejnì jak podmno¾in li hé velikosti, o¾ nám pøesnì øíká dokazovaná rovnost. Poznámky k do¹lým øe¹ením: Úloha byla velmi snadná, vìt¹ina øe¹itelù vyu¾ila binomi kou vìtu nebo dùkaz matemati kou induk í a obdr¾ela plný poèet bodù. Nìkolik øe¹itelù pouze pøepsalo zadání úlohy do jiného tvaru a tvrdili, ¾e to je známé tvrzení. Ano, je tomu tak, ale úkolem bylo ho dokázat. 3. úloha
iv
A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
A
Uka¾te, ¾e pro libovolné n pøirozené je hodnota souètu n X
2n 4i 9n i 2i i=0
rovna výrazu
2n +1
5
2
.
Nejprve se h eme øe¹itelùm omluvit. Pøi pøedávání úlohy do¹lo k jakémusi ¹umu, a tak se tato úloha objevila v komentáøí h s nesprávným zadáním. Na internetu byla velmi brzo opravena. Zde u¾ je napsáno správné zadání. Kdy¾ si uvìdomíme, ¾e 5 = 3 + 2 a 1 = 3 2, je ji¾ úloha vpodstatì vyøe¹ena. Potom toti¾ 2n X
52n = (3 + 2)2n =
1 = 12n = (3
2)2n =
j =0 2n X
2n ; 2j 32n j
j
2n ; ( 1)j 2j 32n j
j
j =0
Kdy¾ tyto dva výrazy seèteme, èleny souètu se sudým j se seètou, èleny s li hým j se odeètou, oznaèíme-li j = 2i, dostaneme tak: 52n + 1 = 2
n X i=0
22i 32n
2
n i 2n = 2 X 4i 9n i 2n :
2i
i=0
2i
Po vydìlení dvìma dostaneme po¾adovanou rovnost. Poznámky k do¹lým øe¹ením: Nìkolik øe¹itelù ukázalo, ¾e pùvodní tvrzení neplatí, tím, ¾e dosadili n = 1. Vhledem k nejasnosti zadání jsem za taková øe¹ení udìlovala plný poèet bodù, aèkoliv si myslím, ¾e bylo v silá h øe¹itelù zformulovat správné tvrzení a dokázat ho. Chválím ty, kteøí to udìlali, pøípadnì se podívali na stránky semináøe, kde na¹li opravené øe¹ení. 4. úloha
Doka¾te, ¾e pro libovolná pøirozená èísla m; n taková, ¾e m n, platí m X n k=0
n
k m k
=
2n
m
:
Pøedstavme si, ¾e máme 2n kulièek a h eme z ni h vybrat právì m. Potom v¹e h mo¾ný h 2n m . Výbìr ale mù¾eme provést i jinak. Rozdìlme si kulièky na dvì hromádky po n kuse h. Nyní mù¾eme vybrat z první hromádky 0 kulièek a z druhé m, takový h mo¾ností je n n , mù¾eme ale také z první hromádky vybrat 1 kulièku a z druhé m 1, to nám dává n0 mn mo¾ností, takto mù¾eme pokraèovat a¾ k mo¾nosti, kdy z první hromádky vybereme 1 m 1 m kulièek a z druhé 0. Proto¾e jsme tímto získali v¹e hny mo¾nosti, jak z onì h dvou hromádek vybrat m kulièek, seètením tì hto souèinù dostaneme poèet v¹e h mo¾ností výbìru. Vidíme, ¾e
m-ti je
v
A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
A
tento souèet je právì levá strana dokazované rovnosti. Ukázali jsme, ¾e obì strany udávají poèet m-ti na 2n-prvkové mno¾inì, urèitì se tedy rovnají. Poznámky k do¹lým øe¹ením: Vìt¹ina øe¹ení byla správnì. Vedle my¹lenky vzorového øe¹ení se vyskytla pomìrnì èastá alternativa podívat se na koe ient u xm na straná h rovnosti (1 + x)n (1 + x)n = (1 + x)2n , uvedení obou mo¾ností jsem o enil +i. 5. úloha
Doka¾te, ¾e pro libovolné pøirozené n je splnìna rovnost n X
n ( 1)k+1 n = : k k + 1 n + 1 k=1 Nejprve vyu¾ijeme rovnost z 2. úlohy, kde místo n dosadíme n + 1 a odeèteme levou stranu, dostáváme rovnost nX +1 n + 1 = 0; ( 1)j
j
j =0
nebo mù¾eme opìt vyu¾ít binomi kou vìtu a rozpis 0 = (1
nX +1
1)n+1 =
k=0
n + 1 : 1k ( 1)n k
k
Nyní postupnì upravujme výraz ze zadání této úlohy: n X
n n X ( 1)k+1 n X ( 1)k+1 n! ( 1)k+1 (n + 1)! = = = k=1 k + 1 k k=1 (k + 1)!(n k)! k=1 (n + 1)(k + 1)!(n k)!
= =
1 n+1
+1 n n + 1 n + 1 1 nX 1 X = ( 1)k+1 = ( 1)j k+1 j n + 1 k=1 n + 1 j =2
1 + (n + 1) +
nX +1 j =0
( 1)j
n + 1
!
j
=
1
n+1
( 1 + (n + 1) + 0) =
n ; n+1
kde jsme v závìru dosadili vý¹e odvozenou rovnost. Poznámky k do¹lým øe¹ením: Ako sa ukázalo, tak táto úloha vám nerobila väè¹ie problémy (aspoò nie tým èo ju poslali), staèilo sa tam toti¾ iba tro hu pohra» s nejakými sumami a nájs» tam jednu binomi kú vetu a bolo, tak¾e najmä preto to skoro v¹et i mali za pä» : : : 6. úloha
Pro obe né pøirozené n vyjádøete polynom v promìnné x
pn (x) = v o nejjednodu¹¹ím tvaru.
n X
( 1)k (x
k=0
vi
k )n
n
k
A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
A
P Pro úèely øe¹ení si oznaème qn;m (x) = nk=0 ( 1)k (x k)m nk pro 0 m < n. Nejprve odvodíme rekurentní vyjádøení pro qn;m (x) a pak spoèteme polynom qn;n (x) = pn (x).
Pro n; m 1 máme
qn;m (x) =
=x
n X k=0
( 1)k (x
= xqn;m
= xqn;m
1
(x)
n
nX1 l=0
1
n X k=0
( 1)k (x
k )m
(x) +
( 1)l (x
1
n
n X
k
k)(x k)m
+
n X
1
k
k)m
n
l
1
1
i=
k )m
k=1
( 1)k n(x
l )m
n
( 1)k k(x
k=1
1
1
1
n
k 1
= xqn;m
1
(x)
1
n
k
=
=
nqn
Ne h» n > 0, pak snadno nahlédneme (napø. s vyu¾itím 2. úlohy), ¾e qn;0 = Z toho s vyu¾itím rekurze postupnì pro 0 m < n vy hází
;m1 (x
1
k n k=0 ( 1) k = 0.
Pn
qn; (x) = qn; (x) = = qn;n (x) = 0: 0
1
1
Av¹ak
pn (x) = qn;n (x) = nqn
;n
1
1
(x
1) = = n!q0;0 (x
V¹imnìte si, ¾e na promìnné x vlastnì vùbe nezále¾í. vii
1):
n) = n!:
A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
A
7. úloha
Pro libovolné pøirozené n uka¾te, ¾e [3℄ X n n
3k
k=0
=
1 n n 2 + 2 os : 3 3
První øe¹ení. Tato úloha má hezké øe¹ení vy¾ívají í h komplexní h èísel, nejprve v¹ak uka¾me øe¹ení, které lze vymyslet, pokud nám nìkdo uká¾e jen výsledek sumy. n Dohodnìme se, ¾e v pøípadì m > n nebo n < 0 budeme brát binomi ké koe ienty m n + n = n+1 platí. Takto mù¾eme vzít indexy nulové, a tedy základní vztah pro souèty m m+1 m+1 v sumá h od 1 do n a netrápit se mezemi. Dále budeme potøebovat následují í goniometri ký vzore :
os
os = 2 sin
+ 2
sin
;
2
který se snadno odvodí ze souètový h vzor ù pro funk i kosinus ve výrazu os(x + y) os(x y). Hlavní my¹lenkou je nejprve nalézt obdobné vztahy pro souèty n X
n
n X
a
k=0 3k + 1
n
k=0 3k + 2
a následnì dokázat v¹e hny vztahy matemati kou induk í. Zkusme tedy zatím pøedpokládat, ¾e dokazovaný vztah platí, a odvodíme vý¹e uvedené vztahy. Bez újmy na obe nosti mù¾eme naví pøedpokládat, ¾e mají tvar 13 (2n + 2an ) a 31 (2n + 2bn ). n X n + 1
k=0
3k
1 n+1 (n + 1) 2 + 2 os 3 3
=
n X n
3k
k=0
=
+
n
3k + 2
;
n 1 n 1 n 2 + 2 os + (2 + 2bn ) ; 3 3 3
n (n + 2) (n + 1) n = os
os = sin + ; 3 3 3 6 3 Pn P kde v prvním øádku jsme vyu¾ili vztahu k=0 3kn 1 = nk=0 3kn+2 . Analogi ky
bn = os
n X n+1
k=0 3k + 2
1 n+1 (n + 3) 2 + 2 os 3 3
=
n X k=0
=
n
3k + 2
+
n
3k + 1
1 n (n + 2)) 2 + 2 os 3 3
;
+
1 n (2 + an ) ; 3
(n + 2) (n + 3) (n + 2) (n + 4)
os = sin + = os : 3 3 3 6 3 Nyní ji¾ je v¹e pøipravené k dùkazu, který provedeme matemati kou induk í.
an = os
viii
A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
A
Pro n = 0 jsou vzor e v poøádku, nebo» 00 = 1 = 13 20 + os 03 , 0 = 13 20 + os 43 a 0 = 13 20 + os 23 . Pøedpokládejme, jsme vztahy dokázali pro n = m, doka¾me je pro n = m + 1. Vzor e P¾e P m+1 n pro nk=0 m3+1 k a k=0 3k+2 se doká¾í stejnì jak v pøed hozí èásti, pøièem¾ vyu¾ijeme jeji h platnost pro n = m. Zbývá dokázat poslední vztah: n X m + 1 k=0
3k + 1
=
n X
m
3k + 1
k=0
+
m
3k
;
1 n+1 n (n + 5) 1 n (n + 4)) 1 n 2 + 2 os ; 2 + 2 os = 2 + 2 os + 3 3 3 3 3 3 (n + 4) (n + 4) n (n + 5)
os = sin( + ) = os :
os 3 3 3 6 3 A tím je dùkaz hotov. Druhé øe¹ení. K øe¹ení vyu¾ijeme nìjaké základní vlastnosti komplexní h èísel. Nejprve øe¹me rovni i x3 = 1. Tu lze upravit na tvar (x2 + x + 1)(x 1) = 0. Snadno spoèítáme koøeny kvadrati ké rovni e, které jsou:
p
1+i 3 ; x2 = 2
x = 1
p
1
2
i 3
:
Tøetí koøen je pak x3 = 1. Vyu¾itím Moivreovy vìty nebo pøímým spoèítáním snadno zjistíme, ¾e x2 = x21 ; 1 = x3 = x31 . Odtud plyne, ¾e x31k+i = xi1 . Nyní si z binomi ké vìty (a pou¾itím pøed hozího vztahu) vyjádøeme: (1 + x1 )n = (1 + x21 )n =
n
0
n
0
(1 + 1)n = n
0
=3
+ x21
n
0
Seètením dostáváme, ¾e (1 + x1 )n + (1 + x21 )n + 2n = 3
+ x1
+
n
1
n
1
n
1
+ x21 + x1
n
2
n
2
n
+
+
2
n
+ (1 + x1 + x21 )
n
+
n
+
1
n
+ +
n
3
+
n
3
+
n
3
+ :
+ (1 + x1 + x21 )
+ :
n
2
+3
n
3
+ =
6 3 0 Pøi poslední úpravì jsme vyu¾ili právì vlastnosti, ¾e x1 je øe¹ením kvadrati ké rovni e x2 + x +1 = 0. Odtud je n n n (1 + x1 )n + (1 + x21 )n + 2n + = + + = 6 3 0 3
=
p
i
1+
2
3
n
+
1
p
i
2
3 ix
3
n
+ 2n
=
A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
A
( os 60Æ + i sin 60Æ )n + ( os( 60Æ ) + i sin( 60Æ ))n + 2n = 3
os n60Æ + i sin n60Æ + os( n60Æ ) + i sin( n60Æ ) + 2n 2n + 2 os(n60Æ ) = = : 3 3 Co¾ je právì to, o jsme htìli dokázat (v pøedposlední úpravì jsme vyu¾ili Moivreovy vìty). =
8. úloha
Uka¾te, ¾e pro pøirozená èísla d; r taková, ¾e d > 2r, platí r dd X
r j 1 2r = r! r j
j
j =0
rY1 k=0
(d
2k
1):
Nejprve si tro hu poupravíme výraz na levé stranì: r r j 1 X d!(d r j 1)! = = ( d j )! j !(d 2r 1)!(r j )! r j j
r X d d j =0
j
=0
= =
r X j =0
r!d!(d r j 1)! = r!(d j )!j !(d 2r 1)!(r j )!
r X d! r (d r j 1)! = j r!(d 2r 1)! j (d j )! =0
=
r X r
d(d 1)(d 2) (d 2r) r! j
=0
1
j (d j )(d j 1) (d r j )
:
Potom si poupravíme výraz na stranì pravé: 2r rY1 (d r! k=0
2k
1) =
2r d(d r!d(d
1)(d 2)(d
2) (d 4) (d
2r ) : 2r )
Odtud vidíme, ¾e staèí dokázat: r X r j =0
j (d j )(d j
1 1) (d
r j)
=
d(d
2r 2)(d 4) (d
2r)
:
Nyní si povíme nì o o par iální h zlom í h. Jsou-li x1 ; x2 ; : : : xn navzájem rùzná reálná èísla a je-li Q(x) polynom stupnì men¹ího ne¾ n, potom existují jednoznaènì urèená reálná èísla A1 ; A2 ; : : : An taková, ¾e (x
A A An Q(x) : = + + + x )(x x ) (x xn ) x x x x x xn 1
1
2
2
1
2
(Rovnost hápeme jako rovnost výrazù, nastává pro v¹e hny hodnoty, pro nì¾ jsou oba výrazy de novány.) Výraz xA1x1 + xA2x2 + + xAnxn se nazývá rozklad výrazu (x x1 )(x Qx(x2 ))(x xn ) na par iální zlomky. x
A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
A
Dùkaz zde uvádìt nebudeme, není pøíli¹ tì¾ký, zvídavý ètenáø si ho jistì sám odvodí (náznak dùkazu plyne z následují í h úvah). Nyní se zabývejme tím, jak urèit hodnoty A1 ; A2 ; : : : ; An . Platí-li: (x
A A An Q(x) ; = + + + x )(x x ) (x xn ) x x x x x xn 1
1
2
2
1
2
potom:
Q(x) = (x x1 )(x x2 ) (x xn ) A (x x2 )(x x3 ) (x xn ) + A2 (x x1 )(x x3 ) (x xn )+ = 1 (x x1 )(x x2 ) (x xn ) + + An (x x1 )(x x2 ) (x xn 1 ) : (x x1 )(x x2 ) (x xn ) První mo¾nost je výrazy v èitateli na pravé stranì roznásobit. Dostaneme tak polynom, který musí být roven polynomu Q(x), èím dostaneme n rovni pro n neznámý h A1 ; A2 ; : : : ; An . Tento zpùsob je ponìkud zdlouhavý. Dal¹í mo¾nost je uvìdomit si, ¾e má-li být výraz v èitatelí h rovný pro v¹e hna x 6= x1 ; x2 xn (tedy pro nekoneènì mnoho x), musí být rovný u¾ pro v¹e hna reálná x (polynomy stupnì n shodují í se v n + 1 hodnotá h jsou nutnì identi ké, nebo» jeji h rozdíl je polynom stupnì nejvý¹e n mají í n + 1 koøenù, tedy nulový polynom). Spe iálnì dostáváme, ¾e rovnost èitatelù musí nastat i pro x1 ; x2 ; : : : ; xn . Dosadíme-li (do èitatelù) tyto hodnoty, dostáváme: Q(xi ) = Ai (xi
x )(xi 1
x ) (xi
xi ) (xi
xi )(xi
2
1
+1
xn );
Q(xi ) ; (xi x1 )(xi x2 ) (xi xi 1 )(xi xi+1 ) (xi xn )
o¾ je o nì o jednodu¹¹í zpùsob, jak urèit Ai . Nyní tohoto povídání vyu¾ijeme pro na¹i úlohu. Rozlo¾me nejprve (d j )(d j par iální zlomky (v¹imnìte si, ¾e j; j + 1; : : : ; j + r jsou rùzná èísla). Máme Ai =
(d
j )(d j
1 1) (d
r j)
=
r X i=0
1 1)
d (
r j ) na
Ai ; d j i
kde dosazením do døíve odvozeného vzor e (zde Q je jednotkový polynom)
Ai = Dále podobným zpùsobem rozlo¾me d(d
d(d 2)(d kde
Bi =
1
i!( 1)r i (r i)! 2)(
d
1 4)
d
1 4) (d
1 2i (i!)( 2)r i (r
i)! xi
(
r na par iální zlomky. Dostáváme
2 )
2r) =
:
=
r X i=0
Bi ; d 2i
1 ( 1)r i 2r i!(r
i)!
:
A
A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
Nyní se vra»me k rovnosti kterou máme dokázat. r X r j =0
1 1) (d
j (d j )(d j
=
r j)
2r 2)(d 4) (d
d(d
2r)
:
Upravujme: r X r j =0
=
j (d j )(d j
r X r r r 1 X ( 1)r i j i d r! j =0 i=0
1 1) (d 1
i j
=
r j)
=
r X X r r i!( j =0
j
i=0
1)r
1
i(
r i)!
d i j
=
2r r r X 1 1 X ( 1)r i j i d i r! k=0 i;j 2f1;2;:::rg;i+j =k
j
:
V poslední úpravì jsme neudìlali ni jiného, ne¾ ¾e namísto seètení výrazu pøes v¹e hna i, j jsme výraz seèetli pøes v¹e hna i, j s pevným souètem k pøes v¹e hny mo¾né souèty k. Nakone upravíme na tvar: 2r r r X 1 X ( 1)r i j i d r! k=0 i;j 2f1;2;:::rg;i+j =k
= =
1
i j
=
2r r r 1 X 1 X ( 1)r i = j i d k r! k=0 i;j 2f1;2;:::rg;i+j =k 2r r r X 1 X 1 : ( 1)r i r! k=0 d k i;j 2f1;2;:::rg;i+j =k j i
Výraz na levé stranì dokazované nerovnosti také rozlo¾íme na par iální zlomky a budeme dále upravovat: 1 r X 2r ( 1)r i 2r i!(r i)! = 2r = d(d 2)(d 4) (d 2r) d 2i i=0 =
r r 2r 1 X 1 1X V (k); ( 1)r i i = r! i=0 d 2i r! k=0 d k
kde
V (k) = 0
pro k li hé a
V (k) = ( 1)r
k
2
r
k 2
pro k sudé. Srovnáním upravený h výrazù vidíme, ¾e staèí dokázat, ¾e
V (k) =
X
i;j 2f1;2;:::rg;i+j =k
xii
r r : ( 1)r i
j
i
A
Korespondenèní semináø, KAM MFF UK, Malostranské námìstí 25, 118 00 Praha 1
A
To u¾ je ov¹em velmi snadné. Mìjme polynom P (x) = (x2 1)r = (x 1)r (x + 1)r . Zkoumejme, jaký má tento polynom koe ient u výrazu xk pro k 2 f0; 1; : : : 2rg. Pomo í binomi ké vìty dostáváme r
P (x) = (x
r x2i ; ( 1)r i
X
1)r =
2
i=0
i
odkud je zøejmé, ¾e koe ient u xk je V (k). Na druhou stranu (opìt za pomo i binomi ké vìty)
P (x) = (x =
1)r (x + 1)r =
r X i=1
( 1)r i
2r r r X xk xi xj = ( 1)r i
r X r X j =1 i=1
i
neboli koe ient u xk je
j
k=0
X
i;j 2f1;2;:::rg;i+j =k
r
i
xi
!
r X r j =1
X
i;j 2f1;2;:::rg;i+j =k
j
xj
!
=
r r ; ( 1)r i
j
i
r r ; ( 1)r i
j
i
odtud plyne po¾adovaná rovnost:
V (k) =
X
i;j 2f1;2;:::rg;i+j =k
r r ; ( 1)r i
j
i
èím¾ je elá úloha dokázána. Poznámky k do¹lým øe¹ením: Pøi¹la pouze tøi øe¹ení, na druhou stranu byla v¹e hna správnì. Tì¹il jsem se, ¾e úlohu nìkdo vyøe¹í krásnou kombinatori kou úvahou, nestalo se tak, a tak v¹e hna øe¹ení byla svým pøístupem podobná autorskému.
xiii
