%%Page: 1 1 1 0 bop Black 0 TeXcolorgray Black Black Black Black 10800 5267 a @beginspecial 0 @llx 0 @lly 99 @urx 16 @ury 2880 @rwi @setspecial%%BeginDocument: logo129.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: logo128.eps %%Creator: fig2dev Version 3.2.3 Patchlevel %%CreationDate: Thu Nov 8 16:13:04 2001 %%For: pope@fry.research.att.com (Sue Pope) %%BoundingBox: 0 0 99 16 %%Magnification: 0.1500 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save newpath 0 16 moveto 0 0 lineto 99 0 lineto 99 16 lineto closepath clip newpath -12.0 26.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /DrawEllipse { /endangle exch def /startangle exch def /yrad exch def /xrad exch def /y exch def /x exch def /savematrix mtrx currentmatrix def x y tr xrad yrad sc 0 0 1 startangle endangle arc closepath savematrix setmatrix } def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin %%Page: 1 1 10 setmiterlimit 0.00900 0.00900 sc 7.500 slw % Ellipse n 2213 1988 856 856 0 360 DrawEllipse gs col4 1.00 shd ef gr gs col4 s gr % Ellipse n 2213 1991 813 813 0 360 DrawEllipse gs col8 1.00 shd ef gr gs col8 s gr % Ellipse n 1602 1879 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2001 2575 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2831 1877 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2618 1509 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 1806 1519 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2205 1364 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 1669 2290 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2762 2305 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2439 2579 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr % Ellipse n 2220 1992 440 440 0 360 DrawEllipse gs col4 1.00 shd ef gr gs col4 s gr % Ellipse n 2618 1509 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 1805 1515 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 1669 2290 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2205 1360 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2762 2305 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 1600 1875 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2439 2579 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2831 1877 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr % Ellipse n 2001 2573 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr /Times-Bold ff 225.00 scf sf 1997 2652 m gs 1 -1 sc (23) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 2438 2659 m gs 1 -1 sc (11) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Roman ff 480.00 scf sf 3375 2205 m gs 1 -1 sc (Article 03.4.1) col0 sh gr /Times-Roman ff 480.00 scf sf 3375 1650 m gs 1 -1 sc (Journal of Integer Sequences, Vol. 6 \(2003\),) col0 sh gr /Times-Bold ff 225.00 scf sf 2618 1592 m gs 1 -1 sc (2) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 2830 1956 m gs 1 -1 sc (3) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 2761 2386 m gs 1 -1 sc (6) dup sw pop 2 div neg 0 rm col0 sh gr % Ellipse n 1805 1517 42 42 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr % Polyline n 2554 1797 m 2554 1796 l 2554 1790 l 2554 1779 l 2554 1765 l 2553 1753 l 2552 1743 l 2550 1736 l 2548 1730 l 2544 1725 l 2540 1721 l 2534 1717 l 2528 1713 l 2521 1711 l 2514 1709 l 2507 1708 l 2499 1707 l 2492 1707 l 2483 1707 l 2474 1707 l 2465 1708 l 2456 1710 l 2447 1712 l 2438 1714 l 2431 1717 l 2423 1720 l 2416 1724 l 2408 1728 l 2401 1734 l 2394 1739 l 2388 1745 l 2382 1751 l 2377 1756 l 2372 1762 l 2368 1768 l 2363 1775 l 2359 1783 l 2356 1791 l 2352 1799 l 2350 1807 l 2348 1814 l 2346 1823 l 2345 1831 l 2345 1841 l 2345 1852 l 2346 1863 l 2349 1873 l 2352 1884 l 2356 1894 l 2360 1902 l 2365 1910 l 2371 1919 l 2378 1928 l 2385 1937 l 2393 1946 l 2401 1955 l 2409 1963 l 2417 1970 l 2425 1977 l 2435 1985 l 2446 1993 l 2457 2000 l 2467 2008 l 2477 2015 l 2487 2021 l 2494 2027 l 2501 2033 l 2506 2038 l 2510 2043 l 2513 2049 l 2515 2055 l 2516 2061 l 2516 2067 l 2516 2073 l 2514 2079 l 2510 2087 l 2505 2095 l 2498 2104 l 2490 2113 l 2481 2120 l 2473 2125 l 2465 2129 l 2458 2131 l 2449 2133 l 2440 2134 l 2431 2134 l 2422 2133 l 2414 2131 l 2406 2128 l 2396 2122 l 2385 2115 l 2375 2107 l 2366 2101 l 2359 2097 l 2353 2096 l 2350 2098 l 2347 2101 l 2346 2107 l 2344 2114 l 2344 2122 l 2344 2130 l 2345 2138 l 2346 2145 l 2347 2151 l 2349 2158 l 2352 2164 l 2355 2169 l 2360 2174 l 2364 2179 l 2370 2182 l 2375 2186 l 2382 2188 l 2390 2190 l 2399 2193 l 2409 2194 l 2419 2195 l 2429 2196 l 2438 2196 l 2448 2196 l 2456 2195 l 2465 2194 l 2475 2192 l 2484 2189 l 2493 2187 l 2501 2183 l 2509 2180 l 2516 2177 l 2524 2172 l 2533 2166 l 2541 2159 l 2548 2152 l 2555 2144 l 2560 2137 l 2565 2129 l 2569 2121 l 2573 2111 l 2576 2102 l 2579 2093 l 2581 2084 l 2583 2076 l 2584 2068 l 2584 2058 l 2584 2049 l 2583 2040 l 2582 2032 l 2580 2023 l 2577 2014 l 2572 2004 l 2568 1994 l 2563 1984 l 2558 1976 l 2552 1968 l 2546 1960 l 2538 1952 l 2531 1945 l 2524 1938 l 2517 1932 l 2509 1926 l 2501 1921 l 2493 1914 l 2484 1908 l 2476 1902 l 2468 1897 l 2461 1890 l 2453 1883 l 2445 1876 l 2437 1869 l 2431 1862 l 2427 1856 l 2423 1849 l 2420 1842 l 2418 1835 l 2417 1830 l 2417 1825 l 2417 1820 l 2417 1816 l 2418 1812 l 2419 1808 l 2419 1806 l 2420 1803 l 2421 1801 l 2422 1798 l 2424 1796 l 2425 1794 l 2427 1792 l 2429 1789 l 2431 1787 l 2433 1785 l 2436 1783 l 2437 1781 l 2439 1780 l 2442 1779 l 2444 1778 l 2446 1778 l 2448 1777 l 2450 1777 l 2452 1777 l 2455 1777 l 2457 1777 l 2460 1776 l 2462 1776 l 2465 1775 l 2468 1775 l 2470 1775 l 2473 1775 l 2476 1775 l 2479 1776 l 2482 1776 l 2484 1777 l 2487 1777 l 2489 1777 l 2492 1778 l 2495 1779 l 2498 1780 l 2502 1782 l 2506 1785 l 2510 1788 l 2514 1790 l 2517 1792 l 2520 1794 l 2522 1795 l 2524 1796 l 2525 1798 l 2527 1799 l 2529 1800 l 2531 1802 l 2534 1805 l 2536 1807 l 2539 1809 l 2540 1811 l 2542 1812 l 2544 1813 l 2546 1814 l 2547 1814 l 2549 1813 l 2550 1811 l 2552 1808 l 2554 1804 l 2555 1801 l 2556 1798 l 2556 1796 l 2557 1795 l 2557 1793 l 2557 1792 l gs 0.00 setgray ef gr gs col0 s gr % Polyline n 1871 1753 m 1902 1705 l 2090 1705 l 2075 1753 l 2075 2255 l 2012 2317 l 1933 2317 l 2012 2255 l 2012 1753 l 1871 1753 l 1918 1737 l cp gs 0.00 setgray ef gr gs col0 s gr % Polyline n 2169 1705 m 2278 1705 l 2263 1720 l 2247 1753 l 2247 2129 l 2278 2191 l 2152 2191 l 2169 2176 l 2185 2129 l 2185 2098 l 2185 1753 l cp gs 0.00 setgray ef gr gs col0 s gr % Ellipse n 1600 1877 42 42 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr /Times-Bold ff 225.00 scf sf 2197 1439 m gs 1 -1 sc (1) dup sw pop 2 div neg 0 rm col0 sh gr /Times-Bold ff 225.00 scf sf 1667 2376 m gs 1 -1 sc (47) dup sw pop 2 div neg 0 rm col0 sh gr $F2psEnd rs %%EndDocument @endspecial Black Black 14019 11461 a Fn(Tw)-60 b(o)717 b(Game-Set)g(Inequalities)22660 16603 y Fm(W)-130 b(alter)519 b(Sh)-43 b(ur)21349 18596 y(11)521 b(Middle)e(Road)17139 20588 y(P)-43 b(ort)520 b(W)-130 b(ashington,)520 b(NY)h(11050)25196 22581 y(USA)p 0 1 0 0 TeXcolorcmyk 19418 24573 a Fl(shur@optonline.net) p [[247 496 380 508] [1 1 1 [3 3]] [0 0 1]] (mailto:shur@optonline.net) pdfm Black Black Black 24133 29118 a Fk(Abstract)p Black Black 5870 31365 a Fj(Tw)-34 b(o)320 b(pla)-34 b(y)g(ers)319 b(comp)34 b(ete)318 b(in)h(a)f(con)-34 b(test)320 b(where)f(the)g (\257rst)g(pla)-34 b(y)g(er)319 b(to)g(win)g(a)g(sp)34 b(eci\257ed)318 b(n)-34 b(um)g(b)34 b(er)320 b(of)4052 32871 y(p)34 b(oin)-34 b(ts)366 b(wins)g(the)f(game,)373 b(and)366 b(the)g(\257rst)f(pla)-34 b(y)g(er)366 b(to)f(win)h(a)f(sp)34 b(eci\257ed)365 b(n)-34 b(um)g(b)34 b(er)366 b(of)g(games)f(wins)h(the) 4052 34376 y(set.)508 b(This)316 b(pap)34 b(er)314 b(pro)-34 b(v)g(es)315 b(t)-34 b(w)g(o)316 b(generalized)e(inequalities,)331 b(eac)-34 b(h)315 b(indep)34 b(enden)-34 b(t)316 b(of)f(the)g (probabilit)-34 b(y)4052 35882 y(of)295 b(winning)i(a)e(p)34 b(oin)-34 b(t,)318 b(concerning)295 b(the)g(b)34 b(etter)296 b(pla)-34 b(y)g(er's)295 b(c)-34 b(hances)295 b(of)h(winning.)503 b(Coun)-34 b(terexamples)4052 37387 y(are)291 b(giv)-34 b(en)291 b(for)g(t)-34 b(w)g(o)293 b(additional)f(conjectured)g (inequalities.)500 b(A)292 b(sequence)f(of)g(in)-34 b(tegers)292 b(whic)-34 b(h)292 b(pla)-34 b(ys)4052 38893 y(a)457 b(signi\257can)-34 b(t)459 b(role)d(in)i(this)g(pap)34 b(er)457 b(can)g(b)34 b(e)457 b(found)i(in)f(A033820)g(of)f(the)h (On-line)f(Encyclop)34 b(edia)4052 40398 y(of)404 b(In)-34 b(teger)404 b(Sequences.)800 44835 y Fn(1)2152 b(In)-60 b(tro)60 b(duction)800 47756 y Fi(A)473 b Fh(and)g Fi(B)540 b Fh(pla)-36 b(y)474 b(a)f(set)h(of)f(games.)698 b(The)473 b(winner)g(of)h(eac)-36 b(h)473 b(game)h(is)g(the)e(\257rst)h(pla)-36 b(y)g(er)473 b(to)g(win)h Fi(k)518 b Fh(p)36 b(oin)-36 b(ts,)800 49361 y(and)407 b(the)f(winner)h(of)h(the)f(set)g(is)g(the)g (\257rst)f(pla)-36 b(y)g(er)407 b(to)h(win)f Fi(n)h Fh(games.)570 b(The)407 b(probabilities)g(that)g Fi(A)g Fh(and)g Fi(B)800 50966 y Fh(win)397 b(eac)-36 b(h)397 b(p)36 b(oin)-36 b(t)396 b(are)i Fi(p)e Fh(and)h Fi(q)48 b Fh(,)403 b(resp)36 b(ectiv)-36 b(ely)-108 b(,)406 b(with)397 b Fi(p)295 b Fh(+)f Fi(q)417 b Fh(=)368 b(1)q(.)566 b(Let)396 b Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))398 b(and)f Fi(Q)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))398 b(b)36 b(e)397 b(the)800 52571 y(probabilities)305 b(that)f Fi(A)h Fh(wins)f(and)g(loses)i(the)e(set,)330 b(resp)36 b(ectiv)-36 b(ely)306 b(.)535 b(Let)304 b Fi(P)181 b Fh(\()p Fi(n;)221 b(p)p Fh(\))370 b(=)e Fi(P)181 b Fh(\()p Fi(n;)221 b Fh(1)p Fi(;)g(p)p Fh(\))371 b(=)e Fi(P)181 b Fh(\(1)p Fi(;)221 b(n;)g(p)p Fh(\))800 54176 y(and)491 b Fi(Q)p Fh(\()p Fi(n;)221 b(p)p Fh(\))370 b(=)e Fi(Q)p Fh(\()p Fi(n;)221 b Fh(1)p Fi(;)g(p)p Fh(\))371 b(=)e Fi(Q)p Fh(\(1)p Fi(;)221 b(n;)g(p)p Fh(\))493 b(b)36 b(e)491 b(the)h(probabilities)f(that)h Fi(A)f Fh(wins)h(and)f(loses)i (an)e Fi(n)h Fh(p)36 b(oin)-36 b(t)800 55781 y(game,)600 b(resp)36 b(ectiv)-36 b(ely)-108 b(.)977 b(\(Note)567 b(that)f Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))596 b(=)e Fi(P)181 b Fh(\()p Fi(n;)221 b(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\)\))567 b(and)f Fi(Q)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))596 b(=)f Fi(Q)p Fh(\()p Fi(n;)221 b(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\)\).)800 57386 y(This)434 b(pap)36 b(er)433 b(pro)-36 b(v)g(es)434 b(the)f(follo)-36 b(wing)435 b(t)-36 b(w)g(o)434 b(theorems:)p Black 800 60899 a Fg(Theorem)499 b(1.)p Black 554 w Ff(If)464 b Fi(n)370 b Fe(\270)f Fh(2)p Fi(;)687 b(k)414 b Fe(\270)369 b Fh(2)p Fi(;)465 b Ff(and)g Fi(:)p Fh(5)370 b Fi(<)e(p)h(<)g Fh(1)p Ff(,)465 b(then)f Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))370 b Fi(>)f(P)181 b Fh(\()p Fi(nk)45 b(;)221 b(p)p Fh(\))p Ff(.)p Black 800 65518 a Fg(Theorem)499 b(2.)p Black 554 w Ff(If)464 b Fh(2)369 b Fe(\267)h Fi(k)414 b(<)368 b(n)466 b Ff(and)e Fi(:)p Fh(5)370 b Fi(<)f(p)f(<)h Fh(1)p Ff(,)465 b(then)f Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))370 b Fi(>)f(P)181 b Fh(\()p Fi(k)45 b(;)221 b(n;)g(p)p Fh(\))p Ff(.)p Black 26475 74617 a Fh(1)p Black eop %%Page: 2 2 2 1 bop Black 0 TeXcolorgray Black Black 800 1424 a Fn(2)2152 b(Pro)60 b(ofs)p Black 800 5258 a Fg(Lemma)499 b(1.)p Black 554 w Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))369 b(=)13680 4735 y Fd(1)p 13680 4953 471 54 v 13680 5717 a(2)14579 5258 y Fh(+)16019 4735 y Fd(1)p 16019 4953 V 16019 5717 a(2)16622 5258 y Fh(\()p Fi(p)295 b Fe(\241)g Fi(q)48 b Fh(\))20857 3598 y Fc(k)24 b Fb(\241)p Fd(1)20756 3997 y Fa(X)20954 6796 y Fc(i)p Fd(=0)22896 3386 y Fa(\265)23873 4360 y Fh(2)p Fi(i)24199 6170 y(i)24968 3386 y Fa(\266)25945 5258 y Fh(\()p Fi(pq)48 b Fh(\))28235 4710 y Fc(i)28610 5258 y Fi(:)p Black 800 9069 a Ff(Pr)-66 b(o)g(of.)p Black 649 w Fh(W)-108 b(e)434 b(sho)-36 b(w)433 b(\257rst)g(that)12234 12711 y Fi(P)181 b Fh(\()p Fi(k)340 b Fh(+)295 b(1)p Fi(;)221 b(p)p Fh(\))295 b Fe(\241)h Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))369 b(=)25966 11812 y(1)p 25966 12405 651 54 v 25966 13622 a(2)26749 12711 y(\()p Fi(p)295 b Fe(\241)h Fi(q)48 b Fh(\))30663 10838 y Fa(\265)31640 11812 y Fh(2)p Fi(k)31965 13622 y(k)33011 10838 y Fa(\266)33989 12711 y Fh(\()p Fi(pq)g Fh(\))36279 12162 y Fc(k)36846 12711 y Fi(;)656 b(k)414 b Fe(\270)369 b Fh(1)p Fi(:)9772 b Fh(\(1\))2751 15799 y(The)425 b(only)h(\()p Fi(k)323 b Fh(+)277 b(1\)-p)36 b(oin)-36 b(t)425 b(games)g(in)g(whic)-36 b(h)425 b(the)g(winner)g (migh)-36 b(t)425 b(b)36 b(e)425 b(di\256eren)-36 b(t)423 b(than)i(the)f(winner)h(of)800 17404 y(the)433 b Fi(k)45 b Fh(-p)36 b(oin)-36 b(t)433 b(game)h(are)g(those)f(whic)-36 b(h)434 b(are)f(tied)h(at)f Fi(k)479 b Fh(p)36 b(oin)-36 b(ts)433 b(eac)-36 b(h.)2751 19009 y(The)474 b(increase)h(in)f Fi(A)p Fh('s)g(c)-36 b(hance)474 b(of)h(winning)f(a)h Fi(k)367 b Fh(+)323 b(1-p)36 b(oin)-36 b(t)473 b(game)i(o)-36 b(v)g(er)475 b(his)f(c)-36 b(hance)474 b(of)h(winning)f(a)800 20615 y Fi(k)45 b Fh(-p)36 b(oin)-36 b(t)484 b(game)h(is)g(the)f (excess)h(of)h(\(a\))e(the)g(probabilit)-36 b(y)485 b(that)f(there)g (is)h(a)g Fi(k)45 b Fh(-p)36 b(oin)-36 b(t)483 b(tie,)498 b Fi(B)552 b Fh(ha)-36 b(ving)485 b(w)-36 b(on)800 22220 y(the)381 b Fi(k)45 b Fh(-p)36 b(oin)-36 b(t)380 b(game,)393 b(and)381 b Fi(A)g Fh(wins)g(the)g(next)g(p)36 b(oin)-36 b(t,)392 b(o)-36 b(v)g(er)382 b(\(b\))e(the)h(probabilit)-36 b(y)381 b(that)g(there)g(is)g(a)h Fi(k)45 b Fh(-p)36 b(oin)-36 b(t)800 23825 y(tie,)456 b Fi(A)450 b Fh(ha)-36 b(ving)451 b(w)-36 b(on)451 b(the)f Fi(k)45 b Fh(-p)36 b(oin)-36 b(t)450 b(game,)456 b(and)451 b Fi(B)517 b Fh(wins)451 b(the)g(next)f(p)36 b(oin)-36 b(t.)630 b(Note)451 b(that)f(in)g(half)i(of)f(those)800 25430 y(tied)433 b(games,)i Fi(B)500 b Fh(w)-36 b(on)434 b(the)f Fi(k)45 b Fh(-p)36 b(oin)-36 b(t)433 b(game,)h(and)f(in)g(the)g(other)g(half,)i Fi(A)e Fh(w)-36 b(on)434 b(the)f Fi(k)45 b Fh(-p)36 b(oin)-36 b(t)432 b(game.)579 b(Since)800 25959 y Fa(\241)1409 26445 y Fd(2)p Fc(k)1644 27493 y(k)2393 25959 y Fa(\242)3002 27035 y Fh(\()p Fi(pq)48 b Fh(\))5292 26553 y Fc(k)6293 27035 y Fh(is)434 b(the)f(probabilit)-36 b(y)434 b(of)g(a)g Fi(k)45 b Fh(-p)36 b(oin)-36 b(t)433 b(tie,)h(\(1\))f(holds.)2751 28640 y(Lemma)591 b(1)f(is)h(true)f(since)h(it)g(is)g(true)f(for)h Fi(k)681 b Fh(=)636 b(1,)631 b(and)590 b(its)h(righ)-36 b(t)590 b(hand)g(side)g(simply)h(sums)g(the)800 30245 y(di\256erences)433 b(in)g(\(1\).)p 51860 31850 45 878 v 51905 31016 781 45 v 51905 31850 V 52684 31850 45 878 v Black 800 35476 a Fg(Lemma)499 b(2.)p Black 554 w Ff(L)-66 b(et)464 b Fi(a)10737 35675 y Fc(k)24 b(;i)12256 35476 y Fh(:=)14131 34577 y(1)p 14131 35171 651 54 v 14131 36387 a(2)14914 33603 y Fa(\265)15892 34577 y Fh(2)p Fi(k)16217 36387 y(k)17263 33603 y Fa(\266\265)19219 34577 y Fh(2)p Fi(i)19544 36387 y(i)20313 33603 y Fa(\266)22446 34577 y Fi(k)p 21423 35171 2767 54 v 21423 36387 a(k)341 b Fh(+)294 b Fi(i)24323 35476 y Ff(.)597 b(Then)465 b Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))p Fi(Q)p Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))369 b(=)g(\()p Fi(pq)48 b Fh(\))40732 34994 y Fc(k)41622 33816 y(k)24 b Fb(\241)p Fd(1)41521 34214 y Fa(X)41719 37014 y Fc(i)p Fd(=0)43661 35476 y Fi(a)44344 35675 y Fc(k)g(;i)45494 35476 y Fh(\()p Fi(pq)48 b Fh(\))47784 34928 y Fc(i)48159 35476 y Ff(,)2751 39969 y Fh(\(Note)467 b(that)g Fi(a)9968 40168 y Fc(k)24 b(;i)11586 39969 y Fh(is)468 b(equal)g(to)f Fi(a)18700 40168 y Fc(k)24 b Fd(+)p Fc(i)p Fb(\241)p Fd(1)p Fc(;k)g Fb(\241)p Fd(1)23968 39969 y Fh(in)467 b(A033820)j(of)e(the)f(On-line)f (Encyclop)36 b(edia)468 b(of)g(In)-36 b(teger)800 41574 y(Sequences.\))p Black 800 44176 a Ff(Pr)-66 b(o)g(of.)p Black 649 w Fh(W)-108 b(e)434 b(see)f(from)h(Lemma)g(1,)g(noting)g (that)f Fe(\241)p Fh(\()p Fi(p)295 b Fe(\241)g Fi(q)48 b Fh(\))30184 43693 y Fd(2)31078 44176 y Fh(=)369 b(4)p Fi(pq)342 b Fe(\241)296 b Fh(1,)434 b(that)11965 48520 y Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))p Fi(Q)p Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))370 b(=)21833 47621 y(1)p 21833 48214 651 54 v 21833 49431 a(4)22912 48520 y(+)24351 47621 y(1)p 24351 48214 V 24351 49431 a(4)25134 48520 y(\(4)p Fi(pq)343 b Fe(\241)295 b Fh(1\))30568 46248 y Fa(\303)31722 46859 y Fc(k)24 b Fb(\241)p Fd(1)31620 47258 y Fa(X)31818 50057 y Fc(i)p Fd(=0)33760 46647 y Fa(\265)34738 47621 y Fh(2)p Fi(i)35063 49431 y(i)35832 46647 y Fa(\266)36810 48520 y Fh(\()p Fi(pq)48 b Fh(\))39100 47971 y Fc(i)39475 46248 y Fa(!)40526 46462 y Fd(2)41273 48520 y Fi(:)9504 b Fh(\(2\))2751 51928 y(Since)12685 52312 y Fa(\303)14226 52923 y Fb(1)13737 53321 y Fa(X)13935 56121 y Fc(i)p Fd(=0)15877 52710 y Fa(\265)16855 53685 y Fh(2)p Fi(i)17180 55495 y(i)17949 52710 y Fa(\266)18927 54583 y Fh(\()p Fi(pq)48 b Fh(\))21217 54035 y Fc(i)21591 52312 y Fa(!)22643 52609 y Fd(2)23537 54583 y Fh(=)24918 52710 y Fa(\265)28358 53685 y Fh(1)p 26029 54278 5309 54 v 26029 54544 a Fe(p)p 27136 54544 4202 54 v 969 x Fh(1)295 b Fe(\241)h Fh(4)p Fi(pq)31470 52710 y Fa(\266)32448 53008 y Fd(2)33342 54583 y Fh(=)35212 52923 y Fb(1)34723 53321 y Fa(X)34921 56121 y Fc(i)p Fd(=0)36863 54583 y Fh(4)37513 54035 y Fc(i)37889 54583 y Fh(\()p Fi(pq)48 b Fh(\))40179 54035 y Fc(i)40554 54583 y Fi(;)800 58178 y Fh(w)-36 b(e)425 b(see)f(that)g(if)h(1)369 b Fe(\267)g Fi(t)g Fe(\267)g Fi(k)322 b Fe(\241)276 b Fh(1,)427 b(the)d(co)36 b(e\261cien)-36 b(t)424 b(of)h(\()p Fi(pq)48 b Fh(\))29251 57696 y Fc(t)30069 58178 y Fh(in)424 b(\(2\))h(equals)37733 57655 y Fd(1)p 37733 57872 471 54 v 37733 58636 a(4)38631 58178 y Fe(\242)295 b Fh(4)h Fe(\242)f Fh(4)41555 57696 y Fc(t)p Fb(\241)p Fd(1)43448 58178 y Fe(\241)44909 57655 y Fd(1)p 44909 57872 V 44909 58636 a(4)45808 58178 y Fe(\242)g Fh(4)47122 57696 y Fc(t)47886 58178 y Fh(=)369 b(0,)427 b(and)800 59783 y(equals)434 b(0)g(for)g Fi(t)369 b Fh(=)g(0)434 b(as)f(w)-36 b(ell.)2751 62988 y(Hence,)434 b(w)-36 b(e)434 b(can)f(de\257ne)g Fi(a)15718 63187 y Fc(k)24 b(;i)17302 62988 y Fh(suc)-36 b(h)432 b(that)16893 67112 y Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))p Fi(Q)p Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))370 b(=)e(\()p Fi(pq)48 b Fh(\))28918 66563 y Fc(k)29809 65451 y(k)24 b Fb(\241)p Fd(1)29707 65850 y Fa(X)29906 68649 y Fc(i)p Fd(=0)31848 67112 y Fi(a)32531 67311 y Fc(k)g(;i)33681 67112 y Fh(\()p Fi(pq)48 b Fh(\))35971 66563 y Fc(i)36345 67112 y Fi(:)14432 b Fh(\(3\))2751 70639 y(Th)-36 b(us,)433 b Fi(a)7090 70838 y Fc(k)24 b(;t)p Fb(\241)p Fc(k)9939 70639 y Fh(is)434 b(the)f(co)36 b(e\261cien)-36 b(t)434 b(of)g(\()p Fi(pq)48 b Fh(\))23328 70157 y Fc(t)24155 70639 y Fh(in)434 b(\(2\).)p Black 26475 74617 a(2)p Black eop %%Page: 3 3 3 2 bop Black 0 TeXcolorgray Black Black 800 1424 a Fh(W)-108 b(e)434 b(ha)-36 b(v)g(e,)434 b(then)4586 6657 y Fi(a)5269 6856 y Fc(k)24 b(;t)p Fb(\241)p Fc(k)8053 6657 y Fh(=)9950 4996 y Fc(k)g Fb(\241)p Fd(1)9849 5395 y Fa(X)9434 8223 y Fc(j)51 b Fd(=)p Fc(t)p Fb(\241)p Fc(k)12404 4784 y Fa(\265)13382 5758 y Fh(2)p Fi(j)13707 7568 y(j)14645 4784 y Fa(\266\265)16601 5758 y Fh(2)p Fi(t)295 b Fe(\241)g Fh(2)p Fi(j)371 b Fe(\241)295 b Fh(2)17251 7568 y Fi(t)g Fe(\241)g Fi(j)370 b Fe(\241)296 b Fh(1)22881 4784 y Fa(\266)24154 6657 y Fe(\241)25615 5758 y Fh(1)p 25615 6351 651 54 v 25615 7568 a(4)27737 4996 y Fc(k)24 b Fb(\241)p Fd(1)27636 5395 y Fa(X)26620 8223 y Fc(j)51 b Fd(=)p Fc(t)p Fb(\241)p Fc(k)24 b Fd(+1)30792 4784 y Fa(\265)31770 5758 y Fh(2)p Fi(j)32095 7568 y(j)33033 4784 y Fa(\266\265)34989 5758 y Fh(2)p Fi(t)295 b Fe(\241)g Fh(2)p Fi(j)35639 7568 y(t)g Fe(\241)g Fi(j)38996 4784 y Fa(\266)8053 13427 y Fh(=)9434 11554 y Fa(\265)10412 12529 y Fh(2)p Fi(t)g Fe(\241)g Fh(2)p Fi(k)11062 14339 y(t)g Fe(\241)g Fi(k)14527 11554 y Fa(\266\265)16482 12529 y Fh(2)p Fi(k)341 b Fe(\241)295 b Fh(2)16808 14339 y Fi(k)340 b Fe(\241)295 b Fh(1)20128 11554 y Fa(\266)21401 13427 y Fh(+)23825 11767 y Fc(k)24 b Fb(\241)p Fd(1)23724 12165 y Fa(X)22708 14994 y Fc(j)51 b Fd(=)p Fc(t)p Fb(\241)p Fc(k)24 b Fd(+1)26880 11554 y Fa(\265)27858 12529 y Fh(2)p Fi(j)28183 14339 y(j)29121 11554 y Fa(\266)221 b(\265\265)32276 12529 y Fh(2)p Fi(t)295 b Fe(\241)g Fh(2)p Fi(j)371 b Fe(\241)295 b Fh(2)32926 14339 y Fi(t)g Fe(\241)g Fi(j)370 b Fe(\241)296 b Fh(1)38556 11554 y Fa(\266)39829 13427 y Fe(\241)41290 12529 y Fh(1)p 41290 13122 V 41290 14339 a(4)42074 11554 y Fa(\265)43051 12529 y Fh(2)p Fi(t)g Fe(\241)f Fh(2)p Fi(j)43702 14339 y(t)g Fe(\241)g Fi(j)47058 11554 y Fa(\266\266)8053 20198 y Fh(=)9434 18325 y Fa(\265)10412 19300 y Fh(2)p Fi(t)g Fe(\241)g Fh(2)p Fi(k)11062 21110 y(t)g Fe(\241)g Fi(k)14527 18325 y Fa(\266\265)16482 19300 y Fh(2)p Fi(k)341 b Fe(\241)295 b Fh(2)16808 21110 y Fi(k)340 b Fe(\241)295 b Fh(1)20128 18325 y Fa(\266)21401 20198 y Fh(+)22840 19300 y(1)p 22840 19893 V 22840 21110 a(2)24962 18538 y Fc(k)24 b Fb(\241)p Fd(1)24861 18936 y Fa(X)23845 21765 y Fc(j)51 b Fd(=)p Fc(t)p Fb(\241)p Fc(k)24 b Fd(+1)28017 18325 y Fa(\265)28995 19300 y Fh(2)p Fi(j)29320 21110 y(j)30258 18325 y Fa(\266\265)32214 19300 y Fh(2)p Fi(t)295 b Fe(\241)g Fh(2)p Fi(j)371 b Fe(\241)295 b Fh(2)32864 21110 y Fi(t)g Fe(\241)g Fi(j)370 b Fe(\241)296 b Fh(1)38494 18325 y Fa(\266)40633 19300 y Fh(1)p 39605 19893 2707 54 v 39605 21110 a Fi(t)f Fe(\241)g Fi(j)42444 20198 y(:)3200 b Fh(\(4\))15329 25723 y(Let)433 b Fi(g)48 b Fh(\()p Fi(t;)221 b(j)75 b Fh(\))368 b(=)22889 24575 y Fi(j)75 b Fh(\(2)p Fi(t)294 b Fe(\241)i Fh(2)p Fi(j)370 b Fe(\241)295 b Fh(1\))30793 23499 y Fa(\241)31402 23986 y Fd(2)p Fc(j)31638 25033 y(j)32304 23499 y Fa(\242\241)33522 23986 y Fd(2)p Fc(t)p Fb(\241)p Fd(2)p Fc(j)51 b Fb(\241)p Fd(2)33993 25033 y Fc(t)p Fb(\241)p Fc(j)g Fb(\241)p Fd(1)37168 23499 y Fa(\242)p 22889 25418 14889 54 v 28239 26634 a Fh(\()p Fi(t)295 b Fe(\241)g Fi(j)75 b Fh(\))p Fi(t)37910 25723 y(:)2751 28625 y Fh(W)-108 b(e)434 b(sho)-36 b(w)433 b(that)13427 29897 y Fa(\265)14404 30872 y Fh(2)p Fi(j)14730 32681 y(j)15668 29897 y Fa(\266)o(\265)17623 30872 y Fh(2)p Fi(t)295 b Fe(\241)h Fh(2)p Fi(j)370 b Fe(\241)296 b Fh(2)18274 32681 y Fi(t)e Fe(\241)i Fi(j)370 b Fe(\241)295 b Fh(1)23904 29897 y Fa(\266)26042 30872 y Fh(1)p 25015 31465 2707 54 v 25015 32681 a Fi(t)f Fe(\241)i Fi(j)28222 31770 y Fh(=)369 b Fi(g)48 b Fh(\()p Fi(t;)221 b(j)370 b Fh(+)294 b(1\))i Fe(\241)f Fi(g)48 b Fh(\()p Fi(t;)221 b(j)75 b Fh(\))10964 b(\(5\))800 35426 y(b)-36 b(y)434 b(dividing)g(b)36 b(oth)433 b(sides)g(of)h(the)f(equation)i(b)-36 b(y)24660 34350 y Fa(\241)25269 34837 y Fd(2)p Fc(j)25504 35884 y(j)26171 34350 y Fa(\242\241)27389 34837 y Fd(2)p Fc(t)p Fb(\241)p Fd(2)p Fc(j)51 b Fb(\241)p Fd(2)27859 35884 y Fc(t)p Fb(\241)p Fc(j)g Fb(\241)p Fd(1)31035 34350 y Fa(\242)32077 35426 y Fh(to)434 b(obtain)16271 38272 y(1)p 15243 38865 V 15243 40081 a Fi(t)295 b Fe(\241)g Fi(j)18451 39170 y Fh(=)19965 38272 y(1)g(+)g(2)p Fi(j)p 19965 38865 3516 54 v 21487 40081 a(t)23908 39170 y Fe(\241)25369 38272 y Fi(j)75 b Fh(\(2)p Fi(t)295 b Fe(\241)g Fh(2)p Fi(j)371 b Fe(\241)295 b Fh(1\))p 25369 38865 7906 54 v 27228 40081 a(\()p Fi(t)g Fe(\241)g Fi(j)75 b Fh(\))p Fi(t)33776 39170 y Fh(=)36317 38272 y(1)p 35290 38865 2707 54 v 35290 40081 a Fi(t)294 b Fe(\241)i Fi(j)38128 39170 y(:)2751 42629 y Fh(Let)528 b Fi(S)77 b Fh(\()p Fi(t;)221 b(k)45 b Fh(\))528 b(equal)h(the)f(sum)f(in)h(\(4\).)862 b(By)529 b(summing)f(b)36 b(oth)527 b(sides)h(of)h(\(5\))f(from)h Fi(j)444 b Fh(=)368 b Fi(t)295 b Fe(\241)g Fi(k)341 b Fh(+)294 b(1)529 b(to)800 44234 y Fi(k)340 b Fe(\241)296 b Fh(1,)434 b(w)-36 b(e)434 b(see)f(that)h Fi(S)77 b Fh(\()p Fi(t;)221 b(k)45 b Fh(\))433 b(is)h(equal)h(to)e Fi(g)48 b Fh(\()p Fi(t;)221 b(k)45 b Fh(\))295 b Fe(\241)g Fi(g)48 b Fh(\()p Fi(t;)221 b(t)295 b Fe(\241)g Fi(k)340 b Fh(+)295 b(1\),)434 b(and)f(w)-36 b(e)434 b(ha)-36 b(v)g(e)5442 48058 y Fi(S)77 b Fh(\()p Fi(t;)221 b(k)45 b Fh(\))369 b(=)10987 46989 y Fi(k)45 b Fh(\(2)p Fi(t)295 b Fe(\241)g Fh(2)p Fi(k)341 b Fe(\241)295 b Fh(1\))19108 45914 y Fa(\241)19717 46400 y Fd(2)p Fc(k)19952 47448 y(k)20701 45914 y Fa(\242\241)21919 46400 y Fd(2)p Fc(t)p Fb(\241)p Fd(2)p Fc(k)24 b Fb(\241)p Fd(2)22389 47448 y Fc(t)p Fb(\241)p Fc(k)g Fb(\241)p Fd(1)25647 45914 y Fa(\242)p 10987 47752 15270 54 v 16474 48969 a Fh(\()p Fi(t)294 b Fe(\241)i Fi(k)45 b Fh(\))p Fi(t)26684 48058 y Fe(\241)28145 46989 y Fh(\()p Fi(t)295 b Fe(\241)g Fi(k)340 b Fh(+)295 b(1\)\(2)p Fi(k)341 b Fe(\241)295 b Fh(3\))38880 45914 y Fa(\241)39489 46400 y Fd(2)p Fc(t)p Fb(\241)p Fd(2)p Fc(k)24 b Fd(+2)39960 47448 y Fc(t)p Fb(\241)p Fc(k)g Fd(+1)43218 45914 y Fa(\242)o(\241)44435 46400 y Fd(2)p Fc(k)g Fb(\241)p Fd(4)44670 47448 y Fc(k)g Fb(\241)p Fd(2)46621 45914 y Fa(\242)p 28145 47752 19086 54 v 35450 48969 a Fh(\()p Fi(k)340 b Fe(\241)295 b Fh(1\))p Fi(t)47363 48058 y(:)2751 51516 y Fh(W)-108 b(e)434 b(see)f(from)h (\(4\))g(that)15270 54994 y Fi(a)15953 55193 y Fc(k)24 b(;t)p Fb(\241)p Fc(k)18737 54994 y Fh(=)20117 53121 y Fa(\265)21095 54095 y Fh(2)p Fi(t)295 b Fe(\241)h Fh(2)p Fi(k)21746 55905 y(t)e Fe(\241)i Fi(k)25210 53121 y Fa(\266\265)27166 54095 y Fh(2)p Fi(k)340 b Fe(\241)296 b Fh(2)27491 55905 y Fi(k)340 b Fe(\241)296 b Fh(1)30811 53121 y Fa(\266)32084 54994 y Fh(+)33524 54095 y(1)p 33524 54688 651 54 v 33524 55905 a(2)34307 54994 y Fi(S)77 b Fh(\()p Fi(t;)221 b(k)45 b Fh(\))p Fi(:)800 58679 y Fh(Dividing)435 b(b)36 b(oth)433 b(sides)g(b)-36 b(y)14092 57603 y Fa(\241)14701 58090 y Fd(2)p Fc(k)14936 59137 y(k)15685 57603 y Fa(\242\241)16902 58090 y Fd(2)p Fc(t)p Fb(\241)p Fd(2)p Fc(k)17373 59137 y(t)p Fb(\241)p Fc(k)19428 57603 y Fa(\242)20037 58679 y Fh(,)434 b(w)-36 b(e)434 b(ha)-36 b(v)g(e)12638 61476 y Fi(a)13321 61675 y Fc(k)24 b(;t)p Fb(\241)p Fc(k)p 11214 62069 5946 54 v 11214 62357 a Fa(\241)11823 62843 y Fd(2)p Fc(k)12058 63891 y(k)12807 62357 y Fa(\242\241)14024 62843 y Fd(2)p Fc(t)p Fb(\241)p Fd(2)p Fc(k)14495 63891 y(t)p Fb(\241)p Fc(k)16550 62357 y Fa(\242)17661 62375 y Fh(=)20637 61476 y Fi(k)p 19175 62069 3646 54 v 19175 63286 a Fh(4)p Fi(k)340 b Fe(\241)295 b Fh(2)23248 62375 y(+)24687 61476 y(1)p 24687 62069 651 54 v 24687 63286 a(2)25692 60502 y Fa(\265)27002 61476 y Fi(k)p 26803 62069 1121 54 v 26803 63286 a Fh(2)p Fi(t)28351 62375 y Fe(\241)29812 61476 y Fi(k)45 b Fh(\(2)p Fi(t)295 b Fe(\241)g Fh(2)p Fi(k)341 b Fh(+)295 b(1\))p 29812 62069 8100 54 v 30973 63286 a(2\(2)p Fi(k)341 b Fe(\241)295 b Fh(1\))p Fi(t)38045 60502 y Fa(\266)39391 62375 y Fh(=)41104 61476 y Fi(k)p 40905 62069 1121 54 v 40905 63286 a Fh(2)p Fi(t)42158 62375 y(:)800 66125 y Fh(Replacing)434 b Fi(t)g Fh(b)-36 b(y)433 b Fi(k)340 b Fh(+)295 b Fi(i)433 b Fh(giv)-36 b(es)19665 68420 y Fi(a)20348 68619 y Fc(k)24 b(;i)21868 68420 y Fh(=)23381 67521 y(1)p 23381 68114 651 54 v 23381 69331 a(2)24164 66547 y Fa(\265)25142 67521 y Fh(2)p Fi(k)25467 69331 y(k)26514 66547 y Fa(\266)o(\265)28469 67521 y Fh(2)p Fi(i)28794 69331 y(i)29563 66547 y Fa(\266)31697 67521 y Fi(k)p 30674 68114 2767 54 v 30674 69331 a(k)340 b Fh(+)295 b Fi(i)33573 68420 y(:)p 51860 71296 45 878 v 51905 70462 781 45 v 51905 71296 V 52684 71296 45 878 v Black 26475 74617 a Fh(3)p Black eop %%Page: 4 4 4 3 bop Black 0 TeXcolorgray Black Black Black 800 1424 a Fg(Lemma)499 b(3.)p Black 5822 4789 a Fi(P)6841 4241 y Fb(0)7151 4789 y Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))369 b(=)12002 3891 y(1)p 12002 4484 651 54 v 12002 5700 a(2)12785 4789 y Fi(k)13506 2916 y Fa(\265)14484 3891 y Fh(2)p Fi(k)14809 5700 y(k)15855 2916 y Fa(\266)16833 4789 y Fh(\()p Fi(pq)48 b Fh(\))19123 4241 y Fc(k)24 b Fb(\241)p Fd(1)20893 4789 y Fi(;)221 b Ff(wher)-66 b(e)465 b(the)g(derivative)e (is)i(taken)f(with)g(r)-66 b(esp)g(e)g(ct)464 b(to)g Fi(p:)p Black 800 8587 a Ff(Pr)-66 b(o)g(of.)p Black 649 w Fh(The)434 b(probabilit)-36 b(y)434 b(that)f Fi(A)g Fh(wins)h(a)g Fi(k)45 b Fh(-p)36 b(oin)-36 b(t)433 b(game)h(on)f(the)g (\()p Fi(k)341 b Fh(+)294 b Fi(i)p Fh(\))38246 8105 y Fc(th)39617 8587 y Fh(p)36 b(oin)-36 b(t)433 b(pla)-36 b(y)g(ed)434 b(is)20353 12285 y Fi(p)21006 11736 y Fc(k)21575 10412 y Fa(\265)22553 11386 y Fi(k)340 b Fe(\241)296 b Fh(1)f(+)g Fi(i)24851 13196 y(i)27594 10412 y Fa(\266)28571 12285 y Fh(\(1)h Fe(\241)f Fi(p)p Fh(\))32510 11736 y Fc(i)32885 12285 y Fi(:)800 15893 y Fh(Hence,)4462 19999 y Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))369 b(=)g Fi(p)10852 19450 y Fc(k)11744 18338 y(k)24 b Fb(\241)p Fd(1)11642 18737 y Fa(X)11840 21536 y Fc(i)p Fd(=0)13782 18126 y Fa(\265)14760 19100 y Fi(k)340 b Fe(\241)296 b Fh(1)f(+)g Fi(i)17059 20910 y(i)19801 18126 y Fa(\266)20779 19999 y Fh(\(1)g Fe(\241)g Fi(p)p Fh(\))24717 19450 y Fc(i)25461 19999 y Fh(=)369 b Fi(p)27495 19450 y Fc(k)28387 18338 y(k)24 b Fb(\241)p Fd(1)28285 18737 y Fa(X)28428 21536 y Fc(j)51 b Fd(=0)30204 19999 y Fh(\()p Fe(\241)p Fh(1\))32899 19450 y Fc(j)33607 17727 y Fa(\303)34760 18338 y Fc(k)24 b Fb(\241)p Fd(1)34659 18737 y Fa(X)34876 21536 y Fc(i)p Fd(=)p Fc(j)36799 18126 y Fa(\265)37861 19100 y Fi(i)37777 20910 y(j)38390 18126 y Fa(\266\265)40345 19100 y Fi(k)341 b Fe(\241)295 b Fh(1)g(+)g Fi(i)42644 20910 y(i)45386 18126 y Fa(\266)46364 17727 y(!)47637 19999 y Fi(p)48290 19450 y Fc(j)48776 19999 y Fi(:)2751 24203 y Fh(W)-108 b(e)434 b(ha)-36 b(v)g(e)4765 27995 y Fc(k)24 b Fb(\241)p Fd(1)4664 28393 y Fa(X)4881 31193 y Fc(i)p Fd(=)p Fc(j)6804 27782 y Fa(\265)7866 28757 y Fi(i)7782 30566 y(j)8395 27782 y Fa(\266\265)10350 28757 y Fi(k)341 b Fe(\241)295 b Fh(1)h(+)e Fi(i)12649 30566 y(i)15391 27782 y Fa(\266)16738 29655 y Fh(=)18220 27995 y Fc(k)24 b Fb(\241)p Fd(1)18118 28393 y Fa(X)18336 31193 y Fc(i)p Fd(=)p Fc(j)20259 27782 y Fa(\265)21236 28757 y Fi(k)341 b Fe(\241)295 b Fh(1)g(+)g Fi(i)22417 30566 y(i)g Fe(\241)g Fi(j)26277 27782 y Fa(\266\265)28233 28757 y Fi(k)340 b Fe(\241)295 b Fh(1)h(+)f Fi(j)30531 30566 y(j)33442 27782 y Fa(\266)34789 29655 y Fh(=)36170 27782 y Fa(\265)37148 28757 y Fi(k)340 b Fe(\241)295 b Fh(1)h(+)f Fi(j)39446 30566 y(j)42357 27782 y Fa(\266\265)44313 28757 y Fh(2)p Fi(k)341 b Fe(\241)295 b Fh(1)44668 30566 y Fi(k)340 b Fh(+)295 b Fi(j)47958 27782 y Fa(\266)16738 35914 y Fh(=)19359 35016 y Fi(k)p 18251 35609 2936 54 v 18251 36826 a(k)341 b Fh(+)294 b Fi(j)21320 34041 y Fa(\265)22298 35016 y Fi(k)340 b Fh(+)295 b Fi(j)23459 36826 y(j)25234 34041 y Fa(\266\265)27189 35016 y Fh(2)p Fi(k)341 b Fe(\241)295 b Fh(1)27544 36826 y Fi(k)340 b Fh(+)295 b Fi(j)30835 34041 y Fa(\266)32181 35914 y Fh(=)33695 35016 y(1)p 33695 35609 651 54 v 33695 36826 a(2)34478 34041 y Fa(\265)35456 35016 y Fh(2)p Fi(k)35781 36826 y(k)36827 34041 y Fa(\266\265)38783 35016 y Fi(k)340 b Fe(\241)295 b Fh(1)39974 36826 y Fi(j)41778 34041 y Fa(\266)43996 35016 y Fi(k)p 42888 35609 2936 54 v 42888 36826 a(k)341 b Fh(+)294 b Fi(j)45957 35914 y(:)2751 40323 y Fh(Hence,)13339 43100 y Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))369 b(=)19209 42202 y(1)p 19209 42795 651 54 v 19209 44012 a(2)19992 43100 y Fi(k)20713 41227 y Fa(\265)21691 42202 y Fh(2)p Fi(k)22016 44012 y(k)23062 41227 y Fa(\266)24363 41440 y Fc(k)24 b Fb(\241)p Fd(1)24262 41839 y Fa(X)24404 44638 y Fc(j)51 b Fd(=0)26180 43100 y Fh(\()p Fe(\241)p Fh(1\))28875 42552 y Fc(j)29362 41227 y Fa(\265)30340 42202 y Fi(k)340 b Fe(\241)296 b Fh(1)31531 44012 y Fi(j)33335 41227 y Fa(\266)35588 42202 y Fh(1)p 34446 42795 2936 54 v 34446 44012 a Fi(k)340 b Fh(+)295 b Fi(j)37514 43100 y(p)38167 42552 y Fc(k)24 b Fd(+)p Fc(j)39899 43100 y Fi(:)2751 46696 y Fh(T)-108 b(aking)435 b(the)e(deriv)-72 b(ativ)-36 b(e)434 b(with)g(resp)36 b(ect)433 b(to)g Fi(p)p Fh(,)h(w)-36 b(e)434 b(ha)-36 b(v)g(e)8797 50820 y Fi(P)9816 50271 y Fb(0)10126 50820 y Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))370 b(=)14977 49921 y(1)p 14977 50514 651 54 v 14977 51731 a(2)15760 50820 y Fi(k)16481 48947 y Fa(\265)17459 49921 y Fh(2)p Fi(k)17784 51731 y(k)18830 48947 y Fa(\266)20131 49159 y Fc(k)24 b Fb(\241)p Fd(1)20030 49558 y Fa(X)20172 52357 y Fc(j)51 b Fd(=0)21948 50820 y Fh(\()p Fe(\241)p Fh(1\))24643 50271 y Fc(j)25130 48947 y Fa(\265)26108 49921 y Fi(k)340 b Fe(\241)296 b Fh(1)27299 51731 y Fi(j)29103 48947 y Fa(\266)30081 50820 y Fi(p)30734 50271 y Fc(k)24 b Fd(+)p Fc(j)51 b Fb(\241)p Fd(1)34037 50820 y Fh(=)35551 49921 y(1)p 35551 50514 V 35551 51731 a(2)36334 50820 y Fi(k)37055 48947 y Fa(\265)38033 49921 y Fh(2)p Fi(k)38358 51731 y(k)39404 48947 y Fa(\266)40382 50820 y Fh(\()p Fi(pq)d Fh(\))42672 50271 y Fc(k)24 b Fb(\241)p Fd(1)44442 50820 y Fi(:)p 51860 54370 45 878 v 51905 53537 781 45 v 51905 54370 V 52684 54370 45 878 v Black 800 57082 a Fg(Lemma)499 b(4.)p Black 554 w Ff(The)465 b(function)21138 59346 y Fi(r)21724 59545 y Fc(n;k)23125 59346 y Fh(\()p Fi(p)p Fh(\))369 b(=)26672 58448 y Fi(P)27691 57966 y Fb(0)28002 58448 y Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))p 26672 59041 5657 54 v 26964 60257 a Fi(P)27983 59874 y Fb(0)28293 60257 y Fh(\()p Fi(nk)45 b(;)221 b(p)p Fh(\))800 62342 y Ff(is)465 b(a)g(de)-66 b(cr)g(e)g(asing)462 b(function)i(of)g Fi(p)p Ff(,)g(for)h Fi(:)p Fh(5)370 b Fe(\267)f Fi(p)g(<)f Fh(1)p Ff(.)p Black 26475 74617 a Fh(4)p Black eop %%Page: 5 5 5 4 bop Black 0 TeXcolorgray Black Black Black 800 1424 a Ff(Pr)-66 b(o)g(of.)p Black 6517 5016 a Fi(r)7103 5215 y Fc(n;k)8505 5016 y Fh(\()p Fi(p)p Fh(\))368 b(=)12051 4118 y Fi(P)13070 3636 y Fb(0)13381 4118 y Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))p 12051 4711 5657 54 v 12343 5928 a Fi(P)13362 5544 y Fb(0)13672 5928 y Fh(\()p Fi(nk)45 b(;)221 b(p)p Fh(\))18210 5016 y(=)19723 4118 y Fi(P)20742 3636 y Fb(0)21053 4118 y Fh(\()p Fi(n;)g(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\)\))p 19723 4711 7688 54 v 21030 5928 a Fi(P)22049 5544 y Fb(0)22360 5928 y Fh(\()p Fi(nk)45 b(;)221 b(p)p Fh(\))10538 10950 y(=)12184 9444 y Fd(1)p 12184 9661 471 54 v 12184 10425 a(2)12787 9967 y Fi(n)13563 8891 y Fa(\241)14173 9377 y Fd(2)p Fc(n)14408 10425 y(n)15214 8891 y Fa(\242)16044 9967 y Fh(\()p Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))p Fi(Q)p Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\)\))25041 9321 y Fc(n)p Fb(\241)p Fd(1)27224 9444 y(1)p 27224 9661 V 27224 10425 a(2)27828 9967 y Fi(k)28549 8891 y Fa(\241)29157 9377 y Fd(2)p Fc(k)29393 10425 y(k)30141 8891 y Fa(\242)30750 9967 y Fh(\()p Fi(pq)48 b Fh(\))33040 9485 y Fc(k)24 b Fb(\241)p Fd(1)p 12051 10644 22759 54 v 18745 11485 a(1)p 18745 11702 471 54 v 18745 12466 a(2)19348 12008 y Fi(nk)20845 10932 y Fa(\241)21455 11419 y Fd(2)p Fc(nk)21690 12466 y(nk)23010 10932 y Fa(\242)23618 12008 y Fh(\()p Fi(pq)48 b Fh(\))25908 11624 y Fc(nk)24 b Fb(\241)p Fd(1)10538 17163 y Fh(=)12051 16264 y(1)p 12051 16857 651 54 v 12051 18074 a(2)12967 15104 y Fa(\241)13576 15591 y Fd(2)p Fc(n)13811 16638 y(n)14618 15104 y Fa(\242)o(\241)15835 15591 y Fd(2)p Fc(k)16070 16638 y(k)16819 15104 y Fa(\242)17649 16180 y Fh(\()p Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))p Fi(Q)p Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\)\))26647 15534 y Fc(n)p Fb(\241)p Fd(1)p 12967 16857 15508 54 v 16654 17145 a Fa(\241)17262 17632 y Fd(2)p Fc(nk)17498 18679 y(nk)18817 17145 y Fa(\242)19426 18221 y Fh(\()p Fi(pq)48 b Fh(\))21716 17837 y Fc(k)24 b Fd(\()p Fc(n)p Fb(\241)p Fd(1\))28608 17163 y Fi(;)6255 b(:)p Fh(5)370 b Fe(\267)f Fi(p)g(<)f Fh(1)p Fi(:)4001 b Fh(\(6\))2751 21048 y(Substituting)432 b(from)i(Lemma)f(2,)i(w)-36 b(e)433 b(ha)-36 b(v)g(e)15591 25392 y Fi(r)16177 25591 y Fc(n;k)17579 25392 y Fh(\()p Fi(p)p Fh(\))368 b(=)21125 24493 y(1)p 21125 25086 651 54 v 21125 26303 a(2)22041 23333 y Fa(\241)22650 23819 y Fd(2)p Fc(n)22886 24867 y(n)23692 23333 y Fa(\242)o(\241)24909 23819 y Fd(2)p Fc(k)25145 24867 y(k)25893 23333 y Fa(\242)p 22041 25086 4461 54 v 22886 25374 a(\241)23494 25861 y Fd(2)p Fc(nk)23730 26908 y(nk)25049 25374 y Fa(\242)26856 23120 y(\303)28009 23731 y Fc(k)24 b Fb(\241)p Fd(1)27908 24130 y Fa(X)28106 26929 y Fc(i)p Fd(=0)30048 25392 y Fi(a)30731 25591 y Fc(k)g(;i)31881 25392 y Fh(\()p Fi(pq)48 b Fh(\))34171 24843 y Fc(i)34546 23120 y Fa(!)35598 23334 y Fc(n)p Fb(\241)p Fd(1)37647 25392 y Fi(;)800 29819 y Fh(where)434 b Fi(a)5241 30018 y Fc(k)24 b(;i)6760 29819 y Fh(=)8273 28920 y(1)p 8273 29513 651 54 v 8273 30730 a(2)9056 27946 y Fa(\265)10034 28920 y Fh(2)p Fi(k)10359 30730 y(k)11406 27946 y Fa(\266)o(\265)13361 28920 y Fh(2)p Fi(i)13686 30730 y(i)14455 27946 y Fa(\266)16589 28920 y Fi(k)p 15566 29513 2767 54 v 15566 30730 a(k)340 b Fh(+)295 b Fi(i)18466 29819 y(:)2751 33787 y Fh(Since)430 b Fi(a)6827 33986 y Fc(k)24 b(;i)8346 33787 y Fi(>)369 b Fh(0,)432 b(and)d Fi(pq)478 b Fh(is)431 b(a)f(decreasing)h(function)f(of)h Fi(p)p Fh(,)g(it)f(follo)-36 b(ws)433 b(that)c Fi(r)41058 33986 y Fc(n;k)42460 33787 y Fh(\()p Fi(p)p Fh(\))h(is)g(a)h (decreasing)800 35392 y(function)i(of)i Fi(p)p Fh(.)p 51860 36998 45 878 v 51905 36164 781 45 v 51905 36998 V 52684 36998 45 878 v Black 800 39710 a Fg(Lemma)499 b(5.)p Black 554 w Ff(If)464 b Fh(2)369 b Fe(\267)g Fi(t)g Fe(\267)g Fi(m)p Ff(,)464 b(then)20427 43635 y Fh(4)21077 43087 y Fc(t)21605 41491 y Fa(\241)22214 41978 y Fd(2)p Fc(m)p Fb(\241)p Fd(2)p Fc(t)22684 43025 y(m)p Fb(\241)p Fc(t)25059 41491 y Fa(\242)p 21605 43330 4063 54 v 22376 43574 a(\241)22985 44060 y Fd(2)p Fc(m)23220 45108 y(m)24288 43574 y Fa(\242)25933 42737 y Fh(2)p Fi(m)295 b Fe(\241)h Fi(t)p 25933 43330 3882 54 v 27305 44547 a(m)30316 43635 y(>)369 b Fh(2)465 b Fi(:)p Black 800 47476 a Ff(Pr)-66 b(o)g(of.)p Black 649 w Fh(F)-108 b(or)433 b Fi(t)369 b Fh(=)g(2,)434 b(the)f(left)h(hand)f(side)g(of)h(Lemma)g(5)g(reduces)f (to)16793 50226 y(8\()p Fi(m)295 b Fe(\241)g Fh(1\))21866 49744 y Fd(2)p 14519 50819 10148 54 v 14519 52036 a Fh(\(2)p Fi(m)g Fe(\241)h Fh(1\)\(2)p Fi(m)f Fe(\241)g Fh(3\))25168 51125 y(=)369 b(2)295 b(+)33682 50226 y(2)p 28934 50819 V 28934 52036 a(\(2)p Fi(m)g Fe(\241)g Fh(1\)\(2)p Fi(m)g Fe(\241)h Fh(3\))800 54729 y(whic)-36 b(h)523 b(is)h(clearly)g(greater) g(than)f(2)g(when)g Fi(m)e Fe(\270)h Fh(2.)848 b(W)-108 b(e)523 b(sho)-36 b(w)524 b(b)-36 b(y)523 b(induction)g(that)f(Lemma)i (5)f(holds)800 56335 y(for)489 b(all)g Fi(t)p Fh(.)743 b(Supp)36 b(ose)487 b(it)i(is)f(true)g(for)h(some)g Fi(t)p Fh(,)502 b(and)488 b(consider)g(the)g(left)h(hand)e(side)i(of)g(Lemma)f (5)h(with)f Fi(t)800 57940 y Fh(replaced)433 b(b)-36 b(y)434 b Fi(t)295 b Fh(+)g(1.)578 b(W)-108 b(e)434 b(ha)-36 b(v)g(e,)2444 63308 y(4)3094 62760 y Fc(t)p Fd(+1)4825 61164 y Fa(\241)5433 61651 y Fd(2)p Fc(m)p Fb(\241)p Fd(2)p Fc(t)p Fb(\241)p Fd(2)5904 62698 y Fc(m)p Fb(\241)p Fc(t)p Fb(\241)p Fd(1)9480 61164 y Fa(\242)p 4825 63003 5265 54 v 6197 63246 a(\241)6806 63733 y Fd(2)p Fc(m)7041 64780 y(m)8108 63246 y Fa(\242)10355 62410 y Fh(2)p Fi(m)295 b Fe(\241)h Fi(t)e Fe(\241)i Fh(1)p 10355 63003 6156 54 v 12864 64220 a Fi(m)17012 63308 y Fh(=)369 b(4)19264 61037 y Fa(\303)20316 63308 y Fh(4)20966 62760 y Fc(t)21494 61164 y Fa(\241)22103 61651 y Fd(2)p Fc(m)p Fb(\241)p Fd(2)p Fc(t)22573 62698 y(m)p Fb(\241)p Fc(t)24948 61164 y Fa(\242)p 21494 63003 4063 54 v 22265 63246 a(\241)22874 63733 y Fd(2)p Fc(m)23109 64780 y(m)24177 63246 y Fa(\242)25822 62410 y Fh(2)p Fi(m)296 b Fe(\241)f Fi(t)p 25822 63003 3882 54 v 27194 64220 a(m)29836 61037 y Fa(!)35538 62410 y Fh(\()p Fi(m)g Fe(\241)g Fi(t)p Fh(\))39781 61928 y Fd(2)p 31242 63003 13361 54 v 31242 64220 a Fh(\(2)p Fi(m)g Fe(\241)h Fh(2)p Fi(t)f Fe(\241)g Fh(1\)\(2)p Fi(m)g Fe(\241)h Fh(2)p Fi(t)p Fh(\))44868 62410 y(2)p Fi(m)f Fe(\241)h Fi(t)f Fe(\241)g Fh(1)p 44868 63003 6156 54 v 46005 64220 a(2)p Fi(m)g Fe(\241)h Fi(t)17012 69354 y(>)18851 68456 y Fh(4\()p Fi(m)f Fe(\241)g Fi(t)p Fh(\)\(2)p Fi(m)f Fe(\241)i Fi(t)f Fe(\241)g Fh(1\))p 18525 69049 12710 54 v 18525 70266 a(\(2)p Fi(m)g Fe(\241)h Fh(2)p Fi(t)f Fe(\241)g Fh(1\)\(2)p Fi(m)g Fe(\241)h Fi(t)p Fh(\))31368 69354 y Fi(:)p Black 26475 74617 a Fh(5)p Black eop %%Page: 6 6 6 5 bop Black 0 TeXcolorgray Black Black 2751 1424 a Fh(The)434 b(righ)-36 b(t)433 b(hand)g(side)g(of)h(the)f(inequalit)-36 b(y)435 b(is)f(greater)g(than)f(2)h(when)f Fi(m)368 b(>)h(t)433 b Fh(since)12101 4032 y(4\()p Fi(m)295 b Fe(\241)g Fi(t)p Fh(\)\(2)p Fi(m)g Fe(\241)g Fi(t)g Fe(\241)g Fh(1\))p 11776 4625 12710 54 v 11776 5842 a(\(2)p Fi(m)g Fe(\241)g Fh(2)p Fi(t)g Fe(\241)h Fh(1\)\(2)p Fi(m)f Fe(\241)g Fi(t)p Fh(\))24987 4931 y(=)369 b(2)296 b(+)34548 4032 y(2)p Fi(t)p 28753 4625 V 28753 5842 a Fh(\(2)p Fi(m)f Fe(\241)h Fh(2)p Fi(t)f Fe(\241)g Fh(1\)\(2)p Fi(m)g Fe(\241)h Fi(t)p Fh(\))41596 4931 y Fi(:)2751 9452 y Fh(When)433 b Fi(m)369 b Fh(=)f Fi(t)p Fh(,)434 b(and)f Fi(t)369 b Fe(\270)g Fh(2,)434 b(it)g(is)g(sho)-36 b(wn)433 b(easily)i(b)-36 b(y)434 b(induction)e(that)38078 8554 y(4)38728 8072 y Fc(t)p 37587 9147 2028 54 v 37587 9391 a Fa(\241)38196 9877 y Fd(2)p Fc(t)38431 10925 y(t)39006 9391 y Fa(\242)40117 9452 y Fi(>)369 b Fh(2.)p 51860 11920 45 878 v 51905 11086 781 45 v 51905 11920 V 52684 11920 45 878 v Black 800 14559 a Fg(Lemma)499 b(6.)p Black 554 w Ff(If)464 b Fi(n)369 b Fe(\270)g Fh(2)466 b Ff(and)f Fi(k)414 b Fe(\270)369 b Fh(2)p Ff(,)464 b(then)h Fi(r)22843 14758 y Fc(n;k)24244 14559 y Fh(\()p Fi(:)p Fh(5\))369 b Fi(>)g Fh(1)p Ff(.)p Black 800 17197 a(Pr)-66 b(o)g(of.)p Black 649 w Fh(Noting)434 b(that)f Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(:)p Fh(5\))370 b(=)f Fi(Q)p Fh(\()p Fi(k)45 b(;)221 b(:)p Fh(5\))370 b(=)f Fi(:)p Fh(5,)434 b(w)-36 b(e)434 b(ha)-36 b(v)g(e)434 b(from)g(\(6\),)18089 21100 y Fi(r)18675 21299 y Fc(n;k)20076 21100 y Fh(\()p Fi(:)p Fh(5\))369 b(=)23982 20202 y(1)p 23982 20795 651 54 v 23982 22011 a(2)24898 19041 y Fa(\241)25507 19528 y Fd(2)p Fc(n)25742 20575 y(n)26548 19041 y Fa(\242\241)27766 19528 y Fd(2)p Fc(k)28001 20575 y(k)28750 19041 y Fa(\242)p 24898 20795 4461 54 v 25742 21083 a(\241)26351 21569 y Fd(2)p Fc(nk)26586 22617 y(nk)27906 21083 y Fa(\242)29491 21100 y Fh(4)30141 20552 y Fd(\()p Fc(k)24 b Fb(\241)p Fd(1\)\()p Fc(n)p Fb(\241)p Fd(1\))35150 21100 y Fi(:)2751 24339 y Fh(Lemma)433 b(6)h(is)g(true)f(for)h Fi(k)414 b Fh(=)369 b(2,)434 b(since)g(w)-36 b(e)434 b(ha)-36 b(v)g(e)19517 28198 y Fi(r)20103 28397 y Fc(n;)p Fd(2)21461 28198 y Fh(\()p Fi(:)p Fh(5\))370 b(=)e(3)434 b(4)26968 27650 y Fc(n)p Fb(\241)p Fd(1)28930 26139 y Fa(\241)29539 26626 y Fd(2)p Fc(n)29774 27673 y(n)30580 26139 y Fa(\242)p 28930 27893 2260 54 v 28930 28136 a(\241)29539 28623 y Fd(4)p Fc(n)29539 29670 y Fd(2)p Fc(n)30580 28136 y Fa(\242)31691 28198 y Fi(>)368 b Fh(1)p Fi(;)800 31393 y Fh(and)433 b(w)-36 b(e)434 b(apply)g(Lemma)f(5)h(with)g Fi(m)368 b Fh(=)h(2)p Fi(n)434 b Fh(and)f Fi(t)369 b Fh(=)g Fi(n)p Fh(.)2751 32998 y(W)-108 b(e)448 b(sho)-36 b(w)447 b(b)-36 b(y)448 b(induction)f(that)g(Lemma)g(6)h(holds)g(for)g (all)g Fi(k)45 b Fh(.)621 b(Supp)36 b(ose)446 b(it)i(is)g(true)f(for)h (some)g Fi(k)45 b Fh(,)452 b(and)800 34603 y(consider)433 b(Lemma)h(6)g(with)f Fi(k)479 b Fh(replaced)433 b(b)-36 b(y)434 b Fi(k)340 b Fh(+)295 b(1.)7982 39834 y Fi(r)8568 40033 y Fc(n;k)24 b Fd(+1)11172 39834 y Fh(\()p Fi(:)p Fh(5\))369 b(=)15077 38936 y(1)p 15077 39529 651 54 v 15077 40746 a(2)15993 37690 y Fa(\241)16602 38177 y Fd(2)p Fc(n)16837 39224 y(n)17644 37690 y Fa(\242)o(\241)18861 38177 y Fd(2)p Fc(k)24 b Fd(+2)19096 39224 y Fc(k)g Fd(+1)21048 37690 y Fa(\242)p 15993 39529 5663 54 v 16552 39817 a(\241)17161 40303 y Fd(2)p Fc(nk)g Fd(+2)p Fc(n)17631 41351 y(nk)g Fd(+)p Fc(n)20489 39817 y Fa(\242)21789 39834 y Fh(4)22439 39286 y Fc(k)g Fd(\()p Fc(n)p Fb(\241)p Fd(1\))13564 46258 y Fh(=)369 b(4)15595 45710 y Fc(n)p Fb(\241)p Fd(1)17645 43987 y Fa(\303)18829 45360 y Fh(1)p 18829 45953 651 54 v 18829 47170 a(2)19745 44199 y Fa(\241)20354 44686 y Fd(2)p Fc(n)20589 45733 y(n)21395 44199 y Fa(\242\241)22613 44686 y Fd(2)p Fc(k)22848 45733 y(k)23597 44199 y Fa(\242)p 19745 45953 4461 54 v 20589 46241 a(\241)21198 46727 y Fd(2)p Fc(nk)21433 47775 y(nk)22753 46241 y Fa(\242)24339 46258 y Fh(4)24989 45710 y Fd(\()p Fc(k)24 b Fb(\241)p Fd(1\)\()p Fc(n)p Fb(\241)p Fd(1\))29997 43987 y Fa(!)31403 45360 y Fh(\(2)p Fi(k)340 b Fh(+)295 b(2\)\(2)p Fi(k)341 b Fh(+)295 b(1\))p 31403 45953 9271 54 v 33783 47170 a(\()p Fi(k)340 b Fh(+)295 b(1\))37768 46786 y Fd(2)41826 44199 y Fa(\241)42435 44686 y Fd(2)p Fc(nk)42670 45733 y(nk)43990 44199 y Fa(\242)p 40939 45953 4546 54 v 40939 46241 a(\241)41548 46727 y Fd(2)p Fc(nk)24 b Fd(+2)p Fc(n)42019 47775 y(nk)g Fd(+)p Fc(n)44876 46241 y Fa(\242)13564 52597 y Fi(>)15077 51698 y Fh(1)p 15077 52291 651 54 v 15077 53508 a(2)15861 52597 y(4)16511 52048 y Fc(n)18157 50538 y Fa(\241)18765 51024 y Fd(2)p Fc(nk)19001 52072 y(nk)20320 50538 y Fa(\242)p 17270 52291 4546 54 v 17270 52579 a(\241)17879 53066 y Fd(2)p Fc(nk)g Fd(+2)p Fc(n)18349 54113 y(nk)g Fd(+)p Fc(n)21207 52579 y Fa(\242)22081 51698 y Fh(2)p Fi(k)341 b Fh(+)295 b(1)p 22081 52291 3624 54 v 22407 53508 a Fi(k)340 b Fh(+)295 b(1)26207 52597 y Fi(>)369 b Fh(1)p Fi(:)800 56481 y Fh(The)434 b(\257nal)f(inequalit)-36 b(y)435 b(is)f(obtained)f(b)-36 b(y)433 b(applying)h(Lemma)g(5)g(with)f Fi(m)369 b Fh(=)f Fi(nk)341 b Fh(+)295 b Fi(n)434 b Fh(and)f Fi(t)369 b Fh(=)f Fi(n)p Fh(.)p 51860 58086 45 878 v 51905 57253 781 45 v 51905 58086 V 52684 58086 45 878 v Black 800 60725 a Fg(Theorem)499 b(1.)p Black 554 w Ff(If)464 b Fi(n)370 b Fe(\270)f Fh(2)p Fi(;)687 b(k)414 b Fe(\270)369 b Fh(2)p Fi(;)465 b Ff(and)g Fi(:)p Fh(5)370 b Fi(<)e(p)h(<)g Fh(1)p Ff(,)465 b(then)f Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))370 b Fi(>)f(P)181 b Fh(\()p Fi(nk)45 b(;)221 b(p)p Fh(\))p Ff(.)p Black 800 63363 a(Pr)-66 b(o)g(of.)p Black 649 w Fh(W)-108 b(e)434 b(ha)-36 b(v)g(e)433 b Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(:)p Fh(5\))372 b(=)c Fi(P)181 b Fh(\()p Fi(nk)45 b(;)221 b(:)p Fh(5\))371 b(=)d Fi(:)p Fh(5,)435 b(and)e Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b Fh(1\))370 b(=)f Fi(P)181 b Fh(\()p Fi(nk)45 b(;)221 b Fh(1\))370 b(=)f(1.)2751 66568 y(If)434 b(there)g(existed)g(a)g(p)36 b(oin)-36 b(t)433 b Fi(p)16888 66767 y Fd(1)17414 66568 y Fh(,)h Fi(:)p Fh(5)370 b Fi(<)f(p)21624 66767 y Fd(1)22519 66568 y Fi(<)g Fh(1,)434 b(suc)-36 b(h)433 b(that)h Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)35937 66767 y Fd(1)36464 66568 y Fh(\))369 b(=)g Fi(P)181 b Fh(\()p Fi(nk)45 b(;)221 b(p)42977 66767 y Fd(1)43504 66568 y Fh(\),)434 b(then)e Fi(r)48353 66767 y Fc(n;k)49755 66568 y Fh(\()p Fi(p)p Fh(\))368 b(=)933 68047 y Fi(P)1952 67565 y Fb(0)2262 68047 y Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))p 933 68640 5657 54 v 1224 69857 a Fi(P)2243 69473 y Fb(0)2554 69857 y Fh(\()p Fi(nk)45 b(;)221 b(p)p Fh(\))7268 68945 y(w)-36 b(ould)546 b(need)g(to)g(b)36 b(e)545 b(1)i(at)f(least)g(t)-36 b(wice,)575 b(once)546 b(on)g(the)f(in)-36 b(terv)-72 b(al)546 b Fi(:)p Fh(5)561 b Fi(<)f(p)g(<)g(p)46558 69144 y Fd(1)47630 68945 y Fh(and)545 b(once)800 71296 y(on)468 b(the)g(in)-36 b(terv)-72 b(al)469 b Fi(p)10301 71495 y Fd(1)11255 71296 y Fi(<)428 b(p)h(<)f Fh(1)468 b(\(since)h Fi(r)20649 71495 y Fc(n;k)22050 71296 y Fh(\()p Fi(p)p Fh(\))f(cannot)g(b)36 b(e)468 b(greater)h(than)f(1)h(\(or)f(less)h(than)f(1\))h(o)-36 b(v)g(er)469 b(the)p Black 26475 74617 a(6)p Black eop %%Page: 7 7 7 6 bop Black 0 TeXcolorgray Black Black 800 1424 a Fh(full)453 b(exten)-36 b(t)452 b(of)h(either)f(in)-36 b(terv)-72 b(al\).)634 b(But)452 b Fi(r)21244 1623 y Fc(n;k)22645 1424 y Fh(\()p Fi(p)p Fh(\))g(cannot)g(b)36 b(e)452 b(1)g(at)h(least)f (t)-36 b(wice)453 b(b)36 b(ecause)452 b(w)-36 b(e)453 b(kno)-36 b(w)453 b(from)800 3029 y(Lemma)569 b(4)f(that)h Fi(r)10336 3228 y Fc(n;k)11737 3029 y Fh(\()p Fi(p)p Fh(\))f(is)h(a)g(decreasing)g(function)f(of)h Fi(p)p Fh(.)984 b(Hence,)602 b(either)569 b Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))600 b Fi(>)e(P)181 b Fh(\()p Fi(nk)45 b(;)221 b(p)p Fh(\),)800 4634 y(or)546 b Fi(P)181 b Fh(\()p Fi(nk)45 b(;)221 b(p)p Fh(\))370 b Fi(>)e(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))r(,)574 b(on)546 b(the)g(in)-36 b(terv)-72 b(al)546 b Fi(:)p Fh(5)561 b Fi(<)g(p)f(<)g Fh(1.)917 b(Since)545 b(w)-36 b(e)547 b(kno)-36 b(w)547 b(from)f(Lemma)g(6)h(that)800 6239 y Fi(r)1386 6438 y Fc(n;k)2787 6239 y Fh(\()p Fi(:)p Fh(5\))370 b Fi(>)e Fh(1,)434 b(w)-36 b(e)434 b(m)-36 b(ust)433 b(ha)-36 b(v)g(e)434 b Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))370 b Fi(>)f(P)181 b Fh(\()p Fi(nk)45 b(;)221 b(p)p Fh(\))434 b(o)-36 b(v)g(er)434 b(that)f(same)h(range.)p 51860 7844 45 878 v 51905 7011 781 45 v 51905 7844 V 52684 7844 45 878 v Black 800 10557 a Fg(Lemma)499 b(7.)p Black 554 w Ff(L)-66 b(et)21225 13031 y Fi(f)142 b Fh(\()p Fi(n;)221 b(x)p Fh(\))370 b(=)26940 11371 y Fc(n)p Fb(\241)p Fd(1)26868 11769 y Fa(X)27066 14569 y Fc(i)p Fd(=0)29008 13031 y Fi(a)29691 13230 y Fc(n;i)30899 13031 y Fi(x)31638 12483 y Fc(i)32013 13031 y Fi(:)800 16454 y Ff(If)464 b(the)h(function)10457 19664 y Fi(h)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(x)p Fh(\))371 b(=)d(\()p Fi(n)296 b Fe(\241)f Fh(1\))p Fi(f)142 b Fh(\()p Fi(n;)221 b(x)p Fh(\))p Fi(f)26106 19116 y Fb(0)26417 19664 y Fh(\()p Fi(k)45 b(;)221 b(x)p Fh(\))296 b Fe(\241)f Fh(\()p Fi(k)340 b Fe(\241)296 b Fh(1\))p Fi(f)142 b Fh(\()p Fi(k)45 b(;)221 b(x)p Fh(\))p Fi(f)39722 19116 y Fb(0)40033 19664 y Fh(\()p Fi(n;)g(x)p Fh(\))800 21989 y Ff(has)528 b(at)f(most)g(one)g(p)-66 b(ositive)526 b(zer)-66 b(o,)542 b(then)527 b(the)f(functions)g Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))529 b Ff(and)e Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(n;)g(p)p Fh(\))528 b Ff(c)-66 b(annot)526 b(interse)-66 b(ct)800 23594 y(on)465 b(the)f(interval)g Fi(:)p Fh(5)369 b Fi(<)g(p)g(<)f Fh(1)p Ff(.)p Black 800 26195 a(Pr)-66 b(o)g(of.)p Black 649 w Fh(Let)20756 28459 y Fi(R)21746 28658 y Fc(n;k)23147 28459 y Fh(\()p Fi(p)p Fh(\))368 b(=)26694 27561 y Fi(P)27713 27079 y Fb(0)28023 27561 y Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))p 26694 28154 5657 54 v 26694 29370 a Fi(P)27713 28987 y Fb(0)28023 29370 y Fh(\()p Fi(k)45 b(;)221 b(n;)g(p)p Fh(\))32483 28459 y Fi(:)800 31455 y Fh(Lo)36 b(oking)435 b(at)e(the)g(pro)36 b(of)435 b(of)f(Lemma)f(4)h(w)-36 b(e)434 b(see)g(that)12149 35352 y Fi(R)13139 35551 y Fc(n;k)14540 35352 y Fh(\()p Fi(p)p Fh(\))369 b(=)18275 33846 y Fd(1)p 18275 34063 471 54 v 18275 34827 a(2)18879 34369 y Fi(n)19655 33293 y Fa(\241)20264 33780 y Fd(2)p Fc(n)20499 34827 y(n)21305 33293 y Fa(\242)22136 34369 y Fh(\()o Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\))p Fi(Q)p Fh(\()p Fi(k)45 b(;)221 b(p)p Fh(\)\))31133 33723 y Fc(n)p Fb(\241)p Fd(1)33315 33846 y(1)p 33315 34063 V 33315 34827 a(2)33919 34369 y Fi(k)34640 33293 y Fa(\241)35249 33780 y Fd(2)p Fc(k)35484 34827 y(k)36233 33293 y Fa(\242)36841 34369 y Fh(\()p Fi(pq)48 b Fh(\))39131 33887 y Fc(k)24 b Fb(\241)p Fd(1)p 18087 35046 22870 54 v 18220 35944 a(1)p 18220 36161 471 54 v 18220 36925 a(2)18823 36467 y Fi(k)19544 35391 y Fa(\241)20153 35877 y Fd(2)p Fc(k)20389 36925 y(k)21137 35391 y Fa(\242)21967 36467 y Fh(\()p Fi(P)181 b Fh(\()p Fi(n;)221 b(p)p Fh(\))p Fi(Q)p Fh(\()p Fi(n;)g(p)p Fh(\)\))31075 35821 y Fc(k)24 b Fb(\241)p Fd(1)33201 35944 y(1)p 33201 36161 V 33201 36925 a(2)33804 36467 y Fi(n)34580 35391 y Fa(\241)35189 35877 y Fd(2)p Fc(n)35424 36925 y(n)36231 35391 y Fa(\242)36839 36467 y Fh(\()p Fi(pq)48 b Fh(\))39129 36083 y Fc(n)p Fb(\241)p Fd(1)41090 35352 y Fi(:)2751 39293 y Fh(Substituting)432 b(from)i(Lemma)f(2,)i(and)e(simplifying,)i(w)-36 b(e)434 b(ha)-36 b(v)g(e)15273 42960 y Fi(R)16263 43159 y Fc(n;k)17664 42960 y Fh(\()p Fi(p)p Fh(\))368 b(=)21211 42062 y Fi(f)142 b Fh(\()p Fi(k)45 b(;)221 b(pq)48 b Fh(\))25587 41580 y Fc(n)p Fb(\241)p Fd(1)p 21211 42655 6205 54 v 21212 43871 a Fi(f)142 b Fh(\()p Fi(n;)221 b(pq)48 b Fh(\))25643 43488 y Fc(k)24 b Fb(\241)p Fd(1)27548 42960 y Fi(;)4221 b(:)p Fh(5)370 b Fe(\267)f Fi(p)g(<)g Fh(1)p Fi(:)2751 46030 y Fh(F)-108 b(ollo)-36 b(wing)558 b(the)e(simple)h(argumen)-36 b(t)556 b(made)h(in)g(the)f(the)g(pro)36 b(of)557 b(of)h(Theorem)f(1,) 588 b(if)558 b Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))558 b(and)800 47635 y Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(n;)g(p)p Fh(\))496 b(in)-36 b(tersected)493 b(on)h Fi(:)p Fh(5)473 b Fi(<)f(p)g(<)g Fh(1,)510 b Fi(R)23203 47834 y Fc(n;k)24605 47635 y Fh(\()p Fi(p)p Fh(\))493 b(w)-36 b(ould)495 b(equal)g(1)f(at)h(least)g(t)-36 b(wice)494 b(on)h(that)e(in)-36 b(terv)-72 b(al.)800 49240 y(F)-108 b(urthermore,)601 b(since)569 b Fi(f)142 b Fh(\()p Fi(n;)221 b(:)p Fh(25\))601 b(=)e(4)19861 48758 y Fc(n)p Fb(\241)p Fd(1)22258 49240 y Fh(and)569 b Fi(f)142 b Fh(\()p Fi(k)45 b(;)221 b(:)p Fh(25\))370 b(=)f(4)32083 48758 y Fc(k)24 b Fb(\241)p Fd(1)34423 49240 y Fh(\(see)569 b(Lemma)f(2)h(with)g Fi(p)599 b Fh(=)g Fi(:)p Fh(5)570 b(and)800 50845 y Fi(pq)416 b Fh(=)369 b Fi(:)p Fh(25\),)377 b Fi(R)7722 51044 y Fc(n;k)9123 50845 y Fh(\()p Fi(:)p Fh(25\))369 b(=)g(1.)555 b(Hence,)376 b(there)360 b(w)-36 b(ould)362 b(b)36 b(e)361 b(at)g(least)h(three)f(di\256eren)-36 b(t)360 b(v)-72 b(alues)362 b(of)g Fi(pq)408 b Fh(for)362 b(whic)-36 b(h)800 52450 y Fi(R)1790 52649 y Fc(n;k)3191 52450 y Fh(\()p Fi(p)p Fh(\))369 b(=)f(1.)2751 54055 y(Therefore,)391 b(the)379 b(logarithm)h(of)g Fi(R)19432 54254 y Fc(n;k)20833 54055 y Fh(\()p Fi(p)p Fh(\))f(w)-36 b(ould)380 b(equal)g(0)g(at)f (least)h(three)f(times,)390 b(and)379 b(the)g(deriv)-72 b(ativ)-36 b(e)800 55660 y(of)564 b(that)e(logarithm)i(with)f(resp)36 b(ect)563 b(to)g Fi(pq)610 b Fh(w)-36 b(ould)563 b(equal)h(0)g(at)f (least)g(t)-36 b(wice.)968 b(The)563 b(deriv)-72 b(ativ)-36 b(e)564 b(of)g(the)800 57266 y(logarithm)434 b(of)h Fi(R)9197 57465 y Fc(n;k)10598 57266 y Fh(\()p Fi(p)p Fh(\))e(with)g(resp)36 b(ect)434 b(to)f Fi(pq)481 b Fh(is)434 b(equal)g(to)23769 59978 y Fi(h)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(pq)48 b Fh(\))p 22216 60571 8807 54 v 22216 61787 a Fi(f)142 b Fh(\()p Fi(n;)221 b(pq)48 b Fh(\))p Fi(f)142 b Fh(\()p Fi(k)45 b(;)221 b(pq)48 b Fh(\))31155 60876 y Fi(;)800 63872 y Fh(pro)-36 b(ving)434 b(the)f(Lemma.)p 51860 65477 45 878 v 51905 64644 781 45 v 51905 65477 V 52684 65477 45 878 v Black 800 68870 a Fg(Lemma)499 b(8.)p Black 554 w Ff(L)-66 b(et)464 b Fe(f)p Fi(a)11401 69069 y Fc(i)11776 68870 y Fe(g)12440 68388 y Fc(n)12440 69198 y Fd(1)13532 68870 y Ff(b)-66 b(e)464 b(a)h(se)-66 b(quenc)g(e)463 b(such)j(that)e Fi(a)27830 69069 y Fd(1)28725 68870 y Fi(<)369 b Fh(0)p Ff(,)32293 67209 y Fc(n)31619 67608 y Fa(X)31817 70407 y Fc(i)p Fd(=1)33759 68870 y Fi(a)34442 69069 y Fc(i)35187 68870 y Fe(\267)g Fh(0)465 b Ff(and)g(such)h(that)f (either)p Black 26475 74617 a Fh(7)p Black eop %%Page: 8 8 8 7 bop Black 0 TeXcolorgray Black Black 800 1424 a Ff(Case)465 b(1:)598 b Fi(a)6332 1623 y Fc(i)7076 1424 y Fe(\267)369 b Fh(0)930 b Ff(if)f Fh(2)370 b Fe(\267)f Fi(i)f Fe(\267)i Fi(n)p Ff(,)464 b(or)800 3029 y(Case)h(2:)598 b(ther)-66 b(e)463 b(exists)i(a)g Fi(t)369 b Fe(\267)g Fi(n)465 b Ff(such)h(that)e Fi(a)23346 3228 y Fc(i)24091 3029 y Fe(\267)369 b Fh(0)930 b Ff(if)f Fh(2)369 b Fe(\267)h Fi(i)e(<)h(t)p Ff(,)464 b(and)h Fi(a)37955 3228 y Fc(i)38699 3029 y Fi(>)369 b Fh(0)465 b Ff(if)929 b Fi(i)369 b Fe(\270)g Fi(t)p Ff(.)800 4874 y(holds.)2751 8079 y(L)-66 b(et)464 b Fe(f)p Fi(r)6244 8278 y Fc(i)6620 8079 y Fe(g)7284 7597 y Fc(n)7284 8408 y Fd(1)8375 8079 y Ff(b)-66 b(e)464 b(a)h(se)-66 b(quenc)g(e)464 b(such)h(that)g(for)g(al)66 b(l)465 b Fi(i)p Ff(,)f Fi(r)27819 8278 y Fc(i)28564 8079 y Fi(>)369 b Fh(0)465 b Ff(and)g Fi(r)34170 8278 y Fc(i)p Fd(+1)36117 8079 y Fi(<)369 b(r)38084 8278 y Fc(i)38460 8079 y Ff(.)2751 12297 y(Then)6812 10636 y Fc(n)6138 11035 y Fa(X)6336 13834 y Fc(i)p Fd(=1)8278 12297 y Fi(r)8864 12496 y Fc(i)9240 12297 y Fi(a)9923 12496 y Fc(i)10668 12297 y Fi(<)f Fh(0)p Ff(.)p Black 800 15977 a(Pr)-66 b(o)g(of.)p Black 649 w Fh(The)434 b(Lemma)f(is)h(ob)-36 b(vious)434 b(for)g(Case)h(1.)2751 20121 y(F)-108 b(or)492 b(Case)i(2,)10506 18460 y Fc(n)9832 18859 y Fa(X)10031 21658 y Fc(i)p Fd(=1)11973 20121 y Fi(r)12559 20320 y Fc(i)12934 20121 y Fi(a)13617 20320 y Fc(i)14328 20121 y Fe(\241)16371 18460 y Fc(n)15697 18859 y Fa(X)15895 21658 y Fc(i)p Fd(=1)17837 20121 y Fi(r)18423 20320 y Fc(t)18818 20121 y Fi(a)19501 20320 y Fc(i)20346 20121 y Fi(<)469 b Fh(0,)508 b(since)493 b(\()p Fi(r)27684 20320 y Fd(1)28545 20121 y Fe(\241)335 b Fi(r)30499 20320 y Fc(t)30895 20121 y Fh(\))p Fi(a)32084 20320 y Fd(1)33101 20121 y Fh(is)493 b(negativ)-36 b(e,)509 b(and)492 b(if)h Fi(i)469 b(>)g Fh(1,)508 b Fi(r)48372 20320 y Fc(i)49083 20121 y Fe(\241)336 b Fi(r)51038 20320 y Fc(t)51926 20121 y Fh(is)800 22824 y(p)36 b(ositiv)-36 b(e)435 b(when)e Fi(a)9692 23023 y Fc(i)10501 22824 y Fh(is)h(negativ)-36 b(e)434 b(or)g(zero,)g(and)f(zero)h(or)f(negativ) -36 b(e)435 b(when)e Fi(a)37710 23023 y Fc(i)38519 22824 y Fh(is)h(p)36 b(ositiv)-36 b(e.)579 b(Hence,)21038 25054 y Fc(n)20364 25453 y Fa(X)20562 28252 y Fc(i)p Fd(=1)22504 26715 y Fi(r)23090 26914 y Fc(i)23466 26715 y Fi(a)24149 26914 y Fc(i)24893 26715 y Fi(<)26948 25054 y Fc(n)26274 25453 y Fa(X)26472 28252 y Fc(i)p Fd(=1)28414 26715 y Fi(r)29000 26914 y Fc(t)29395 26715 y Fi(a)30078 26914 y Fc(i)30823 26715 y Fe(\267)369 b Fh(0)p Fi(:)p 51860 30064 45 878 v 51905 29231 781 45 v 51905 30064 V 52684 30064 45 878 v Black 800 32719 a Fg(Lemma)499 b(9.)p Black 554 w Ff(Each)465 b(of)g(the)f(r)-66 b(atios)19140 31820 y Fi(a)19823 32019 y Fc(n;t)p 18539 32413 3113 54 v 18539 33630 a Fi(a)19222 33829 y Fc(n;t)p Fb(\241)p Fd(1)22249 32719 y Ff(and)24906 31820 y Fi(a)25589 32019 y Fc(n)p Fd(+1)p Fc(;t)p 24906 32413 V 24906 33630 a Fi(a)25589 33829 y Fc(n;t)p Fb(\241)p Fd(1)28616 32719 y Ff(de)g(cr)g(e)g(ases)464 b(as)h Fi(t)g Ff(de)-66 b(cr)g(e)g(ases.)p Black 800 36084 a(Pr)g(o)g(of.)p Black 12806 37506 a Fi(a)13489 37705 y Fc(n;t)p 12205 38099 V 12205 39316 a Fi(a)12888 39515 y Fc(n;t)p Fb(\241)p Fd(1)15746 38404 y Fe(\241)17207 37506 y Fi(a)17890 37705 y Fc(n;t)p Fb(\241)p Fd(1)p 17207 38099 V 17207 39316 a Fi(a)17890 39515 y Fc(n;t)p Fb(\241)p Fd(2)20821 38404 y Fh(=)22335 37506 y(2)221 b(\(1)296 b(+)e Fi(n)26740 37024 y Fd(2)27562 37506 y Fh(+)h(2)p Fi(n)p Fh(\()p Fi(t)g Fe(\241)g Fh(1\))h(+)f Fi(t)p Fh(\(3)p Fi(t)f Fe(\241)i Fh(5\)\))p 22335 38099 18699 54 v 24575 39316 a Fi(t)p Fh(\()p Fi(t)e Fe(\241)i Fh(1\)\()p Fi(n)f Fh(+)g Fi(t)g Fe(\241)g Fh(1\)\()p Fi(n)h Fh(+)f Fi(t)p Fh(\))41166 38404 y Fi(;)800 41411 y Fh(whic)-36 b(h)433 b(is)h(p)36 b(ositiv)-36 b(e)435 b(for)f Fi(t)369 b Fe(\270)g Fh(2)434 b(and)f Fi(n)369 b Fe(\270)g Fh(3.)10260 44123 y Fi(a)10943 44322 y Fc(n)p Fd(+1)p Fc(;t)p 10260 44716 3113 54 v 10260 45933 a Fi(a)10943 46132 y Fc(n;t)p Fb(\241)p Fd(1)13800 45022 y Fe(\241)15261 44123 y Fi(a)15944 44322 y Fc(n)p Fd(+1)p Fc(;t)p Fb(\241)p Fd(1)p 15261 44716 4315 54 v 15862 45933 a Fi(a)16545 46132 y Fc(n;t)p Fb(\241)p Fd(2)20078 45022 y Fh(=)21591 44123 y(4\(2)p Fi(n)296 b Fh(+)f(1\))221 b(\()q Fi(n)p Fh(\()p Fi(n)295 b Fe(\241)h Fh(1\))f(+)g(2)p Fi(nt)g Fh(+)g Fi(t)p Fh(\(5)p Fi(t)g Fe(\241)g Fh(7\)\))p 21591 44716 21388 54 v 24799 45933 a(\()p Fi(t)f Fe(\241)i Fh(1\))p Fi(tn)p Fh(\()p Fi(n)f Fh(+)g Fi(t)p Fh(\)\()p Fi(n)g Fh(+)g(1)g(+)g Fi(t)p Fh(\))43112 45022 y Fi(;)800 48028 y Fh(whic)-36 b(h)433 b(is)h(p)36 b(ositiv)-36 b(e)435 b(for)f Fi(t)369 b Fe(\270)g Fh(2)434 b(and)f Fi(n)369 b Fe(\270)g Fh(3.)p 51860 49633 45 878 v 51905 48800 781 45 v 51905 49633 V 52684 49633 45 878 v 2751 52215 a(W)-108 b(e)362 b(note)h(that,)376 b(as)363 b(de\257ned,)375 b(the)362 b(quan)-36 b(tit)g(y)363 b Fi(R)25462 52414 y Fc(n;k)26863 52215 y Fh(\(1\))f(is)h(indeterminate.)554 b(W)-108 b(e)362 b(tak)-36 b(e)363 b Fi(R)44821 52414 y Fc(n;k)46222 52215 y Fh(\(1\))g(to)f(mean)839 53821 y(lim)800 54618 y Fc(p)p Fb(!)p Fd(1)2906 53821 y Fi(R)3896 54020 y Fc(n;k)5298 53821 y Fh(\()p Fi(p)p Fh(\).)p Black 800 57079 a Fg(Lemma)499 b(10.)p Black 554 w Ff(If)464 b Fh(1)369 b Fi(<)g(k)414 b(<)369 b(n)465 b Ff(then)f Fi(R)19913 57278 y Fc(n;k)21314 57079 y Fh(\(1\))369 b Fi(<)g Fh(1)p Ff(.)p Black 800 61334 a(Pr)-66 b(o)g(of.)p Black 649 w Fh(Noting)434 b(that)f Fi(pq)416 b Fh(=)369 b(0)434 b(when)f Fi(p)369 b Fh(=)f(1,)14534 65371 y Fi(R)15524 65570 y Fc(n;k)16925 65371 y Fh(\(1\))h(=)20469 64473 y Fi(f)142 b Fh(\()p Fi(k)45 b(;)221 b Fh(0\))24217 63991 y Fc(n)p Fb(\241)p Fd(1)p 20469 65066 5578 54 v 20470 66283 a Fi(f)142 b Fh(\()p Fi(n;)221 b Fh(0\))24273 65899 y Fc(k)24 b Fb(\241)p Fd(1)26548 65371 y Fh(=)28062 64311 y Fi(a)28745 63761 y Fc(n)p Fb(\241)p Fd(1)28745 64681 y Fc(k)g(;)p Fd(0)p 28062 65066 2512 54 v 28091 66390 a Fi(a)28774 65840 y Fc(k)g Fb(\241)p Fd(1)28774 66716 y Fc(n;)p Fd(0)31075 65371 y Fh(=)32588 63312 y Fa(\241)33330 63865 y Fd(1)p 33330 64083 471 54 v 33330 64846 a(2)33933 63312 y Fa(\241)34542 63799 y Fd(2)p Fc(k)34777 64846 y(k)35526 63312 y Fa(\242\242)36744 63534 y Fc(n)p Fb(\241)p Fd(1)p 32588 65066 5984 54 v 32588 65574 a Fa(\241)33330 66127 y Fd(1)p 33330 66344 471 54 v 33330 67108 a(2)33933 65574 y Fa(\241)34542 66060 y Fd(2)p Fc(n)34777 67108 y(n)35583 65574 y Fa(\242\242)36801 65840 y Fc(k)g Fb(\241)p Fd(1)38705 65371 y Fi(;)2751 70677 y Fh(Let)433 b Fi(u)5821 70876 y Fc(n;k)7592 70677 y Fh(=)9105 69779 y Fi(R)10095 69978 y Fc(n)p Fd(+1)p Fc(;k)12698 69779 y Fh(\(1\))p 9105 70372 5256 54 v 9706 71588 a Fi(R)10696 71787 y Fc(n;k)12097 71588 y Fh(\(1\))14862 70677 y(=)16243 68804 y Fa(\265)17679 69779 y Fi(n)295 b Fh(+)g(1)p 17354 70372 3680 54 v 17354 71588 a(4)p Fi(n)g Fh(+)g(2)21165 68804 y Fa(\266)22143 69102 y Fc(k)24 b Fb(\241)p Fd(1)24269 69779 y Fh(1)p 24269 70372 651 54 v 24269 71588 a(2)25052 68804 y Fa(\265)26030 69779 y Fh(2)p Fi(k)26355 71588 y(k)27401 68804 y Fa(\266)28379 70677 y Fi(;)655 b Fh(and)p Black 26475 74617 a(8)p Black eop %%Page: 9 9 9 8 bop Black 0 TeXcolorgray Black Black 2751 2022 a Fh(Let)433 b Fi(v)5710 2221 y Fc(n;k)7480 2022 y Fh(=)8994 1123 y Fi(u)9734 1322 y Fc(n;k)24 b Fd(+1)p 8994 1716 3344 54 v 9595 2933 a Fi(u)10335 3132 y Fc(n;k)12839 2022 y Fh(=)14678 1123 y Fi(n)295 b Fh(+)g(1)p 14353 1716 3680 54 v 14353 2933 a(4)p Fi(n)g Fh(+)g(2)18386 149 y Fa(\301)20231 1123 y Fi(k)340 b Fh(+)295 b(1)p 19906 1716 3624 54 v 19906 2933 a(4)p Fi(k)341 b Fh(+)294 b(2)2751 5138 y(It)434 b(is)g(assumed)f(in)g(the)g(follo)-36 b(wing)436 b(that)d(1)369 b Fi(<)g(k)414 b(<)368 b(n)p Fh(.)2751 7543 y Fi(v)3380 7742 y Fc(n;k)5150 7543 y Fi(<)h Fh(1,)434 b(since)f Fi(n)370 b(>)e(k)45 b Fh(,)434 b(and)f(the)g(function)25436 7020 y Fc(r)26 b Fd(+1)p 25200 7237 2124 54 v 25200 8001 a(4)p Fc(r)g Fd(+2)27890 7543 y Fh(is)434 b(a)g(decreasing)g(function)f(of)i Fi(r)469 b Fh(;)2751 9548 y(Since)433 b Fi(v)6776 9747 y Fc(n;k)8546 9548 y Fi(<)369 b Fh(1,)434 b Fi(u)12112 9747 y Fc(n;k)13947 9548 y Fh(is)g(a)g(decreasing)f(function)h(of)g Fi(k)45 b Fh(,)434 b(and)f(since)h Fi(u)37180 9747 y Fc(n;)p Fd(1)38907 9548 y Fh(=)369 b(1,)434 b Fi(u)42473 9747 y Fc(n;k)44243 9548 y Fi(<)369 b Fh(1;)2751 11553 y(Since)421 b Fi(u)6875 11752 y Fc(n;k)8645 11553 y Fi(<)369 b Fh(1)421 b(,)j Fi(R)12872 11752 y Fc(n;k)14273 11553 y Fh(\(1\))d(is)g(a)g (decreasing)g(function)g(of)h Fi(n)p Fh(,)i(and)c(since)h Fi(R)39795 11752 y Fc(k)24 b(;k)41139 11553 y Fh(\(1\))369 b(=)g(1,)424 b Fi(R)46976 11752 y Fc(n;k)48377 11553 y Fh(\(1\))369 b Fi(<)f Fh(1.)p 51860 13158 45 878 v 51905 12325 781 45 v 51905 13158 V 52684 13158 45 878 v Black 800 15870 a Fg(Theorem)499 b(2.)p Black 554 w Ff(If)464 b Fh(2)369 b Fe(\267)h Fi(k)414 b Fe(\267)369 b Fi(n)465 b Ff(and)g Fi(:)p Fh(5)370 b Fi(<)e(p)h(<)g Fh(1)p Ff(,)464 b(then)h Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))370 b Fi(>)e(P)181 b Fh(\()p Fi(k)45 b(;)221 b(n;)g(p)p Fh(\))p Ff(.)p Black 800 18582 a(Pr)-66 b(o)g(of.)p Black 649 w Fh(The)434 b Fi(h)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(x)p Fh(\))435 b(of)f(Lemma)f(7)h (can)g(b)36 b(e)433 b(written)g(as)1541 24035 y Fi(h)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(x)p Fh(\))370 b(=)f(\()p Fi(n)295 b Fe(\241)g Fh(1\))12809 22374 y Fc(n)p Fb(\241)p Fd(1)12736 22773 y Fa(X)12934 25572 y Fc(i)p Fd(=0)14876 24035 y Fi(a)15559 24234 y Fc(n;i)16767 24035 y Fi(x)17506 23486 y Fc(i)18205 22374 y(k)24 b Fb(\241)p Fd(1)18103 22773 y Fa(X)18301 25572 y Fc(i)p Fd(=0)20243 24035 y Fi(ia)21370 24234 y Fc(k)g(;i)22520 24035 y Fi(x)23259 23486 y Fc(i)p Fb(\241)p Fd(1)25133 24035 y Fe(\241)295 b Fh(\()p Fi(k)340 b Fe(\241)295 b Fh(1\))30790 22374 y Fc(k)24 b Fb(\241)p Fd(1)30689 22773 y Fa(X)30887 25572 y Fc(i)p Fd(=0)32829 24035 y Fi(a)33512 24234 y Fc(k)g(;i)34662 24035 y Fi(x)35401 23486 y Fc(i)36071 22374 y(n)p Fb(\241)p Fd(1)35999 22773 y Fa(X)36197 25572 y Fc(i)p Fd(=0)38139 24035 y Fi(ia)39266 24234 y Fc(n;i)40473 24035 y Fi(x)41212 23486 y Fc(i)p Fb(\241)p Fd(1)43159 24035 y Fh(=)44540 22374 y Fc(n)p Fd(+)p Fc(k)g Fb(\241)p Fd(3)45090 22773 y Fa(X)45223 25562 y Fc(r)i Fd(=0)47780 24035 y Fi(c)48340 24234 y Fc(n;k)e(;r)50453 24035 y Fi(x)51192 23486 y Fc(r)51698 24035 y Fi(:)2751 28140 y Fh(W)-108 b(e)602 b(sho)-36 b(w)602 b(that)f Fi(h)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(x)p Fh(\))603 b(has)f(at)g(most)g(one)g(p)36 b(ositiv)-36 b(e)602 b(zero)g(b)-36 b(y)602 b(sho)-36 b(wing)602 b(that)g(the)f(sequence)800 29745 y Fe(f)p Fi(c)2024 29944 y Fc(n;k)24 b(;r)4137 29745 y Fe(g)4801 29197 y Fc(n)p Fd(+)p Fc(k)g Fb(\241)p Fd(3)4801 30074 y Fc(r)i Fd(=0)8309 29745 y Fh(has)433 b(exactly)i(one)f(c)-36 b(hange)433 b(in)h(sign,)g(and)f(applying)h(Descartes')h(Rule)e(of)i (Signs.)2751 31350 y(W)-108 b(e)434 b(do)f(this)g(b)-36 b(y)434 b(considering)f(four)h(cases,)800 34556 y(Case)g(1:)579 b(0)369 b Fe(\267)h Fi(r)405 b Fe(\267)369 b Fi(k)340 b Fe(\241)296 b Fh(2.)578 b(W)-108 b(e)434 b(sho)-36 b(w)434 b(that)f Fi(c)23094 34755 y Fc(n;k)24 b(;r)25576 34556 y Fi(>)368 b Fh(0.)800 36161 y(Case)434 b(2:)579 b Fi(k)340 b Fe(\241)296 b Fh(1)369 b Fe(\267)g Fi(r)405 b Fe(\267)370 b Fi(n)295 b Fe(\241)h Fh(2.)578 b(W)-108 b(e)434 b(sho)-36 b(w)434 b(that)f(if)h Fi(c)26686 36360 y Fc(n;k)24 b(;r)29168 36161 y Fe(\267)369 b Fh(0,)434 b(then)f Fi(c)35538 36360 y Fc(n;k)24 b(;r)i Fd(+1)39222 36161 y Fi(<)369 b Fh(0.)800 37766 y(Case)434 b(3:)579 b Fi(n)296 b Fe(\241)f Fh(1)369 b Fe(\267)h Fi(r)405 b Fe(\267)369 b Fi(n)296 b Fh(+)e Fi(k)341 b Fe(\241)295 b Fh(4.)579 b(W)-108 b(e)433 b(sho)-36 b(w)434 b(that)f Fi(c)27872 37965 y Fc(n;k)24 b(;r)30354 37766 y Fi(<)369 b Fh(0.)800 39371 y(Case)434 b(4:)579 b Fi(r)405 b Fh(=)369 b Fi(n)296 b Fh(+)e Fi(k)341 b Fe(\241)295 b Fh(3.)579 b(W)-108 b(e)433 b(sho)-36 b(w)434 b(that)f Fi(c)23029 39570 y Fc(n;k)24 b(;r)25511 39371 y Fh(=)369 b(0.)800 42576 y Fg(Case)499 b(1:)665 b Fh(0)369 b Fe(\267)g Fi(r)405 b Fe(\267)370 b Fi(k)340 b Fe(\241)295 b Fh(2)p Fi(:)11342 46656 y(c)11902 46855 y Fc(n;k)24 b(;r)14384 46656 y Fh(=)15898 44995 y Fc(r)i Fd(+1)15765 45394 y Fa(X)15907 48193 y Fc(j)51 b Fd(=0)17905 46656 y Fh(\(\()p Fi(n)295 b Fe(\241)g Fh(1\))p Fi(j)371 b Fe(\241)295 b Fh(\()p Fi(k)340 b Fe(\241)295 b Fh(1\)\()p Fi(r)332 b Fh(+)295 b(1)g Fe(\241)g Fi(j)75 b Fh(\)\))221 b Fi(a)36248 46855 y Fc(k)24 b(;j)37510 46656 y Fi(a)38193 46855 y Fc(n;r)i Fd(+1)p Fb(\241)p Fc(j)41897 46656 y Fi(:)2751 50251 y Fh(W)-108 b(e)475 b(see)g(that)g Fi(c)10596 50450 y Fc(n;k)24 b(;r)13184 50251 y Fh(is)475 b(an)g(increasing)h(function)f (of)h Fi(n)p Fh(,)486 b(since)475 b(the)f(brac)-36 b(k)g(eted)475 b(term)g(in)g Fi(c)47490 50450 y Fc(n;k)24 b(;r)50078 50251 y Fh(is)475 b(an)800 51856 y(increasing)434 b(fun)-36 b(tion)433 b(of)h Fi(n)p Fh(,)h(and)16454 54624 y Fi(a)17137 54823 y Fc(n)p Fd(+1)p Fc(;t)p 16454 55218 3113 54 v 17055 56434 a Fi(a)17738 56633 y Fc(n;t)20068 55523 y Fh(=)369 b(1)295 b(+)23834 54624 y(3)p Fi(n)25260 54142 y Fd(2)26082 54624 y Fh(+)f Fi(n)i Fh(+)f(2)p Fi(t)g Fh(+)g(3)p Fi(nt)p 23834 55218 10552 54 v 25665 56434 a(n)p Fh(\()p Fi(n)h Fh(+)f Fi(t)g Fh(+)g(1\))34887 55523 y Fi(>)369 b Fh(1)p Fi(:)2751 58544 y Fh(Since)433 b Fi(c)6707 58743 y Fc(k)24 b(;k)g(;r)9132 58544 y Fh(=)368 b(0,)435 b Fi(c)12518 58743 y Fc(n;k)24 b(;r)15000 58544 y Fi(>)368 b Fh(0.)800 61749 y Fg(Case)499 b(2:)665 b Fi(k)340 b Fe(\241)295 b Fh(1)370 b Fe(\267)f Fi(r)405 b Fe(\267)369 b Fi(n)296 b Fe(\241)f Fh(2)p Fi(:)11523 65873 y(c)12083 66072 y Fc(n;k)24 b(;r)14565 65873 y Fh(=)16047 64212 y Fc(k)g Fb(\241)p Fd(1)15945 64611 y Fa(X)16088 67410 y Fc(j)51 b Fd(=0)18086 65873 y Fh(\()o(\()p Fi(n)296 b Fe(\241)f Fh(1\))p Fi(j)370 b Fe(\241)296 b Fh(\()p Fi(k)340 b Fe(\241)295 b Fh(1\)\()p Fi(r)331 b Fh(+)295 b(1)h Fe(\241)f Fi(j)75 b Fh(\)\))221 b Fi(a)36429 66072 y Fc(k)24 b(;j)37690 65873 y Fi(a)38373 66072 y Fc(n;r)i Fd(+1)p Fb(\241)p Fc(j)2751 69453 y Fh(Let)10762 71058 y Fi(b)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(r)-36 b(;)221 b(j)75 b Fh(\))371 b(=)e(\(\()p Fi(n)295 b Fe(\241)g Fh(1\))p Fi(j)371 b Fe(\241)295 b Fh(\()p Fi(k)340 b Fe(\241)295 b Fh(1\)\()p Fi(r)332 b Fh(+)295 b(2)g Fe(\241)g Fi(j)75 b Fh(\)\))221 b Fi(a)36828 71257 y Fc(k)24 b(;j)38090 71058 y Fi(a)38773 71257 y Fc(n;r)i Fd(+1)p Fb(\241)p Fc(j)42477 71058 y Fi(;)p Black 26475 74617 a Fh(9)p Black eop %%Page: 10 10 10 9 bop Black 0 TeXcolorgray Black Black 2751 1424 a Fh(so)434 b(that)17424 5548 y Fi(c)17984 5747 y Fc(n;k)24 b(;r)i Fd(+1)21668 5548 y Fh(=)23151 3888 y Fc(k)e Fb(\241)p Fd(1)23049 4286 y Fa(X)23191 7086 y Fc(j)51 b Fd(=0)25189 5548 y Fi(b)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(r)-36 b(;)221 b(j)75 b Fh(\))31293 4650 y Fi(a)31976 4849 y Fc(n;r)26 b Fd(+2)p Fb(\241)p Fc(j)p 31293 5243 4387 54 v 31293 6459 a Fi(a)31976 6658 y Fc(n;r)g Fd(+1)p Fb(\241)p Fc(j)35815 5548 y Fi(:)2751 9217 y Fh(W)-108 b(e)503 b(see)g(that)f Fi(b)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(r)-36 b(;)221 b Fh(0\))490 b Fi(<)c Fh(0,)521 b(the)502 b(brac)-36 b(k)g(eted)503 b(term)f(in)h Fi(b)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(r)-36 b(;)221 b(j)75 b Fh(\))504 b(increases)g(as)f Fi(j)577 b Fh(increases,)800 12068 y(and)587 b(if)i Fi(c)5390 12267 y Fc(n;k)24 b(;r)8135 12068 y Fe(\267)632 b Fh(0,)627 b(then)14656 10408 y Fc(k)24 b Fb(\241)p Fd(1)14555 10806 y Fa(X)14697 13606 y Fc(j)51 b Fd(=0)16695 12068 y Fi(b)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(r)-36 b(;)221 b(j)75 b Fh(\))634 b Fi(<)d Fh(0\(since)588 b(the)g(brac)-36 b(k)g(eted)587 b(term)h(in)f Fi(b)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(r)-36 b(;)221 b(j)75 b Fh(\))590 b(is)f(less)800 15018 y(than)438 b(the)f(brac)-36 b(k)g(eted)438 b(term)g(in)g Fi(c)17172 15217 y Fc(n;k)24 b(;r)19285 15018 y Fh(\).)592 b(F)-108 b(urthermore,)438 b(w)-36 b(e)439 b(kno)-36 b(w)438 b(from)h(Lemma)f(9)h(that)e(the)h (sequence)800 15553 y Fa(\275)1929 16527 y Fi(a)2612 16726 y Fc(n;r)26 b Fd(+2)p Fb(\241)p Fc(j)p 1929 17120 V 1929 18337 a Fi(a)2612 18536 y Fc(n;r)g Fd(+1)p Fb(\241)p Fc(j)6449 15553 y Fa(\276)7879 17426 y Fh(is)434 b(decreasing)f(as)h Fi(j)509 b Fh(increases.)2751 20542 y(Hence)433 b(the)g(conditions)h (set)f(forth)h(in)f(Lemma)h(8)g(are)g(met,)f(and)g(w)-36 b(e)434 b(ha)-36 b(v)g(e)434 b Fi(c)40701 20741 y Fc(n;k)24 b(;r)i Fd(+1)44385 20542 y Fi(<)369 b Fh(0)p Fi(:)800 23747 y Fg(Case)499 b(3:)665 b Fi(n)295 b Fe(\241)h Fh(1)369 b Fe(\267)g Fi(r)405 b Fe(\267)370 b Fi(n)295 b Fh(+)g Fi(k)340 b Fe(\241)295 b Fh(4)p Fg(.)2751 26952 y Fh(Let)433 b Fi(r)405 b Fh(=)369 b Fi(n)296 b Fe(\241)f Fh(1)g(+)g Fi(t)p Fh(,)867 b(0)370 b Fe(\267)f Fi(t)g Fe(\267)g Fi(k)340 b Fe(\241)295 b Fh(3.)9770 31076 y Fi(c)10330 31275 y Fc(n;k)24 b(;n)p Fb(\241)p Fd(1+)p Fc(t)15206 31076 y Fh(=)17082 29415 y Fc(k)g Fb(\241)p Fd(1)16980 29814 y Fa(X)16587 32613 y Fc(j)51 b Fd(=)p Fc(t)p Fd(+1)19514 31076 y Fh(\(\()p Fi(n)295 b Fe(\241)g Fh(1\))p Fi(j)371 b Fe(\241)295 b Fh(\()p Fi(k)340 b Fe(\241)295 b Fh(1\)\()p Fi(n)h Fh(+)f Fi(t)f Fe(\241)i Fi(j)75 b Fh(\)\))221 b Fi(a)37831 31275 y Fc(k)24 b(;j)39092 31076 y Fi(a)39775 31275 y Fc(n;n)p Fd(+)p Fc(t)p Fb(\241)p Fc(j)43469 31076 y Fi(:)2751 34745 y Fh(Let)433 b Fi(b)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(t;)g(j)75 b Fh(\))371 b(=)d(\()p Fi(nj)j Fe(\241)295 b Fh(\()p Fi(k)340 b Fe(\241)295 b Fh(1\)\()p Fi(n)h Fh(+)f(1)g(+)g Fi(t)g Fe(\241)g Fi(j)75 b Fh(\)\))221 b Fi(a)30007 34944 y Fc(k)24 b(;j)31269 34745 y Fi(a)31952 34944 y Fc(n;n)p Fd(+)p Fc(t)p Fb(\241)p Fc(j)35645 34745 y Fh(,)434 b(so)g(that)15278 38869 y Fi(c)15838 39068 y Fc(n)p Fd(+1)p Fc(;k)24 b(;n)p Fd(+)p Fc(t)20714 38869 y Fh(=)22590 37208 y Fc(k)g Fb(\241)p Fd(1)22488 37607 y Fa(X)22095 40406 y Fc(j)51 b Fd(=)p Fc(t)p Fd(+1)25022 38869 y Fi(b)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(t;)g(j)75 b Fh(\))31046 37970 y Fi(a)31729 38169 y Fc(n)p Fd(+1)p Fc(;n)p Fd(+1+)p Fc(t)p Fb(\241)p Fc(j)p 31046 38563 6781 54 v 32249 39780 a Fi(a)32932 39979 y Fc(n;n)p Fd(+)p Fc(t)p Fb(\241)p Fc(j)37961 38869 y Fi(:)2751 42538 y Fh(W)-108 b(e)642 b(see)g(that)g Fi(b)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(t;)g(t)438 b Fh(+)f(1\))724 b(=)f(\()p Fi(n)p Fh(\()p Fi(t)295 b Fe(\241)g Fh(\()p Fi(k)340 b Fe(\241)296 b Fh(2\)\)\))221 b Fi(a)31085 42737 y Fc(k)24 b(;j)32347 42538 y Fi(a)33030 42737 y Fc(n;n)p Fb(\241)p Fd(1)36414 42538 y Fi(<)723 b Fh(0,)695 b(the)641 b(brac)-36 b(k)g(eted)642 b(term)f(in)800 45428 y Fi(b)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(t;)g(j)75 b Fh(\))575 b(increases)f(as)f Fi(j)649 b Fh(increases,)609 b(and)572 b(if)i Fi(c)26293 45627 y Fc(n;k)24 b(;n)p Fb(\241)p Fd(1+)p Fc(t)31407 45428 y Fi(<)607 b Fh(0,)i(then)38243 43768 y Fc(k)24 b Fb(\241)p Fd(1)38142 44166 y Fa(X)37748 46966 y Fc(j)51 b Fd(=)p Fc(t)p Fd(+1)40675 45428 y Fi(b)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(t;)g(j)75 b Fh(\))371 b Fi(<)d Fh(0)574 b(\(since)800 48378 y(the)492 b(brac)-36 b(k)g(eted)491 b(term)h(in)g Fi(b)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(t;)g(j)75 b Fh(\))494 b(is)e(less)h(than)e(or)i(equal)g(to)f(the)f (brac)-36 b(k)g(eted)492 b(term)g(in)g Fi(c)47426 48577 y Fc(n;k)24 b(;n)p Fb(\241)p Fd(1+)p Fc(t)51933 48378 y Fh(\).)800 50786 y(F)-108 b(urthermore,)457 b(from)d(Lemma)g(9)f(w) -36 b(e)454 b(kno)-36 b(w)454 b(that)f(the)h(sequence)33436 48913 y Fa(\275)34565 49887 y Fi(a)35248 50086 y Fc(n)p Fd(+1)p Fc(;n)p Fd(+1+)p Fc(t)p Fb(\241)p Fc(j)p 34565 50480 V 35767 51697 a Fi(a)36450 51896 y Fc(n;n)p Fd(+)p Fc(t)p Fb(\241)p Fc(j)41479 48913 y Fa(\276)42929 50786 y Fh(is)g(decreasing)f(as)h Fi(j)800 53061 y Fh(increases.)2751 55466 y(Hence)513 b(the)f(conditions)h(set)g(forth)g(in)g(Lemma)g(8)g (are)g(met,)533 b(and)512 b(w)-36 b(e)514 b(ha)-36 b(v)g(e)513 b Fi(c)41753 55665 y Fc(n)p Fd(+1)p Fc(;k)24 b(;n)p Fd(+)p Fc(t)46629 55466 y Fi(<)369 b Fh(0.)816 b(Since)800 57071 y Fi(c)1360 57270 y Fc(k)24 b(;k)g(;k)g Fb(\241)p Fd(1+)p Fc(t)6121 57071 y Fh(=)369 b(0,)434 b(w)-36 b(e)434 b(ha)-36 b(v)g(e)434 b(for)g(all)g Fi(n)370 b(>)e(k)45 b Fh(,)434 b Fi(c)22256 57270 y Fc(n;k)24 b(;n)p Fb(\241)p Fd(1+)p Fc(t)27132 57071 y Fi(<)369 b Fh(0)p Fi(:)800 60276 y Fg(Case)499 b(4:)665 b Fi(r)405 b Fh(=)369 b Fi(n)295 b Fh(+)g Fi(k)340 b Fe(\241)296 b Fh(3)p Fg(.)2751 61881 y Fi(c)3311 62080 y Fc(n;k)24 b(;r)5793 61881 y Fh(=)369 b(\()o(\()p Fi(n)296 b Fe(\241)f Fh(1\)\()p Fi(k)340 b Fe(\241)296 b Fh(1\))f Fe(\241)g Fh(\()p Fi(k)341 b Fe(\241)295 b Fh(1\)\()p Fi(n)g Fe(\241)h Fh(1\)\))221 b Fi(a)26850 62080 y Fc(n;n)p Fb(\241)p Fd(1)29511 61881 y Fi(a)30194 62080 y Fc(k)24 b(;k)g Fb(\241)p Fd(1)33109 61881 y Fh(=)368 b(0)p Fg(.)2751 66686 y Fh(W)-108 b(e)609 b(ha)-36 b(v)g(e)610 b(pro)-36 b(v)g(ed)609 b(that)f Fi(h)p Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(x)p Fh(\))611 b(has)e(at)h(most)f(one)g(p)36 b(ositiv)-36 b(e)610 b(zero.)1106 b(Hence)609 b(w)-36 b(e)610 b(kno)-36 b(w)610 b(from)800 68291 y(Lemma)433 b(7)h(that)f(on)h(the)f(in)-36 b(terv)-72 b(al)434 b Fi(:)p Fh(5)369 b Fi(<)g(p)g(<)f Fh(1,)435 b Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))434 b(and)f Fi(P)181 b Fh(\()p Fi(k)45 b(;)221 b(n;)g(p)p Fh(\))p Black 26150 74617 a(10)p Black eop %%Page: 11 11 11 10 bop Black 0 TeXcolorgray Black Black 800 1991 a Fh(cannot)454 b(in)-36 b(tersect.)639 b(F)-108 b(rom)453 b(Lemma)h(10,)460 b(w)-36 b(e)454 b(kno)-36 b(w)455 b(that)493 b(lim)29305 2788 y Fc(p)p Fb(!)p Fd(1)31545 1092 y Fi(P)32564 610 y Fb(0)32874 1092 y Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))p 31545 1685 5657 54 v 31545 2902 a Fi(P)32564 2518 y Fb(0)32874 2902 y Fh(\()p Fi(k)45 b(;)221 b(n;)g(p)p Fh(\))37738 1991 y Fi(<)403 b Fh(1.)640 b(Hence,)459 b(w)-36 b(e)455 b(m)-36 b(ust)453 b(ha)-36 b(v)g(e)800 4341 y Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))370 b Fi(>)f(P)181 b Fh(\()p Fi(k)45 b(;)221 b(n;)g(p)p Fh(\))435 b(on)e Fi(:)p Fh(5)370 b Fi(<)e(p)h(<)g Fh(1.)p 51860 5946 45 878 v 51905 5112 781 45 v 51905 5946 V 52684 5946 45 878 v 800 10370 a Fn(3)2152 b(Coun)-60 b(terexamples)715 b(for)i(t)-60 b(w)g(o)718 b(conjectured)d (inequalities)800 15691 y Fh(De\257ne)378 b(Maxp)36 b(oin)-36 b(ts\()p Fi(m;)221 b(n)p Fh(\))370 b(:=)f(\(2)p Fi(m)182 b Fe(\241)g Fh(1\)\(2)p Fi(n)g Fe(\241)g Fh(1\),)392 b(the)378 b(maxim)-36 b(um)378 b(n)-36 b(um)g(b)36 b(er)377 b(of)i(p)36 b(oin)-36 b(ts)378 b(p)36 b(ossible)379 b(where)800 17296 y(the)433 b(winner)g(is)h(the)f(\257rst)g(pla)-36 b(y)g(er)434 b(to)g(win)f Fi(m)h(n)p Fh(-p)36 b(oin)-36 b(t)433 b(games.)2751 18901 y(Initial)528 b(examination)g(of)g(n)-36 b(umerical)527 b(v)-72 b(alues)527 b(of)h Fi(P)181 b Fh(\()p Fi(n;)221 b(k)45 b(;)221 b(p)p Fh(\))528 b(for)g(a)f(wide)h (range)f(of)h(v)-72 b(alues)527 b(of)h Fi(n)p Fh(,)551 b Fi(k)800 20506 y Fh(and)540 b Fi(p)g Fh(suggested)g(that)f(the)h (follo)-36 b(wing)542 b(conjectured)e(inequalities)h(migh)-36 b(t)540 b(b)36 b(e)540 b(univ)-36 b(ersally)541 b(true)f(and)800 22111 y(pro)-36 b(v)-72 b(able)434 b(\()p Fi(:)p Fh(5)369 b Fi(<)g(p)g(<)f Fh(1\):)p Black 800 24748 a Fg(Conjecture)499 b(1.)p Black 554 w Ff(If)464 b Fh(Maxp)36 b(oin)-36 b(ts\()p Fi(a;)221 b(b)p Fh(\))369 b Fi(>)g Fh(Maxp)36 b(oin)-36 b(ts\()p Fi(c;)221 b(d)p Fh(\))p Ff(,)465 b(then)f Fi(P)181 b Fh(\()p Fi(a;)221 b(b;)g(p)p Fh(\))369 b Fi(>)g(P)181 b Fh(\()p Fi(c;)221 b(d;)g(p)p Fh(\))p Ff(.)p Black 800 27384 a Fg(Conjecture)499 b(2.)p Black 554 w Ff(If)464 b Fi(ab)369 b Fh(=)f Fi(cd)465 b Ff(and)g Fh(min\()p Fi(a;)221 b(b)p Fh(\))369 b Fi(>)f Fh(min\()p Fi(c;)221 b(d)p Fh(\))p Ff(,)464 b(then)h Fi(P)181 b Fh(\()p Fi(a;)221 b(b)p Fh(\))369 b Fi(>)f(P)181 b Fh(\()p Fi(c;)221 b(d)p Fh(\))p Ff(.)2751 30021 y Fh(The)434 b(follo)-36 b(wing)435 b(computations)f(sho)-36 b(w)433 b(that)g(neither)g(of)i(these)e (conjectures)g(is)h(univ)-36 b(ersally)435 b(true:)3305 33914 y(Maxp)36 b(oin)-36 b(ts\(3)p Fi(;)221 b Fh(2\))370 b(=)e(15)1108 b Fi(P)181 b Fh(\(3)p Fi(;)221 b Fh(2)p Fi(;)g(:)p Fh(6\))371 b(=)e Fi(:)p Fh(7617)221 b Fe(\242)g(\242)g(\242) 3305 35519 y Fh(Maxp)36 b(oin)-36 b(ts\(1)p Fi(;)221 b Fh(7\))370 b(=)e(13)2341 b Fi(P)181 b Fh(\(7)p Fi(;)221 b(:)p Fh(6\))370 b(=)f Fi(:)p Fh(7711)221 b Fe(\242)g(\242)g(\242)3305 39635 y Fh(min)g(\(4)p Fi(;)g Fh(3\))370 b(=)e(3)1108 b Fi(P)181 b Fh(\(4)p Fi(;)221 b Fh(3)p Fi(;)g(:)p Fh(99\))371 b(=)e Fi(:)p Fh(999999999999999999670)221 b Fe(\242)g(\242)g(\242)3305 41240 y Fh(min)g(\(6)p Fi(;)g Fh(2\))370 b(=)e(2)1108 b Fi(P)181 b Fh(\(6)p Fi(;)221 b Fh(2)p Fi(;)g(:)p Fh(99\))371 b(=)e Fi(:)p Fh(999999999999999999676)221 b Fe(\242)g(\242)g(\242)800 45149 y Fn(4)2152 b(Remark)800 48069 y Fh(The)531 b(in)-36 b(tegers)530 b Fi(a)9163 48268 y Fc(k)24 b(;i)10314 48069 y Fh(,)555 b(whic)-36 b(h)530 b(pla)-36 b(y)531 b(a)g(signi\257can)-36 b(t)531 b(role)g(in)f(this)h(pap)36 b(er,)554 b(are)531 b(the)f(same)h(as)g(the)f(in)-36 b(tegers)800 49675 y Fi(a)1483 49874 y Fc(k)24 b Fd(+)p Fc(i)p Fb(\241)p Fd(1)p Fc(;k)g Fb(\241)p Fd(1)6838 49675 y Fh(in)554 b(A033820)i(of)g(the)e (On-line)f(Encyclop)36 b(edia)555 b(of)g(In)-36 b(teger)555 b(Sequences.)940 b(They)555 b(app)36 b(ear)554 b(in)800 51280 y(quite)434 b(di\256eren)-36 b(t)432 b(con)-36 b(texts)434 b(in)f([)p 0 1 0 0 TeXcolorcmyk(1)p (#cite.ref1) [[218 255 224 267] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(,)p 0 1 0 0 TeXcolorcmyk 434 w(2)p (#cite.ref2) [[231 255 237 267] [1 1 1 [3 3]] [0 0 1]] pdfm Black(].)800 55704 y Fn(References)p Black 800 58624 a Fh([1])p Black 651 w(A.)444 b(Burstein,)i(En)-36 b(umeration)443 b(of)h(w)-36 b(ords)444 b(with)f(forbidden)g(patterns,)j(Ph.)d(D.)h (Thesis,)j(U.)d(of)g(P)-36 b(enn-)2823 60229 y(sylv)-72 b(ania,)436 b(1998.)p Black 800 62916 a([2])p Black 651 w(I.)e(Gessel,)g(Sup)36 b(er)433 b(ballot)h(n)-36 b(um)g(b)36 b(ers,)432 b Ff(J.)465 b(Symb)-66 b(olic)463 b(Computation)432 b Fg(14)i Fh(\(1992\),)h(179{194.)p 800 65909 52000 45 v 800 68110 a(2000)g Ff(Mathematics)464 b(Subje)-66 b(ct)463 b(Classi\257c)-66 b(ation)p Fh(:)577 b(60C05.)800 69715 y Ff(Keywor)-66 b(ds:)653 b Fh(games,)434 b(inequalities,)h(probabilit) -36 b(y)-108 b(,)434 b(sets.)p 800 71296 V Black 26150 74617 a(11)p Black eop %%Page: 12 12 12 11 bop Black 0 TeXcolorgray Black Black 800 1424 a Fh(\(Concerned)433 b(with)h(sequence)p 0 1 0 0 TeXcolorcmyk 433 w(A033820)p 16090 1637 4878 54 v [[217 704 261 716] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/cgi-bin/access.cgi/as/ ~njas/sequences/eisA.cgi?Anum=A033820) pdfm Black 2 w(.\))p 800 3129 52000 45 v 800 6180 a(Receiv)-36 b(ed)432 b(July)h(29)f(2003;)i(revised)e(v)-36 b(ersion)432 b(receiv)-36 b(ed)432 b(No)-36 b(v)g(em)g(b)36 b(er)432 b(24)g(2003.)579 b(Published)431 b(in)h Ff(Journal)463 b(of)800 7785 y(Inte)-66 b(ger)463 b(Se)-66 b(quenc)g(es)p Fh(,)431 b(Decem)-36 b(b)36 b(er)434 b(6)g(2003.)p 800 9416 V 800 11667 a(Return)f(to)p 0 1 0 0 TeXcolorcmyk 433 w(Journal)h(of)g(In)-36 b(teger)434 b(Sequences)f(home)g(page)p [[133 612 338 624] [1 1 1 [3 3]] [0 0 1]] (http://www.math.uwaterloo.ca/JIS/) pdfm Black(.)p Black 26150 74617 a(12)p Black eop %%Trailer end end