%%Page: 1 1 1 0 bop Black 0 TeXcolorgray Black 52150 -2672 a Fw(1)p 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.1.7) 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 5710 11461 a Fv(A)861 b(Note)i(on)e(Rational)i (Succession)e(Rules)22313 16603 y Fu(Enrica)520 b(Duc)-43 b(hi)6697 18596 y(Dipartimen)g(to)519 b(di)h(Sistemi)f(e)h (Informatica,)g(Via)g(Lom)-43 b(broso)521 b(6/17)20005 20588 y(50134)h(Firenze,)c(Italy)p 0 1 0 0 TeXcolorcmyk 19418 22581 a Ft(duchi@dsi.unifi.it)p [[247 514 380 526] [1 1 1 [3 3]] [0 0 1]] (mailto:duchi@dsi.unifi.it) pdfm Black 21734 26566 a Fu(Andrea)j(F)-130 b(rosini)9448 28559 y(Dipartimen)-43 b(to)519 b(di)h(Matematica,)g(Via)g(del)g (Capitano,)h(15)20687 30551 y(53100)h(Siena,)e(Italy)p 0 1 0 0 TeXcolorcmyk 20238 32544 a Ft(frosini@unisi.it)p [[254 424 372 436] [1 1 1 [3 3]] [0 0 1]] (mailto:frosini@unisi.it) pdfm Black 21879 36529 a Fu(Renzo)g(Pinzani)6697 38521 y(Dipartimen)-43 b(to)519 b(di)h(Sistemi)f(e)h(Informatica,)g(Via)g(Lom)-43 b(broso)521 b(6/17)20005 40514 y(50134)h(Firenze,)c(Italy)p 0 1 0 0 TeXcolorcmyk 18597 42506 a Ft(pinzani@dsi.unifi.it)p [[239 334 387 346] [1 1 1 [3 3]] [0 0 1]] (mailto:pinzani@dsi.unifi.it) pdfm Black 21587 46491 a Fu(Simone)h(Rinaldi)9448 48484 y(Dipartimen)-43 b(to)519 b(di)h(Matematica,)g(Via)g(del)g(Capitano,)h(15)20687 50476 y(53100)h(Siena,)e(Italy)p 0 1 0 0 TeXcolorcmyk 20238 52469 a Ft(rinaldi@unisi.it)p [[254 245 372 257] [1 1 1 [3 3]] [0 0 1]] (mailto:rinaldi@unisi.it) pdfm Black Black Black 24133 56988 a Fs(Abstract)p Black Black 5870 59236 a Fr(Succession)509 b(rules)f(ha)-34 b(ving)510 b(a)e(rational)h(generating)g(function)h(are)e(usually)h(called)f Fq(r)-62 b(ational)4052 60741 y(suc)g(c)g(ession)406 b(rules)p Fr(.)529 b(In)378 b(this)h(note)g(w)-34 b(e)378 b(discuss)h(some)f(problems)h(concerning)f(rational)g(succession)4052 62247 y(rules,)389 b(and)f(determine)f(a)g(simple)f(metho)34 b(d)388 b(to)f(pass)h(from)f(a)g(rational)g(generating)g(function)h(to) f(a)4052 63752 y(rational)404 b(succession)g(rule,)f(b)34 b(oth)405 b(de\257ning)g(the)g(same)f(n)-34 b(um)g(b)34 b(er)405 b(sequence.)p Black Black eop %%Page: 2 2 2 1 bop Black 0 TeXcolorgray Black 52150 -2672 a Fw(2)p Black 800 1424 a Fp(1)2152 b(In)-60 b(tro)60 b(duction)2751 5950 y Fw(A)584 b Fo(suc)-66 b(c)g(ession)603 b(rule)585 b Fw(is)g(a)g(formal)g(system)g(de\257ned)e(b)-36 b(y)584 b(an)h Fo(axiom)683 b Fw(\()p Fn(a)p Fw(\),)622 b Fn(a)k Fm(2)f Fl(N)43885 5468 y Fk(+)44673 5950 y Fw(,)d(and)584 b(a)h(set)f(of)800 7555 y Fo(pr)-66 b(o)g(ductions)14277 9160 y Fm(f)p Fw(\()p Fn(k)16123 9359 y Fj(t)16519 9160 y Fw(\))369 b Fi(\303)g Fw(\()p Fn(e)20200 9359 y Fk(1)20725 9160 y Fw(\()p Fn(k)21907 9359 y Fj(t)22303 9160 y Fw(\)\)\()p Fn(e)24424 9359 y Fk(2)24949 9160 y Fw(\()p Fn(k)26131 9359 y Fj(t)26526 9160 y Fw(\)\))221 b Fm(\242)g(\242)g(\242)h Fw(\()p Fn(e)30639 9359 y Fj(k)31129 9470 y Fh(t)31556 9160 y Fw(\()p Fn(k)32738 9359 y Fj(t)33134 9160 y Fw(\)\))368 b(:)i Fn(t)e Fm(2)h Fl(N)p Fm(g)p Fn(;)800 11337 y Fw(where)289 b Fn(e)5016 11536 y Fj(i)5761 11337 y Fw(:)369 b Fl(N)7450 10855 y Fk(+)8606 11337 y Fm(\241)-221 b(!)369 b Fl(N)12074 10855 y Fk(+)12862 11337 y Fw(,)318 b(whic)-36 b(h)289 b(explains)h(ho)-36 b(w)289 b(to)g(deriv)-36 b(e)289 b(the)g Fo(suc)-66 b(c)g(essors)399 b Fw(\()p Fn(e)38997 11536 y Fk(1)39523 11337 y Fw(\()p Fn(k)45 b Fw(\)\))p Fn(;)221 b Fw(\()p Fn(e)43453 11536 y Fk(2)43978 11337 y Fw(\()p Fn(k)45 b Fw(\)\))p Fn(;)221 b(:)g(:)g(:)i(;)e Fw(\()p Fn(e)50238 11536 y Fj(k)50728 11647 y Fh(t)51156 11337 y Fw(\()p Fn(k)45 b Fw(\)\))800 12942 y(of)403 b(an)-36 b(y)402 b(giv)-36 b(en)403 b(lab)36 b(el)403 b(\()p Fn(k)45 b Fw(\),)408 b Fn(k)414 b Fm(2)369 b Fl(N)16958 12460 y Fk(+)17745 12942 y Fw(.)568 b(In)402 b(general,)409 b(for)403 b(a)f(succession)g(rule)g(\255,)409 b(w)-36 b(e)402 b(use)g(the)g(more)g(compact)800 14547 y(notation:)15317 16595 y(\255)370 b(:)17356 14722 y Fg(\275)18906 15781 y Fw(\()p Fn(a)p Fw(\))18906 17386 y(\()p Fn(k)45 b Fw(\))368 b Fi(\303)i Fw(\()p Fn(e)23814 17585 y Fk(1)24339 17386 y Fw(\()p Fn(k)45 b Fw(\)\))433 b(\()p Fn(e)28120 17585 y Fk(2)28646 17386 y Fw(\()p Fn(k)45 b Fw(\)\))442 b Fm(\242)221 b(\242)g(\242)443 b Fw(\()p Fn(e)34428 17585 y Fj(k)34997 17386 y Fw(\()p Fn(k)45 b Fw(\)\))p Fn(:)51138 16595 y Fw(\(1\))2751 19546 y(The)464 b Fo(lab)-66 b(els)464 b Fw(\()p Fn(a)p Fw(\),)472 b(\()p Fn(k)45 b Fw(\),)472 b(\()p Fn(e)15111 19745 y Fj(i)15486 19546 y Fw(\()p Fn(k)45 b Fw(\)\))464 b(of)h(\255)f(are)h(assumed)e(to)i(con)-36 b(tain)464 b(only)h(p)36 b(ositiv)-36 b(e)465 b(in)-36 b(tegers.)670 b(The)464 b(rule)800 21151 y(\255)407 b(can)f(b)36 b(e)406 b(represen)-36 b(ted)405 b(b)-36 b(y)406 b(means)g(of)i(a)e Fo(gener)-66 b(ating)437 b(tr)-66 b(e)g(e)p Fw(,)411 b(that)406 b(is,)412 b(a)407 b(ro)36 b(oted)406 b(tree)g(whose)h(v)-36 b(ertices)407 b(are)800 22757 y(lab)36 b(elled)468 b(with)f(the)g(lab) 36 b(els)468 b(of)g(\255:)646 b(\()p Fn(a)p Fw(\))466 b(is)i(the)f(lab)36 b(el)467 b(of)h(the)f(ro)36 b(ot,)476 b(and)467 b(eac)-36 b(h)467 b(no)36 b(de)467 b(lab)36 b(elled)468 b(\()p Fn(k)45 b Fw(\))467 b(has)g Fn(k)800 24362 y Fw(c)-36 b(hildren)432 b(lab)36 b(elled)434 b(b)-36 b(y)433 b Fn(e)12963 24561 y Fk(1)13489 24362 y Fw(\()p Fn(k)45 b Fw(\))p Fn(;)221 b(:)g(:)g(:)i(;)e(e)18737 24561 y Fj(k)19307 24362 y Fw(\()p Fn(k)45 b Fw(\))433 b(resp)36 b(ectiv)-36 b(ely)-108 b(,)434 b(according)f(to)h(the)e(pro) 36 b(duction)433 b(of)h(\()p Fn(k)45 b Fw(\))433 b(de\257ned)800 25967 y(in)489 b(\()p 0 1 0 0 TeXcolorcmyk(1)p (#equation.1) [[98 483 104 495] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\).)744 b(A)489 b(succession)g(rule)f(\255)h(de\257nes)f(a)h (sequence)g(of)h(p)36 b(ositiv)-36 b(e)489 b(in)-36 b(tegers)489 b(\()p Fn(f)40237 26166 y Fj(n)40863 25967 y Fw(\))41369 26166 y Fj(n)p Ff(\270)p Fk(0)43198 25967 y Fw(,)503 b(where)488 b Fn(f)48515 26166 y Fj(n)49630 25967 y Fw(is)i(the)800 27572 y(n)-36 b(um)g(b)36 b(er)363 b(of)i(the)f(no)36 b(des)365 b(at)f(lev)-36 b(el)366 b Fn(n)f Fw(in)f(the)g(generating)h (tree)f(de\257ned)f(b)-36 b(y)365 b(\255.)555 b(By)365 b(con)-36 b(v)g(en)g(tion)365 b(the)f(ro)36 b(ot)365 b(is)800 29177 y(at)384 b(lev)-36 b(el)386 b(0,)394 b(so)385 b Fn(f)8848 29376 y Fk(0)9743 29177 y Fw(=)368 b(1.)563 b(The)384 b(function)g Fn(f)21007 29376 y Fk(\255)21742 29177 y Fw(\()p Fn(x)p Fw(\))368 b(=)25242 28181 y Fg(P)26644 29564 y Fj(n)p Ff(\270)p Fk(0)28694 29177 y Fn(f)29335 29376 y Fj(n)29961 29177 y Fn(x)30700 28695 y Fj(n)31711 29177 y Fw(is)384 b(the)g Fo(gener)-66 b(ating)417 b(function)382 b Fw(determined)800 30782 y(b)-36 b(y)434 b(\255.)2751 32387 y(Succession)499 b(rules)f(are)h(closely)h(related)f(to)g(a)g (metho)36 b(d)498 b(for)i(the)e(en)-36 b(umeration)498 b(and)g(generation)h(of)800 33992 y(com)-36 b(binatorial)506 b(structures,)523 b(called)506 b(the)e Fo(ECO)532 b(metho)-66 b(d)p Fw(.)793 b(F)-108 b(or)505 b(further)f(details)i(and)f(examples)h (ab)36 b(out)800 35597 y(succession)509 b(rules)f(and)g(the)h(ECO)f (metho)36 b(d)508 b(w)-36 b(e)509 b(refer)g(to)g([)p 0 1 0 0 TeXcolorcmyk(BDLPP)p (#cite.ECO) [[346 397 386 409] [1 1 1 [3 3]] [0 0 1]] pdfm Black(];)547 b(in)508 b([)p 0 1 0 0 TeXcolorcmyk(FPPR)p (#cite.FPPR) [[415 397 447 409] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])h(the)f(authors)h(study)800 37202 y(succession)434 b(rules)f(from)h(an)g(algebraic)g(p)36 b(oin)-36 b(t)433 b(of)i(view.)2751 38807 y(Tw)-36 b(o)447 b(rules)f(are)h Fo(e)-66 b(quivalent)444 b Fw(if)k(they)e(ha)-36 b(v)g(e)446 b(the)g(same)h(generating)f(function.)617 b(A)446 b(succession)h(rule)f (is)800 40413 y Fo(\257nite)432 b Fw(if)i(it)g(has)f(a)h(\257nite)f(n) -36 b(um)g(b)36 b(er)432 b(of)i(lab)36 b(els)435 b(and)e(pro)36 b(ductions;)433 b(for)h(example,)g(the)g(rule)21052 42145 y Fg(8)21052 43340 y(<)21052 45732 y(:)22786 43252 y Fw(\(2\))22786 44857 y(\(2\))369 b Fi(\303)h Fw(\(2\)\(3\))22786 46462 y(\(3\))f Fi(\303)h Fw(\(2\)\(3\)\(3\))p Fn(;)51138 44868 y Fw(\(2\))800 48622 y(de\257ning)495 b(o)36 b(dd-index)495 b(Fib)36 b(onacci)496 b(n)-36 b(um)g(b)36 b(ers)494 b(1)p Fn(;)221 b Fw(2)p Fn(;)g Fw(5)p Fn(;)g Fw(13)p Fn(;)g Fw(34)p Fn(;)g Fw(89)p Fn(;)g Fw(233)p Fn(;)g(:)g(:)g(:)506 b Fw(\(sequence)495 b(A001519)j(in)d([)p 0 1 0 0 TeXcolorcmyk(SL)p (#cite.Sl) [[526 279 539 291] [1 1 1 [3 3]] [0 0 1]] pdfm Black(]\))800 50227 y(is)434 b(\257nite)f(and)g(it)h(is)f(equiv)-72 b(alen)-36 b(t)435 b(to)19893 52007 y Fg(\275)21443 53067 y Fw(\(2\))21443 54672 y(\()p Fn(k)45 b Fw(\))368 b Fi(\303)i Fw(\(2\))26904 54190 y Fj(k)24 b Ff(\241)p Fk(1)28675 54672 y Fw(\()p Fn(k)340 b Fw(+)295 b(2\))p Fn(;)51138 53880 y Fw(\(3\))800 56758 y(whic)-36 b(h)433 b(is)h(not)g(\257nite.) 2751 58929 y(Figure)p 0 1 0 0 TeXcolorcmyk 511 w(1)p (#figure.1) [[134 187 140 199] [1 1 1 [3 3]] [0 0 1]] pdfm Black 512 w(depicts)511 b(the)g(\257rst)g(lev)-36 b(els)513 b(of)f(the)f(generating)h(trees)f(asso)36 b(ciated)513 b(with)e(the)g(rules)h(in)f(\()p 0 1 0 0 TeXcolorcmyk(2)p (#equation.2) [[537 187 543 199] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))800 60534 y(and)433 b(\()p 0 1 0 0 TeXcolorcmyk(3)p (#equation.3) [[107 172 112 184] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\).)2751 62705 y(According)622 b(to)f(our)h(de\257nition,)667 b(t)-36 b(w)g(o)622 b(lab)36 b(els)622 b(con)-36 b(taining)622 b(the)f(same)h(in)-36 b(teger)621 b Fn(k)667 b Fw(are)621 b(allo)-36 b(w)g(ed)623 b(to)800 64310 y(ha)-36 b(v)g(e)478 b(a)h(di\256eren)-36 b(t)477 b(pro)36 b(duction.)711 b(If)478 b(this)g(happ)36 b(ens)477 b(w)-36 b(e)479 b(distinguish)e (those)h(lab)36 b(els)479 b(using)f(some)g(indices)800 65915 y(\(or)535 b Fo(c)-66 b(olors)p Fw(,)560 b(see)535 b(Example)p 0 1 0 0 TeXcolorcmyk 535 w(1)p (#esempio.1) [[206 124 212 136] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\).)882 b(A)534 b(succession)h(rule)g(is)g(called)g Fo(r)-66 b(ational)p Fw(,)559 b Fo(algebr)-66 b(aic)533 b Fw(or)i Fo(tr)-66 b(asc)g(endental)800 67520 y Fw(according)457 b(to)g(the)f(generating)h(function)f(t)-36 b(yp)36 b(e.)648 b(Rational)457 b(succession)g(rules)g(are)f(the)g(sub)72 b(ject)457 b(of)g(this)800 69125 y(note)433 b(\(see)h(also)h([)p 0 1 0 0 TeXcolorcmyk(GF)-36 b(GT)p (#cite.GFGT) [[155 95 190 107] [1 1 1 [3 3]] [0 0 1]] pdfm Black -1 w(],)434 b([)p 0 1 0 0 TeXcolorcmyk(FPPR)p (#cite.FPPR) [[203 95 235 107] [1 1 1 [3 3]] [0 0 1]] pdfm Black(]\).)2751 71296 y(Belo)-36 b(w)435 b(w)-36 b(e)433 b(list)h(some)g(classes)h(of)f(generating)g(functions:)p Black Black eop %%Page: 3 3 3 2 bop Black 0 TeXcolorgray Black 52150 -2672 a Fw(3)p Black Black 10800 96 a 18945146 6251895 0 0 29470228 9801482 startTexFig doclip 10800 96 a%%BeginDocument: array.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: array.eps %%Creator: fig2dev Version 3.2 Patchlevel 3d %%CreationDate: Tue Apr 22 11:23:58 2003 %%For: rinaldi@homelinux (Rinaldi Simone) %%BoundingBox: 0 0 448 149 %%Magnification: 1.0000 %%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 149 moveto 0 0 lineto 448 0 lineto 448 149 lineto closepath clip newpath -18.0 161.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 /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin 10 setmiterlimit 0.06000 0.06000 sc % % Fig objects follow % % Polyline 7.500 slw n 6300 900 m 5700 1500 l gs col0 s gr % Polyline n 6300 900 m 6900 1500 l gs col0 s gr % Polyline n 6975 1800 m 6975 2400 l gs col0 s gr % Polyline n 6975 1800 m 7575 2400 l gs col0 s gr % Polyline n 6975 1800 m 6375 2400 l gs col0 s gr % Polyline n 5625 1800 m 5850 2400 l gs col0 s gr % Polyline n 5550 1800 m 5250 2400 l gs col0 s gr % Polyline n 1950 900 m 1350 1500 l gs col0 s gr % Polyline n 1950 900 m 2550 1500 l gs col0 s gr % Polyline n 2625 1800 m 2625 2400 l gs col0 s gr % Polyline n 2625 1800 m 3225 2400 l gs col0 s gr % Polyline n 2625 1800 m 2025 2400 l gs col0 s gr % Polyline n 1275 1800 m 1500 2400 l gs col0 s gr % Polyline n 1200 1800 m 900 2400 l gs col0 s gr /Times-Italic ff 210.00 scf sf 6225 825 m gs 1 -1 sc (\(2\)) col0 sh gr /Times-Italic ff 210.00 scf sf 5490 1725 m gs 1 -1 sc (\(2\)) col0 sh gr /Times-Italic ff 210.00 scf sf 6225 2625 m gs 1 -1 sc (\(2\)) col0 sh gr /Times-Italic ff 210.00 scf sf 5100 2625 m gs 1 -1 sc (\(2\)) col0 sh gr /Times-Italic ff 210.00 scf sf 6900 1725 m gs 1 -1 sc (\(3\)) col0 sh gr /Times-Italic ff 210.00 scf sf 5775 2625 m gs 1 -1 sc (\(3\)) col0 sh gr /Times-Italic ff 210.00 scf sf 1875 825 m gs 1 -1 sc (\(2\)) col0 sh gr /Times-Italic ff 210.00 scf sf 1140 1725 m gs 1 -1 sc (\(2\)) col0 sh gr /Times-Italic ff 210.00 scf sf 1875 2625 m gs 1 -1 sc (\(2\)) col0 sh gr /Times-Italic ff 210.00 scf sf 750 2625 m gs 1 -1 sc (\(2\)) col0 sh gr /Times-Italic ff 210.00 scf sf 2550 1725 m gs 1 -1 sc (\(3\)) col0 sh gr /Times-Italic ff 210.00 scf sf 2475 2625 m gs 1 -1 sc (\(3\)) col0 sh gr /Times-Italic ff 210.00 scf sf 3150 2625 m gs 1 -1 sc (\(3\)) col0 sh gr /Times-Italic ff 210.00 scf sf 1425 2625 m gs 1 -1 sc (\(3\)) col0 sh gr /Times-Italic ff 240.00 scf sf 300 375 m gs 1 -1 sc (\(a\)) col0 sh gr /Times-Italic ff 240.00 scf sf 4650 375 m gs 1 -1 sc (\(b\)) col0 sh gr /Times-Italic ff 210.00 scf sf 6825 2625 m gs 1 -1 sc (\(2\)) col0 sh gr /Times-Italic ff 210.00 scf sf 7500 2625 m gs 1 -1 sc (\(4\)) col0 sh gr $F2psEnd rs %%EndDocument endTexFig Black 9781 13368 a Fw(Figure)434 b(1:)p 0 TeXcolorgray Black 579 w(The)f(\257rst)g(lev)-36 b(els)435 b(of)f(t)-36 b(w)g(o)434 b(equiv)-72 b(alen)-36 b(t)434 b(generating)g(trees.)p Black Black Black 800 17168 a Fe(-)p Black 651 w Fm(R)553 b Fw(is)h(the)f(set)g(of)h(rational)h(generating)e(functions)h(of)g(in) -36 b(teger)553 b(sequences)h(\()p Fn(Z)95 b Fw(-rational)554 b(functions,)4052 18773 y(using)433 b(the)g(notation)h(in)f([)p 0 1 0 0 TeXcolorcmyk(SS)p (#cite.SS) [[223 548 236 560] [1 1 1 [3 3]] [0 0 1]] pdfm Black(]\);)p Black 800 21486 a Fe(-)p Black 651 w Fm(R)3075 21003 y Fk(+)4295 21486 y Fw(is)h(the)f(set)g(of)i(rational)f (generating)g(functions)f(of)i(p)36 b(ositiv)-36 b(e)434 b(in)-36 b(teger)433 b(sequences;)p Black 800 24198 a Fe(-)p Black 651 w Fn(R)11 b(E)78 b(G)433 b Fw(is)h(the)f(set)g(of)h (generating)g(functions)f(of)i(regular)f(languages;)p Black 800 26910 a Fe(-)p Black 651 w Fm(S)533 b Fw(is)434 b(the)f(set)g(of)i(rational)f(generating)g(functions)f(of)i(succession) e(rules;)p Black 800 29622 a Fe(-)p Black 651 w Fm(F)565 b Fw(is)434 b(the)f(set)g(of)h(generating)g(functions)g(of)g(\257nite)f (succession)g(rules.)2751 32666 y(Summarizing)g(the)g(results)h(in)f([) p 0 1 0 0 TeXcolorcmyk(SS)p (#cite.SS) [[242 423 255 435] [1 1 1 [3 3]] [0 0 1]] pdfm Black -1 w(],)i([)p 0 1 0 0 TeXcolorcmyk(FPPR)p (#cite.FPPR) [[269 423 301 435] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])f(w)-36 b(e)434 b(obtain)f(the)g(follo)-36 b(wing)436 b(sc)-36 b(heme:)22847 36053 y Fn(R)11 b(E)78 b(G)26686 37610 y gsave currentpoint currentpoint translate -45 neg rotate neg exch neg exch translate 26686 37610 a Fm(\275)27719 37610 y currentpoint grestore moveto 27719 37610 a 18439 40336 a Fm(F)21493 38386 y gsave currentpoint currentpoint translate 45 neg rotate neg exch neg exch translate 21493 38386 a Fm(\275)22526 38386 y currentpoint grestore moveto 22526 38386 a 21127 41930 a gsave currentpoint currentpoint translate -45 neg rotate neg exch neg exch translate 21127 41930 a Fm(\265)22160 41930 y currentpoint grestore moveto 22160 41930 a 29235 40391 a Fm(R)30361 39909 y Fk(+)32443 40104 y Ff(\275)34469 40336 y Fm(R)23928 44620 y(S)26977 42756 y gsave currentpoint currentpoint translate 45 neg rotate neg exch neg exch translate 26977 42756 a Fm(\275)28011 42756 y currentpoint grestore moveto 28011 42756 a 2751 47408 a Fw(The)566 b(classes)i Fm(R)p Fw(,)599 b Fn(R)11 b(E)78 b(G)p Fw(,)599 b(and)566 b Fm(F)698 b Fw(are)567 b(decidable,)599 b(while)567 b Fm(R)33451 46926 y Fk(+)34805 47408 y Fw(is)f(not)g(decidable.)977 b(In)566 b([)p 0 1 0 0 TeXcolorcmyk(FPPR)p (#cite.FPPR) [[499 290 531 302] [1 1 1 [3 3]] [0 0 1]] pdfm Black(])h(is)800 49013 y(conjectured)433 b(that)g Fm(F)501 b Fw(=)368 b Fm(S)100 b Fw(,)434 b(i.e.,)h(ev)-36 b(ery)434 b(rational)h(rule)e(is)h(equiv)-72 b(alen)-36 b(t)434 b(to)g(a)g(\257nite)f(one.)2751 50618 y(This)366 b(note)f(prop)36 b(oses)365 b(a)h(simple)f(to)36 b(ol)367 b(to)e(pass)h(from)f(a)h (rational)g(generating)g(function)f(\(i.e.,)380 b(a)366 b(linear)800 52223 y(recurrence)498 b(relation\))h(de\257ning)f(a)h (non-decreasing)f(sequence)h(of)g(p)36 b(ositiv)-36 b(e)500 b(in)-36 b(tegers)499 b(to)g(a)g(succession)800 53828 y(rule)433 b(de\257ning)g(the)g(same)h(sequence.)578 b(The)434 b(results)f(extend)g(those)h(in)f([GF)-36 b(GT].)2751 55433 y(F)-108 b(urthermore)508 b(our)i(tec)-36 b(hnique)510 b(pro)-36 b(vides)510 b(in)-36 b(teresting)510 b(com)-36 b(binatorial)511 b(in)-36 b(terpretations)510 b(\(in)f(terms)800 57038 y(of)468 b(generating)g(trees\))g(for)g(sequences)g(that)f(are)h (de\257ned)e(b)-36 b(y)468 b(a)g(linear)g(recurrence)f(relation,)477 b(using)467 b(an)800 58644 y(approac)-36 b(h)433 b(di\256eren)-36 b(t)433 b(from)h(that)f(in)g([)p 0 1 0 0 TeXcolorcmyk(BDFR)p (#cite.BDFR) [[246 189 279 201] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(])h(and)f([)p 0 1 0 0 TeXcolorcmyk(BR)p (#cite.BR) [[312 189 329 201] [1 1 1 [3 3]] [0 0 1]] pdfm Black(].)2751 60249 y(As)527 b(an)g(application)h(of)g(our)e(metho)36 b(d,)551 b(w)-36 b(e)527 b(giv)-36 b(e)528 b(a)g(simple)f(solution)g (to)g(a)h(problem)f(prop)36 b(osed)526 b(b)-36 b(y)800 61854 y(Jim)421 b(Propp)e(on)h(the)g(mailing)h(list)f(\\domino")h (\(1999\),)j(where)c(he)g(ask)-36 b(ed)421 b(for)f(the)g(com)-36 b(binatorial)421 b(in)-36 b(ter-)800 63459 y(pretation)443 b(of)i(the)e(sequence)h(1)p Fn(;)221 b Fw(1)p Fn(;)g Fw(1)p Fn(;)g Fw(2)p Fn(;)g Fw(3)p Fn(;)g Fw(7)p Fn(;)g Fw(11)p Fn(;)g Fw(26)p Fn(;)g(:)g(:)g(:)454 b Fw(\(sequence)444 b(A005246)i(in)d([)p 0 1 0 0 TeXcolorcmyk(SL)p (#cite.Sl) [[449 146 462 158] [1 1 1 [3 3]] [0 0 1]] pdfm Black(]\))h(de\257ned)e(b)-36 b(y)444 b(the)800 65064 y(linear)434 b(recurrence)f(relation:)15723 66844 y Fg(\275)17273 67903 y Fn(f)17914 68102 y Fk(0)18809 67903 y Fw(=)369 b(1)p Fn(;)1522 b(f)23364 68102 y Fk(1)24259 67903 y Fw(=)369 b(1)p Fn(;)1522 b(f)28814 68102 y Fk(2)29709 67903 y Fw(=)369 b(1)p Fn(;)1523 b(f)34265 68102 y Fk(3)35160 67903 y Fw(=)368 b(2)17273 69508 y Fn(f)17914 69707 y Fj(n)18909 69508 y Fw(=)h(4)p Fn(f)21581 69707 y Fj(n)p Ff(\241)p Fk(2)23705 69508 y Fm(\241)296 b Fn(f)25675 69707 y Fj(n)p Ff(\241)p Fk(4)27503 69508 y Fn(:)p Black Black eop %%Page: 4 4 4 3 bop Black 0 TeXcolorgray Black 52150 -2672 a Fw(4)p Black 800 1424 a Fp(2)2152 b(Tw)-60 b(o)717 b(term)g(linear)g (recurrences.)2751 5950 y Fw(W)-108 b(e)434 b(start)f(b)-36 b(y)433 b(considering)h(t)-36 b(w)g(o-term)433 b(linear)h(recurrences:) 16334 8757 y Fn(f)16975 8956 y Fj(n)17970 8757 y Fw(=)369 b Fn(h)20100 8956 y Fk(1)20625 8757 y Fn(f)21266 8956 y Fj(n)p Ff(\241)p Fk(1)23390 8757 y Fw(+)295 b Fn(h)25446 8956 y Fk(2)25972 8757 y Fn(f)26613 8956 y Fj(n)p Ff(\241)p Fk(2)28441 8757 y Fn(;)2823 b(h)32374 8956 y Fk(1)32900 8757 y Fn(;)221 b(h)34231 8956 y Fk(2)35126 8757 y Fm(2)369 b Fl(Z)800 11565 y Fw(with)487 b(initial)h(conditions)e Fn(f)14542 11764 y Fk(0)15528 11565 y Fw(=)459 b(1,)501 b Fn(f)19152 11764 y Fk(1)20137 11565 y Fw(=)459 b Fn(s)22221 11764 y Fk(0)23206 11565 y Fm(2)g Fl(N)25510 11083 y Fk(+)26298 11565 y Fw(.)738 b(The)487 b(p)36 b(ositivit)-36 b(y)488 b(of)f(the)g(sequence)f(is)i(ensured)d(b)-36 b(y)800 13170 y(the)433 b(additional)h(conditions)g Fn(h)16153 13369 y Fk(1)17047 13170 y Fm(2)369 b Fl(N)19261 12688 y Fk(+)20048 13170 y Fw(,)434 b(and)f Fn(h)24121 13369 y Fk(1)24942 13170 y Fw(+)295 b Fn(h)26998 13369 y Fk(2)27892 13170 y Fn(>)369 b Fw(0.)p Black 800 16070 a Fe(Prop)42 b(osition)500 b(1)p Black 650 w Fo(The)465 b(suc)-66 b(c)g(ession)464 b(rule)18562 19723 y Fw(\255)370 b(=)21251 17850 y Fg(\275)22801 18909 y Fw(\()p Fn(s)23920 19108 y Fk(0)24445 18909 y Fw(\))22801 20514 y(\()p Fn(k)45 b Fw(\))369 b Fd(;)g Fw(\(1\))28262 20032 y Fj(k)24 b Ff(\241)p Fk(1)30255 20514 y Fw(\()o Fn(\301)p Fw(\()p Fn(k)45 b Fw(\)\))221 b Fn(;)800 23397 y Fo(with)465 b Fn(\301)p Fw(\()p Fn(k)45 b Fw(\))368 b(=)h(\()p Fn(h)9130 23596 y Fk(1)9950 23397 y Fm(\241)296 b Fw(1\))p Fn(k)340 b Fw(+)295 b Fn(h)15507 23596 y Fk(2)16328 23397 y Fw(+)g(1)p Fo(,)464 b(de\257nes)g(the)h(se)-66 b(quenc)g(e)463 b Fw(\()p Fn(f)32051 23596 y Fj(n)32677 23397 y Fw(\))33183 23596 y Fj(n)p Ff(\270)p Fk(0)35012 23397 y Fo(.)800 26297 y Fe(Pro)42 b(of.)577 b Fw(W)-108 b(e)431 b(ha)-36 b(v)g(e)431 b Fn(f)11290 26496 y Fk(0)12184 26297 y Fw(=)369 b(1)431 b(and)f Fn(f)17813 26496 y Fk(1)18708 26297 y Fw(=)369 b Fn(s)20702 26496 y Fk(0)21227 26297 y Fw(.)578 b(Let)430 b Fn(k)25169 26496 y Fk(1)25695 26297 y Fn(;)443 b(k)27175 26496 y Fk(2)27702 26297 y Fn(;)221 b(:)g(:)g(:)i(;)e(k)31290 26496 y Fj(f)31742 26619 y Fh(n)p Fc(\241)p Fb(2)33841 26297 y Fw(b)36 b(e)431 b(the)f(lab)36 b(els)431 b(at)g(lev)-36 b(el)432 b Fn(n)290 b Fm(\241)f Fw(2)431 b(of)h(the)800 27902 y(generating)i(tree)f(of)h(\255.)579 b(Then,)434 b(for)g Fn(n)369 b Fm(\270)g Fw(2,)3616 30709 y Fn(f)4257 30908 y Fj(n)5253 30709 y Fw(=)f Fn(k)7309 30908 y Fk(1)8131 30709 y Fw(+)295 b Fn(k)10114 30908 y Fk(2)10935 30709 y Fw(+)g Fm(\242)221 b(\242)g(\242)296 b Fw(+)f Fn(k)16070 30908 y Fj(f)16522 31031 y Fh(n)p Fc(\241)p Fb(2)18485 30709 y Fm(\241)g Fn(f)20454 30908 y Fj(n)p Ff(\241)p Fk(2)22578 30709 y Fw(+)g(\()p Fn(h)25140 30908 y Fk(1)25960 30709 y Fm(\241)g Fw(1\)\()p Fn(k)29626 30908 y Fk(1)30448 30709 y Fw(+)g Fn(k)32431 30908 y Fk(2)33252 30709 y Fw(+)g Fm(\242)221 b(\242)g(\242)296 b Fw(+)f Fn(k)38387 30908 y Fj(f)38839 31031 y Fh(n)p Fc(\241)p Fb(2)40507 30709 y Fw(\))g(+)f Fn(f)43255 30908 y Fj(n)p Ff(\241)p Fk(2)45084 30709 y Fw(\()p Fn(h)46339 30908 y Fk(2)47160 30709 y Fw(+)g(1\))p Fn(:)2751 33517 y Fw(Consequen)-36 b(tly)434 b(w)-36 b(e)434 b(ha)-36 b(v)g(e)4820 36324 y Fn(f)5461 36523 y Fj(n)6456 36324 y Fw(=)369 b Fn(f)8478 36523 y Fj(n)p Ff(\241)p Fk(1)10602 36324 y Fm(\241)295 b Fn(f)12571 36523 y Fj(n)p Ff(\241)p Fk(2)14695 36324 y Fw(+)g(\()p Fn(h)17257 36523 y Fk(1)18077 36324 y Fm(\241)g Fw(1\))p Fn(f)21202 36523 y Fj(n)p Ff(\241)p Fk(1)23326 36324 y Fw(+)g Fn(f)25274 36523 y Fj(n)p Ff(\241)p Fk(2)27103 36324 y Fw(\()p Fn(h)28358 36523 y Fk(2)29179 36324 y Fw(+)f(1\))369 b(=)g Fn(h)34140 36523 y Fk(1)34666 36324 y Fn(f)35307 36523 y Fj(n)p Ff(\241)p Fk(1)37430 36324 y Fw(+)295 b Fn(h)39486 36523 y Fk(2)40012 36324 y Fn(f)40653 36523 y Fj(n)p Ff(\241)p Fk(2)43782 36324 y Fn(n)370 b Fm(\270)f Fw(2)p Fn(:)p 47775 36324 572 572 v 2751 39760 a Fw(A)480 b(succession)h(rule)f(de\257ning)f(the)h(sequence)g (\()p Fn(f)26896 39959 y Fj(n)27522 39760 y Fw(\))28028 39959 y Fj(n)p Ff(\270)p Fk(0)30337 39760 y Fw(can)g(ho)-36 b(w)g(ev)g(er)480 b(ha)-36 b(v)g(e)481 b(a)f(more)h(general)f(form,)800 41365 y(suc)-36 b(h)433 b(as:)18636 43413 y(\255)19575 43612 y Fk(2)20470 43413 y Fw(=)21851 41540 y Fg(\275)23401 42599 y Fw(\()p Fn(s)24520 42798 y Fk(0)25045 42599 y Fw(\))23401 44204 y(\()p Fn(k)45 b Fw(\))368 b Fd(;)i Fw(\()p Fn(c)p Fw(\))28772 43722 y Fj(k)24 b Ff(\241)p Fk(1)30764 44204 y Fw(\()o Fn(\301)p Fw(\()p Fn(k)45 b Fw(\)\))800 46479 y(where)484 b Fn(c;)221 b(s)6363 46678 y Fk(0)7344 46479 y Fm(2)454 b Fl(N)9643 45997 y Fk(+)10431 46479 y Fw(,)496 b Fn(\301)p Fw(\()p Fn(k)45 b Fw(\))455 b(=)f(\()p Fn(h)16967 46678 y Fk(1)17822 46479 y Fm(\241)330 b Fn(c)p Fw(\))p Fn(k)374 b Fw(+)329 b Fn(h)23391 46678 y Fk(2)24246 46479 y Fw(+)g Fn(c)p Fw(,)497 b(and)483 b(the)h(p)36 b(ositivit)-36 b(y)485 b(of)g(the)e(lab)36 b(els)485 b(is)f(ensured)f(b)-36 b(y)800 48084 y(the)433 b(follo)-36 b(wing)436 b(conditions:)p Black 1940 50985 a Fo(\(i\))p Black 651 w Fw(if)e Fn(c)369 b Fm(\267)g Fn(s)8188 51184 y Fk(0)9147 50985 y Fw(then)433 b(1)369 b Fm(\267)g Fn(c)g Fm(\267)g Fn(h)17611 51184 y Fk(1)18570 50985 y Fw(and)433 b(\(\()p Fn(h)22860 51184 y Fk(1)23680 50985 y Fm(\241)296 b Fn(c)p Fw(\))p Fn(c)e Fw(+)h Fn(h)28985 51184 y Fk(2)29806 50985 y Fw(+)g Fn(c)p Fw(\))368 b Fn(>)h Fw(0;)p Black 1542 53661 a Fo(\(ii\))p Black 650 w Fw(if)434 b Fn(c)369 b(>)f(s)8166 53860 y Fk(0)9125 53661 y Fw(then)433 b Fn(s)12701 53860 y Fk(0)13595 53661 y Fm(\267)370 b Fn(c)e Fm(\267)i Fn(h)18078 53860 y Fk(1)19037 53661 y Fw(and)433 b(\(\()p Fn(h)23327 53860 y Fk(1)24147 53661 y Fm(\241)295 b Fn(c)p Fw(\))p Fn(s)27154 53860 y Fk(0)27975 53661 y Fw(+)f Fn(h)30030 53860 y Fk(2)30851 53661 y Fw(+)h Fn(c)p Fw(\))369 b Fn(>)f Fw(0.)800 58079 y Fp(3)2152 b(Linear)716 b(recurrences)h(with)f(more)i(than)e(t) -60 b(w)g(o)718 b(terms.)800 61000 y Fw(In)587 b(this)g(section)h(w)-36 b(e)587 b(consider)h(the)e(general)i(case)g(of)g(linear)g(recurrences)e (de\257ning)h(non-decreasing)800 62605 y(sequences)393 b(of)h(p)36 b(ositiv)-36 b(e)393 b(in)-36 b(tegers,)402 b(and)392 b(w)-36 b(e)393 b(giv)-36 b(e)394 b(the)e(explicit)i(form)g (of)f(succession)g(rules)g(de\257ning)f(suc)-36 b(h)800 64210 y(sequences.)2751 65815 y(F)-108 b(or)461 b(the)f(sak)-36 b(e)462 b(of)g(simplicit)-36 b(y)-108 b(,)469 b(let)461 b(us)g(start)f(b)-36 b(y)461 b(studying)g(the)g(case)g(of)h(three)f (term)f(recurrences)g(of)800 67420 y(the)433 b(form)17893 69025 y Fn(f)18534 69224 y Fj(n)19529 69025 y Fw(=)369 b Fn(h)21659 69224 y Fk(1)22184 69025 y Fn(f)22825 69224 y Fj(n)p Ff(\241)p Fk(1)24949 69025 y Fw(+)295 b Fn(h)27005 69224 y Fk(2)27530 69025 y Fn(f)28171 69224 y Fj(n)p Ff(\241)p Fk(2)30295 69025 y Fw(+)g Fn(h)32351 69224 y Fk(3)32877 69025 y Fn(f)33518 69224 y Fj(n)p Ff(\241)p Fk(3)35346 69025 y Fn(;)800 71296 y Fw(with)434 b Fn(f)4404 71495 y Ff(\241)p Fk(1)6030 71296 y Fw(=)369 b(0,)434 b Fn(f)9497 71495 y Fk(0)10392 71296 y Fw(=)369 b(1,)434 b Fn(f)13859 71495 y Fk(1)14754 71296 y Fw(=)368 b Fn(s)16747 71495 y Fk(0)17642 71296 y Fm(2)g Fl(N)19855 70814 y Fk(+)20643 71296 y Fw(,)434 b(where)f Fn(h)25944 71495 y Fk(1)26839 71296 y Fm(2)368 b Fl(N)29052 70814 y Fk(+)30273 71296 y Fw(and)434 b Fn(h)33552 71495 y Fk(2)34077 71296 y Fn(;)221 b(h)35408 71495 y Fk(3)36303 71296 y Fm(2)369 b Fl(Z)p Fw(.)p Black Black eop %%Page: 5 5 5 4 bop Black 0 TeXcolorgray Black 52150 -2672 a Fw(5)p Black 800 1424 a(On)433 b(the)g(other)g(hand,)g(let)h(us)f(consider)g (the)g(rule)15352 6017 y(\255)16291 6216 y Fk(3)17186 6017 y Fw(=)18566 3294 y Fg(8)18566 4489 y(<)18566 6880 y(:)20301 4263 y Fw(\()p Fn(s)21420 4462 y Fk(0)21945 4263 y Fw(\))20301 6006 y(\()p Fn(k)45 b Fw(\))368 b Fd(;)i Fw(\()p Fn(c)p Fw(\))25671 5360 y Fj(k)24 b Ff(\241)p Fk(1)27664 6006 y Fw(\()o Fn(\301)28939 5524 y Fk(0)29465 6006 y Fw(\()p Fn(k)45 b Fw(\)\))1107 b Fn(k)414 b Fw(=)368 b Fn(s)35894 6205 y Fk(0)36420 6006 y Fn(;)221 b(c)20301 7748 y Fw(\()p Fn(k)45 b Fw(\))368 b Fd(;)i Fw(\()p Fn(c)p Fw(\))25671 7102 y Fj(k)24 b Ff(\241)p Fk(1)27664 7748 y Fw(\()o Fn(\301)28939 7266 y Fk(1)29465 7748 y Fw(\()p Fn(k)45 b Fw(\)\))800 10077 y(where)434 b Fn(c)368 b Fm(2)h Fl(N)7700 9595 y Fk(+)8487 10077 y Fw(,)434 b(and)17678 12916 y Fn(\301)18448 12434 y Fk(0)18973 12916 y Fw(\()p Fn(k)45 b Fw(\))369 b(=)g(\()p Fn(h)23711 13115 y Fk(1)24531 12916 y Fm(\241)296 b Fn(c)p Fw(\))p Fn(k)339 b Fw(+)295 b Fn(h)29997 13115 y Fk(2)30818 12916 y Fw(+)g Fn(c;)17678 16126 y(\301)18448 15644 y Fk(1)18973 16126 y Fw(\()p Fn(k)45 b Fw(\))369 b(=)g(\()p Fn(h)23711 16325 y Fk(1)24531 16126 y Fm(\241)296 b Fn(c)p Fw(\))p Fn(k)339 b Fw(+)295 b Fn(h)29997 16325 y Fk(2)30818 16126 y Fw(+)g Fn(h)32874 16325 y Fk(3)33694 16126 y Fw(+)g Fn(c:)800 19025 y Fw(The)303 b(follo)-36 b(wing)304 b(conditions)f(easily)h(ensure)d(that)h(the)g (lab)36 b(els)304 b(of)f(\255)32780 19224 y Fk(3)33608 19025 y Fw(are)g(p)36 b(ositiv)-36 b(e)304 b(and,)328 b(as)303 b(a)g(consequence,)800 20630 y(the)433 b(sequence)h(de\257ned) e(b)-36 b(y)433 b(\255)15656 20829 y Fk(3)16616 20630 y Fw(is)h(p)36 b(ositiv)-36 b(e)434 b(and)f(non-decreasing.)p Black 2028 23674 a(\(i\))p Black 651 w(If)h Fn(c)369 b Fm(\267)g Fn(s)8296 23873 y Fk(0)9255 23674 y Fw(then)432 b(1)370 b Fm(\267)f Fn(c)g Fm(\267)g Fn(h)17719 23873 y Fk(1)18244 23674 y Fw(,)434 b(\()p Fn(\301)20315 23192 y Fk(0)20841 23674 y Fw(\()p Fn(c)p Fw(\)\))368 b Fn(>)g Fw(0)434 b(and)f Fn(\301)29050 23192 y Fk(1)29797 23674 y Fw(\()p Fn(\301)31073 23192 y Fk(0)31599 23674 y Fw(\()p Fn(c)p Fw(\)\))368 b Fn(>)h Fw(0.)p Black 1667 26386 a(\(ii\))p Black 651 w(If)434 b Fn(c)369 b(>)f(s)8274 26585 y Fk(0)9233 26386 y Fw(then)433 b Fn(s)12809 26585 y Fk(0)13703 26386 y Fm(\267)370 b Fn(c)e Fm(\267)h Fn(h)18185 26585 y Fk(1)18711 26386 y Fw(,)434 b(\()p Fn(\301)20782 25904 y Fk(0)21307 26386 y Fw(\()p Fn(s)22426 26585 y Fk(0)22952 26386 y Fw(\)\))368 b Fn(>)h Fw(0)434 b(and)f Fn(\301)30096 25904 y Fk(1)30843 26386 y Fw(\()p Fn(\301)32119 25904 y Fk(0)32644 26386 y Fw(\()p Fn(s)33763 26585 y Fk(0)34288 26386 y Fw(\)\))369 b Fn(>)g Fw(0.)p Black 800 29430 a Fe(Prop)42 b(osition)500 b(2)p Black 650 w Fo(The)465 b(suc)-66 b(c)g(ession)464 b(rule)h Fw(\255)22717 29629 y Fk(3)23708 29430 y Fo(de\257nes)g(the)f(se)-66 b(quenc)g(e)463 b Fw(\()p Fn(f)36611 29629 y Fj(n)37238 29430 y Fw(\))37744 29629 y Fj(n)p Ff(\270)p Fk(0)39572 29430 y Fo(.)800 32474 y Fe(Pro)42 b(of.)572 b Fw(W)-108 b(e)415 b(can)h(easily)h(v)-36 b(erify)417 b(that)e Fn(f)20601 32673 y Fk(0)21495 32474 y Fw(=)369 b(1,)420 b Fn(f)24948 32673 y Fk(1)25843 32474 y Fw(=)368 b Fn(s)27836 32673 y Fk(0)28777 32474 y Fw(and)415 b Fn(f)31929 32673 y Fk(2)32824 32474 y Fw(=)369 b Fn(h)34954 32673 y Fk(1)35479 32474 y Fn(s)36092 32673 y Fk(0)36876 32474 y Fw(+)258 b Fn(h)38895 32673 y Fk(2)39420 32474 y Fw(.)572 b(F)-108 b(or)415 b Fn(n)370 b Fm(\270)f Fw(3)416 b(the)f(n)-36 b(um)g(b)36 b(er)800 34079 y(of)434 b(o)36 b(ccurrences)434 b(of)g(the)f(lab)36 b(el)434 b Fn(c)g Fw(at)f(lev)-36 b(el)435 b Fn(n)295 b Fm(\241)h Fw(3)434 b(is)g(equal)g(to)g Fn(f)32127 34278 y Fj(n)p Ff(\241)p Fk(2)34250 34079 y Fm(\241)296 b Fn(f)36220 34278 y Fj(n)p Ff(\241)p Fk(3)38048 34079 y Fw(,)434 b(so)g(w)-36 b(e)434 b(obtain)800 37013 y Fn(f)1441 37212 y Fj(n)2436 37013 y Fw(=)369 b Fn(cf)5018 37212 y Fj(n)p Ff(\241)p Fk(1)7017 37013 y Fm(\241)170 b Fn(cf)9421 37212 y Fj(n)p Ff(\241)p Fk(3)11420 37013 y Fw(+)g(\()p Fn(h)13857 37212 y Fk(1)14552 37013 y Fm(\241)g Fn(c)p Fw(\))p Fn(f)17462 37212 y Fj(n)p Ff(\241)p Fk(1)19461 37013 y Fw(+)g(\()p Fn(h)21898 37212 y Fk(2)22593 37013 y Fw(+)g Fn(h)24524 37212 y Fk(3)25220 37013 y Fw(+)g Fn(c)p Fw(\))p Fn(f)28109 37212 y Fj(n)p Ff(\241)p Fk(3)30107 37013 y Fm(\241)g Fn(c)370 b Fw(\()p Fn(f)33387 37212 y Fj(n)p Ff(\241)p Fk(2)35385 37013 y Fm(\241)170 b Fn(f)37229 37212 y Fj(n)p Ff(\241)p Fk(3)39058 37013 y Fw(\))g(+)g(\()p Fn(h)42171 37212 y Fk(2)42867 37013 y Fw(+)g Fn(c)p Fw(\)\()p Fn(f)46262 37212 y Fj(n)p Ff(\241)p Fk(2)48260 37013 y Fm(\241)g Fn(f)50104 37212 y Fj(n)p Ff(\241)p Fk(3)51933 37013 y Fw(\))p Fn(;)800 39946 y Fw(whic)-36 b(h)433 b(simpli\257es)h(to)g Fn(f)12403 40145 y Fj(n)13398 39946 y Fw(=)369 b Fn(h)15528 40145 y Fk(1)16053 39946 y Fn(f)16694 40145 y Fj(n)p Ff(\241)p Fk(1)18818 39946 y Fw(+)295 b Fn(h)20874 40145 y Fk(2)21399 39946 y Fn(f)22040 40145 y Fj(n)p Ff(\241)p Fk(2)24164 39946 y Fw(+)g Fn(h)26220 40145 y Fk(3)26746 39946 y Fn(f)27387 40145 y Fj(n)p Ff(\241)p Fk(3)29649 39946 y Fw(for)434 b Fn(n)369 b Fm(\270)h Fw(3.)p 35773 39946 572 572 v Black 800 43655 a Fe(Example)499 b(1)p Black 650 w Fw(The)434 b(sequence)f(\()p Fn(f)17575 43854 y Fj(n)18202 43655 y Fw(\))18708 43854 y Fj(n)p Ff(\270)p Fk(0)20969 43655 y Fw(satisfying)j(the)d(recurrence) f(relation)19143 46588 y Fn(f)19784 46787 y Fj(n)20780 46588 y Fw(=)368 b(3)p Fn(f)23451 46787 y Fj(n)p Ff(\241)p Fk(1)25575 46588 y Fm(\241)296 b Fw(2)p Fn(f)28195 46787 y Fj(n)p Ff(\241)p Fk(2)30319 46588 y Fw(+)f Fn(f)32267 46787 y Fj(n)p Ff(\241)p Fk(3)34095 46588 y Fn(;)800 49521 y Fw(with)434 b Fn(f)4404 49720 y Fk(1)5299 49521 y Fw(=)368 b(0)p Fn(;)444 b(f)8775 49720 y Fk(0)9669 49521 y Fw(=)369 b(1)p Fn(;)444 b(f)13146 49720 y Fk(1)14040 49521 y Fw(=)369 b(2)p Fn(;)434 b Fw(is)g(de\257ned)e(b)-36 b(y)434 b(the)f(succession)g(rule)18477 51241 y Fg(8)18477 52436 y(>)18477 52835 y(>)18477 53233 y(<)18477 55624 y(>)18477 56023 y(>)18477 56421 y(:)20211 52342 y Fw(\(2\))20211 53947 y(\(1\))369 b Fd(;)g Fw(\(1\))20211 55553 y(\(2\))g Fd(;)g Fw(\(1\)\(3\))20211 57158 y(\()p Fn(k)45 b Fw(\))369 b Fd(;)g Fw(\(1\))25672 56676 y Fj(k)24 b Ff(\241)p Fk(1)27443 57158 y Fw(\(2)p Fn(k)45 b Fw(\))1107 b Fn(k)414 b Fm(\270)369 b Fw(3)p Fn(:)2751 62122 y Fw(In)442 b(the)g(sequel)i(w)-36 b(e)442 b(will)i(extend)e(the)g(statemen)-36 b(t)442 b(of)i(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 443 w(2)p (#proposizione.2) [[395 158 401 170] [1 1 1 [3 3]] [0 0 1]] pdfm Black 442 w(to)443 b(the)f(general)h(case)g(of)h(linear)800 63727 y(recurrences.)2751 65997 y(Let)433 b(us)g(consider)h(the)f(rule) p Black Black eop %%Page: 6 6 6 5 bop Black 0 TeXcolorgray Black 52150 -2672 a Fw(6)p Black 4453 9092 a(\255)5392 9291 y Fj(j)6249 9092 y Fw(=)7629 2782 y Fg(8)7629 3978 y(>)7629 4376 y(>)7629 4775 y(>)7629 5173 y(>)7629 5572 y(>)7629 5970 y(>)7629 6369 y(>)7629 6767 y(>)7629 7166 y(>)7629 7564 y(<)7629 9955 y(>)7629 10354 y(>)7629 10753 y(>)7629 11151 y(>)7629 11550 y(>)7629 11948 y(>)7629 12347 y(>)7629 12745 y(>)7629 13144 y(>)7629 13542 y(:)9364 3988 y Fw(\()p Fn(s)10483 4187 y Fk(0)11008 3988 y Fw(\))9364 5593 y(\()p Fn(k)45 b Fw(\))368 b Fd(;)i Fw(\()p Fn(c)p Fw(\))14735 5111 y Fj(k)24 b Ff(\241)p Fk(1)16727 5593 y Fw(\()o Fn(\301)18002 5111 y Fk(0)18528 5593 y Fw(\()p Fn(k)45 b Fw(\)\))2852 b Fn(k)415 b Fw(=)368 b Fn(s)26703 5792 y Fk(0)27229 5593 y Fn(;)590 b(c)9364 7198 y Fw(\()p Fn(k)45 b Fw(\))368 b Fd(;)i Fw(\()p Fn(c)p Fw(\))14735 6716 y Fj(k)24 b Ff(\241)p Fk(1)16727 7198 y Fw(\()o Fn(\301)18002 6716 y Fk(1)18528 7198 y Fw(\()p Fn(k)45 b Fw(\)\))2852 b Fn(k)415 b Fw(=)368 b Fn(\301)26860 6716 y Fk(0)27386 7198 y Fw(\()p Fn(s)28505 7397 y Fk(0)29030 7198 y Fw(\))p Fn(;)591 b(\301)31258 6716 y Fk(0)31783 7198 y Fw(\()p Fn(c)p Fw(\))9364 8803 y(\()p Fn(k)45 b Fw(\))368 b Fd(;)i Fw(\()p Fn(c)p Fw(\))14735 8321 y Fj(k)24 b Ff(\241)p Fk(1)16727 8803 y Fw(\()o Fn(\301)18002 8321 y Fk(2)18528 8803 y Fw(\()p Fn(k)45 b Fw(\)\))2852 b Fn(k)415 b Fw(=)368 b Fn(\301)26860 8321 y Fk(1)27607 8803 y Fw(\()p Fn(\301)28883 8321 y Fk(0)29409 8803 y Fw(\()p Fn(s)30528 9002 y Fk(0)31053 8803 y Fw(\)\))o Fn(;)591 b(\301)33786 8321 y Fk(1)34533 8803 y Fw(\()p Fn(\301)35809 8321 y Fk(0)36335 8803 y Fw(\()p Fn(c)p Fw(\)\))9364 10078 y(.)9364 10521 y(.)9364 10964 y(.)9364 12569 y(\()p Fn(k)45 b Fw(\))368 b Fd(;)i Fw(\()p Fn(c)p Fw(\))14735 12087 y Fj(k)24 b Ff(\241)p Fk(1)16727 12569 y Fw(\()o Fn(\301)18002 12087 y Fj(j)51 b Ff(\241)p Fk(3)19691 12569 y Fw(\()p Fn(k)45 b Fw(\)\))1689 b Fn(k)415 b Fw(=)368 b Fm(f)h Fn(\301)27893 12087 y Fj(j)51 b Ff(\241)p Fk(4)29582 12569 y Fw(\()p Fn(\301)30858 12087 y Fj(j)g Ff(\241)p Fk(5)32547 12569 y Fw(\()p Fm(\242)221 b(\242)g(\242)h Fn(\301)35594 12087 y Fk(1)36120 12569 y Fw(\()p Fn(\301)37396 12087 y Fk(0)37921 12569 y Fw(\()p Fn(x)p Fw(\)\)\)\))368 b(:)738 b Fn(x)370 b Fw(=)e Fn(s)45759 12768 y Fk(0)46285 12569 y Fn(;)221 b(c)369 b Fm(g)9364 14174 y Fw(\()p Fn(k)45 b Fw(\))368 b Fd(;)i Fw(\()p Fn(c)p Fw(\))14735 13692 y Fj(k)24 b Ff(\241)p Fk(1)16727 14174 y Fw(\()o Fn(\301)18002 13692 y Fj(j)51 b Ff(\241)p Fk(2)19691 14174 y Fw(\()p Fn(k)45 b Fw(\)\))221 b Fn(;)800 17754 y Fw(where)434 b Fn(c;)221 b(s)6313 17953 y Fk(0)6838 17754 y Fn(;)g(h)8169 17953 y Fk(1)9065 17754 y Fm(2)368 b Fl(N)11278 17272 y Fk(+)12066 17754 y Fw(,)434 b Fn(h)13610 17953 y Fk(2)14135 17754 y Fn(;)221 b(h)15466 17953 y Fk(3)15992 17754 y Fn(;)g(:)g(:)g(:)j(;)d(h)19654 17953 y Fj(j)20510 17754 y Fm(2)369 b Fl(Z)p Fw(,)433 b(and)11020 21848 y Fn(\301)11790 21299 y Fj(m)12678 21848 y Fw(\()p Fn(k)45 b Fw(\))368 b(=)h(\()p Fn(h)17415 22047 y Fk(1)18235 21848 y Fm(\241)296 b Fn(c)p Fw(\))p Fn(k)340 b Fw(+)22952 20187 y Fj(m)p Fk(+1)23010 20586 y Fg(X)23208 23385 y Fj(i)p Fk(=1)25208 21848 y Fn(h)25957 22047 y Fj(i)p Fk(+1)27830 21848 y Fw(+)295 b Fn(c;)2823 b(m)369 b Fw(=)f(0)p Fn(;)221 b(:)g(:)g(:)j(;)d(j)371 b Fm(\241)295 b Fw(2)p Fn(:)2751 25799 y Fw(The)434 b(follo)-36 b(wing)435 b(conditions)f (determine)f(the)g(p)36 b(ositivit)-36 b(y)435 b(of)f(the)f(lab)36 b(els)434 b(of)h(\255)41034 25998 y Fj(j)41521 25799 y Fw(:)p Black 1940 28441 a Fo(\(i\))p Black 651 w Fw(if)f Fn(c)369 b Fm(\267)g Fn(s)8188 28640 y Fk(0)9147 28441 y Fw(then)433 b(1)369 b Fm(\267)g Fn(c)g Fm(\267)g Fn(h)17611 28640 y Fk(1)18136 28441 y Fw(,)434 b Fn(\301)19701 27959 y Fj(i)p Ff(\241)p Fk(2)21500 28441 y Fw(\()p Fn(\301)22776 27959 y Fj(i)p Ff(\241)p Fk(1)24354 28441 y Fw(\()p Fm(\242)221 b(\242)g(\242)h Fn(\301)27401 27959 y Fk(0)27927 28441 y Fw(\()p Fn(c)p Fw(\)\)\))o(,)433 b Fn(i)369 b Fw(=)g(2)p Fn(;)221 b(:)g(:)g(:)j(;)d(j)75 b Fw(;)p Black 1542 31130 a Fo(\(ii\))p Black 650 w Fw(if)434 b Fn(c)369 b(>)f(s)8166 31329 y Fk(0)9125 31130 y Fw(then)433 b Fn(s)12701 31329 y Fk(0)13595 31130 y Fm(\267)370 b Fn(c)e Fm(\267)i Fn(h)18078 31329 y Fk(1)18603 31130 y Fw(,)434 b Fn(\301)20168 30648 y Fj(i)p Ff(\241)p Fk(2)21967 31130 y Fw(\()p Fn(\301)23243 30648 y Fj(i)p Ff(\241)p Fk(1)24821 31130 y Fw(\()p Fm(\242)221 b(\242)g(\242)h Fn(\301)27868 30648 y Fk(0)28393 31130 y Fw(\()p Fn(s)29512 31329 y Fk(0)30038 31130 y Fw(\)\)\))o(,)434 b Fn(i)369 b Fw(=)f(2)p Fn(;)221 b(:)g(:)g(:)j(;)d(j)75 b Fw(.)p Black 800 34082 a Fe(Theorem)499 b(1)p Black 651 w Fo(The)j(suc)-66 b(c)g(ession)501 b(rule)h Fw(\255)21089 34281 y Fj(j)22079 34082 y Fo(de\257nes)f(the)h(non-de)-66 b(cr)g(e)g(asing)499 b(p)-66 b(ositive)500 b(se)-66 b(quenc)g(e)501 b(satisfying)800 35687 y(the)465 b(r)-66 b(e)g(curr)g(enc)g(e)462 b(r)-66 b(elation:)16356 38540 y Fn(f)16997 38739 y Fj(n)17992 38540 y Fw(=)369 b Fn(h)20122 38739 y Fk(1)20647 38540 y Fn(f)21288 38739 y Fj(n)p Ff(\241)p Fk(1)23412 38540 y Fw(+)295 b Fn(h)25468 38739 y Fk(2)25993 38540 y Fn(f)26634 38739 y Fj(n)p Ff(\241)p Fk(2)28758 38540 y Fw(+)g Fm(\242)221 b(\242)g(\242)296 b Fw(+)f Fn(h)33966 38739 y Fj(j)34452 38540 y Fn(f)35093 38739 y Fj(n)p Ff(\241)p Fj(j)36883 38540 y Fn(;)800 41392 y Fo(with)465 b(initial)e(c)-66 b(onditions)463 b Fn(f)14293 41591 y Fj(i)15038 41392 y Fw(=)368 b(0)p Fn(;)591 b(i)369 b Fw(=)g Fm(\241)p Fn(j)h Fw(+)295 b(2)p Fn(;)221 b(:)g(:)g(:)j(;)d Fm(\241)p Fw(1)p Fo(,)465 b Fn(f)30213 41591 y Fk(0)31108 41392 y Fw(=)369 b(1)p Fo(,)465 b(and)g Fn(f)37168 41591 y Fk(1)38062 41392 y Fw(=)369 b Fn(s)40056 41591 y Fk(0)40582 41392 y Fo(.)800 44344 y Fe(Pro)42 b(of.)578 b Fw(Analogous)434 b(to)g(that)f(of)i(Prop)36 b(osition)p 0 1 0 0 TeXcolorcmyk 434 w(2)p (#proposizione.2) [[294 318 300 330] [1 1 1 [3 3]] [0 0 1]] pdfm Black(.)p 26223 44344 572 572 v Black 800 47937 a Fe(Example)499 b(2)p Black Black 1879 w Fw(\(i\))p Black 650 w(NSW)434 b(n)-36 b(um)g(b)36 b(ers)432 b(\(sequence)h(A002315)j(in)e([)p 0 1 0 0 TeXcolorcmyk(SL)p (#cite.Sl) [[373 286 387 298] [1 1 1 [3 3]] [0 0 1]] pdfm Black -1 w(]\))g(are)g(de\257ned)e(b)-36 b(y)434 b(the)f(recurrence) 4052 49542 y(relation:)17495 53294 y Fn(f)18136 53493 y Fj(n)19132 53294 y Fw(=)368 b(6)p Fn(f)21803 53493 y Fj(n)p Ff(\241)p Fk(1)23928 53294 y Fm(\241)295 b Fn(f)25897 53493 y Fj(n)p Ff(\241)p Fk(2)27726 53294 y Fn(;)2823 b(f)31551 53493 y Fk(0)32446 53294 y Fw(=)368 b(1)p Fn(;)591 b(f)36069 53493 y Fk(1)36964 53294 y Fw(=)369 b(7)p Fn(:)4052 56126 y Fw(These)k(n)-36 b(um)g(b)36 b(ers)373 b(coun)-36 b(t)372 b(the)i(total)g(area)g(under)e(elev)-72 b(ated)374 b(Sc)-36 b(hr\304)-650 b(oder)373 b(paths)g([)p 0 1 0 0 TeXcolorcmyk(PP)p (#cite.PP) [[452 212 468 224] [1 1 1 [3 3]] [0 0 1]] pdfm Black(,)p 0 1 0 0 TeXcolorcmyk 374 w(BSS)p (#cite.BSS) [[474 212 496 224] [1 1 1 [3 3]] [0 0 1]] pdfm Black -1 w(].)559 b(Accord-)4052 57731 y(ing)433 b(to)h(Theorem)p 0 1 0 0 TeXcolorcmyk 434 w(2)p (#proposizione.2) [[192 197 198 209] [1 1 1 [3 3]] [0 0 1]] pdfm Black(,)g(the)f(succession)h(rule)f(de\257ning)g(these)g(n)-36 b(um)g(b)36 b(ers)432 b(is)22500 59412 y Fg(\275)24050 60471 y Fw(\(7\))24050 62076 y(\()p Fn(k)45 b Fw(\))369 b Fi(\303)g Fw(\(1\))29511 61594 y Fj(k)24 b Ff(\241)p Fk(1)31282 62076 y Fw(\(5)p Fn(k)45 b Fw(\))p Black 1667 65454 a(\(ii\))p Black 651 w(Self-a)-36 b(v)g(oiding)480 b(w)-36 b(alks)481 b(of)f(length)f Fn(n)p Fw(,)491 b(con)-36 b(tained)479 b(in)g(the)g(strip)g Fm(f)p Fw(0)p Fn(;)221 b Fw(1)p Fm(g)328 b(\243)e Fw([)p Fm(\2411)p Fn(;)221 b Fm(1)p Fw(],)494 b(are)479 b(coun)-36 b(ted)4052 67059 y(b)g(y)433 b(the)g(sequence)h Fm(f)p Fn(f)14794 67258 y Fj(n)15420 67059 y Fm(g)g Fw(that)f(satis\257es)h(a)g(linear)g (recurrence)e(relation)i([)p 0 1 0 0 TeXcolorcmyk(Z)p (#cite.Z) [[434 113 441 125] [1 1 1 [3 3]] [0 0 1]] pdfm Black 1 w(]:)5543 69873 y Fn(f)6184 70072 y Fk(0)7079 69873 y Fw(=)368 b(1)p Fn(;)591 b(f)10702 70072 y Fk(1)11597 69873 y Fw(=)369 b(3)p Fn(;)591 b(f)15221 70072 y Fk(2)16116 69873 y Fw(=)368 b(6)p Fn(;)591 b(f)19739 70072 y Fk(3)20634 69873 y Fw(=)369 b(12)p Fn(;)591 b(f)24908 70072 y Fk(4)25803 69873 y Fw(=)369 b(20)p Fn(;)591 b(f)30077 70072 y Fk(5)30972 69873 y Fw(=)368 b(36)p Fn(;)592 b(f)35246 70072 y Fk(6)36141 69873 y Fw(=)368 b(58)p Fn(;)592 b(f)40415 70072 y Fk(7)41310 69873 y Fw(=)368 b(100)p Fn(;)5543 71478 y(f)6184 71677 y Fj(n)7179 71478 y Fw(=)h Fn(f)9201 71677 y Fj(n)p Ff(\241)p Fk(1)11325 71478 y Fw(+)294 b(3)p Fn(f)13922 71677 y Fj(n)p Ff(\241)p Fk(2)16047 71478 y Fw(+)g(2)p Fn(f)18644 71677 y Fj(n)p Ff(\241)p Fk(3)20769 71478 y Fm(\241)h Fw(3)p Fn(f)23388 71677 y Fj(n)p Ff(\241)p Fk(4)25512 71478 y Fw(+)g Fn(f)27460 71677 y Fj(n)p Ff(\241)p Fk(5)29584 71478 y Fw(+)g Fn(f)31532 71677 y Fj(n)p Ff(\241)p Fk(6)46109 71478 y Fn(n)370 b(>)e Fw(7)p Fn(:)51138 70687 y Fw(\(4\))p Black Black eop %%Page: 7 7 7 6 bop Black 0 TeXcolorgray Black 52150 -2672 a Fw(7)p Black 4052 1424 a(F)-108 b(or)433 b(simplicit)-36 b(y)434 b(w)-36 b(e)434 b(c)-36 b(hange)434 b(the)f(initial)h(conditions)g(in) -36 b(to)433 b(the)g(follo)-36 b(wing:)22414 4039 y Fn(f)23055 4238 y Ff(\241)p Fj(i)24531 4039 y Fw(=)369 b(0)p Fn(;)1108 b(i)368 b Fw(=)h(1)p Fn(;)221 b(:)g(:)g(:)j(;)d Fw(5)22414 5644 y Fn(f)23055 5843 y Fk(0)23950 5644 y Fw(=)368 b(1)p Fn(:)4052 8804 y Fw(Then)433 b(the)g(succession)h(rule)f(obtained)g (applying)h(Theorem)p 0 1 0 0 TeXcolorcmyk 434 w(1)p (#teorema.1) [[383 638 389 650] [1 1 1 [3 3]] [0 0 1]] pdfm Black 434 w(is)23246 11083 y Fg(8)23246 12278 y(>)23246 12677 y(>)23246 13075 y(>)23246 13474 y(>)23246 13872 y(>)23246 14271 y(>)23246 14669 y(>)23246 15068 y(>)23246 15466 y(<)23246 17857 y(>)23246 18256 y(>)23246 18654 y(>)23246 19053 y(>)23246 19452 y(>)23246 19850 y(>)23246 20249 y(>)23246 20647 y(>)23246 21046 y(:)24980 12168 y Fw(\(1\))24980 13773 y(\(1\))369 b Fi(\303)g Fw(\(4\))24980 15378 y(\(3\))g Fi(\303)g Fw(\(1\))30370 14896 y Fk(2)30896 15378 y Fw(\()p 31402 14362 651 54 v(4\))24980 16983 y(\(4\))g Fi(\303)g Fw(\(1\))30370 16501 y Fk(3)30896 16983 y Fw(\(6\))24980 18588 y(\()p 25486 17573 V(4\))g Fi(\303)g Fw(\(1\))30370 18106 y Fk(3)30896 18588 y Fw(\(5\))24980 20193 y(\(5\))g Fi(\303)g Fw(\(1\))30370 19711 y Fk(4)30896 20193 y Fw(\(5\))24980 21798 y(\(6\))g Fi(\303)g Fw(\(1\))30370 21316 y Fk(5)30896 21798 y Fw(\(3\))p Fn(:)2751 24074 y Fw(F)-108 b(or)420 b(clarit)-36 b(y's)422 b(sak)-36 b(e,)424 b(w)-36 b(e)421 b(w)-36 b(an)g(t)420 b(to)h(p)36 b(oin)-36 b(t)420 b(out)g(that)g(the)g(lab)36 b(el)421 b(\(4\))f(is)h(pro)36 b(duced)419 b(b)-36 b(y)421 b Fn(\301)45241 23592 y Fk(0)45766 24074 y Fw(\()p Fn(c)p Fw(\),)i(and)d(it)h(is)800 25679 y(sub)72 b(ject)433 b(to)h(the)f(rule)h(in)-36 b(v)g(olving)434 b Fn(\301)18088 25197 y Fk(1)18614 25679 y Fw(,)g(while)g(the)f(lab)36 b(el)434 b(\()p 28694 24664 V(4)q(\))f(is)h(sub)72 b(ject)433 b(to)h(the)f(rule)g(in)-36 b(v)g(olving)435 b Fn(\301)48880 25197 y Fk(4)49406 25679 y Fw(.)2751 27284 y(Finally)-108 b(,)685 b(w)-36 b(e)634 b(remark)g(that)f(a)h(rule)f(de\257ning)g(the)g(original)i(n)-36 b(um)g(b)36 b(er)632 b(sequence)h(can)h(b)36 b(e)633 b(simply)800 28890 y(obtained)433 b(b)-36 b(y)434 b(adding)f(some)h (other)f(pro)36 b(ductions,)433 b(in)h(order)f(to)g(satisfy)i(the)e (initial)i(conditions.)p Black 800 31698 a Fe(Example)499 b(3)p Black 650 w Fw(No)-36 b(w)290 b(w)-36 b(e)289 b(are)h(able)f(to)g (giv)-36 b(e)290 b(a)f(succession)h(rule)e(for)i(the)f(n)-36 b(um)g(b)36 b(er)287 b(sequence)i(1)p Fn(;)221 b Fw(1)p Fn(;)g Fw(1)p Fn(;)g Fw(2)p Fn(;)g Fw(3)p Fn(;)g Fw(7)p Fn(;)g Fw(11)p Fn(;)g Fw(26)p Fn(;)g(:)g(:)g(:)11 b Fw(,)800 33303 y(de\257ned)461 b(in)h(the)f(\257rst)h(part)g(of)h(the)e(pap)36 b(er.)664 b(Omitting)462 b(for)g(simplicit)-36 b(y)464 b(the)d(initial)i(constan)-36 b(t)462 b(terms)g(w)-36 b(e)800 34908 y(ha)g(v)g(e)21801 35052 y Fg(8)21801 36247 y(>)21801 36646 y(>)21801 37044 y(>)21801 37443 y(>)21801 37841 y(>)21801 38240 y(>)21801 38638 y(<)21801 41030 y(>)21801 41428 y(>)21801 41827 y(>)21801 42225 y(>)21801 42624 y(>)21801 43022 y(>)21801 43421 y(:)23535 36142 y Fw(\(2\))23535 37747 y(\(2\))369 b Fd(;)g Fw(\(1\)\(2\))23535 39352 y(\(1\))g Fd(;)g Fw(\(4\))23535 40958 y(\(4\))g Fd(;)g Fw(\(1\))28925 40475 y Fk(3)29451 40958 y Fw(\()p 29957 39942 V(1\))23535 42563 y(\(3\))g Fd(;)g Fw(\(1\))28925 42081 y Fk(2)29451 42563 y Fw(\()p 29957 41547 V(1\))23535 44168 y(\()p 24041 43152 V(1\))g Fd(;)g Fw(\(3\))p Fn(:)800 48824 y Fe(Succession)546 b(rules)g(with)f(negativ)-42 b(e)545 b(lab)42 b(els.)1302 b Fw(Theorem)p 0 1 0 0 TeXcolorcmyk 474 w(2)p (#proposizione.2) [[362 278 368 290] [1 1 1 [3 3]] [0 0 1]] pdfm Black 474 w(clearly)475 b(do)36 b(es)474 b(not)f(in)-36 b(v)g(olv)g(e)475 b(the)e(whole)800 50430 y(set)500 b Fm(R)g Fw(of)h(rational)f(generating)h(functions.)777 b(Moreo)-36 b(v)g(er,)518 b(as)500 b(w)-36 b(e)500 b(already)h(remark) -36 b(ed,)517 b(the)500 b(problem)f(of)800 52035 y(establishing)e(if)h (a)f(rational)h(generating)f(function)g(de\257nes)f(a)h(non-negativ)-36 b(e)497 b(sequence)g(of)h(in)-36 b(tegers)497 b(is)800 53640 y(undecidable,)620 b(and)582 b(then)g(if)h(w)-36 b(e)583 b(w)-36 b(an)g(t)583 b(to)g(treat)g(the)f(whole)h(set)g(of)h (rational)f(generating)g(functions)800 55245 y(w)-36 b(e)576 b(ha)-36 b(v)g(e)577 b(to)f(allo)-36 b(w)578 b(lab)36 b(els)577 b(of)f(the)g(rules)g(to)g(con)-36 b(tain)576 b(negativ)-36 b(e)577 b(v)-72 b(alues.)1007 b(Under)575 b(this)h(h)-36 b(yp)36 b(othesis)576 b(a)800 56850 y(succession)371 b(rule)f(de\257nes)g(a)h(sequence)f(of)h(in)-36 b(teger)371 b(n)-36 b(um)g(b)36 b(ers)369 b(\()p Fn(f)31980 57049 y Fj(n)32606 56850 y Fw(\))33112 57049 y Fj(n)p Ff(\270)p Fk(0)34940 56850 y Fw(,)384 b(not)370 b(necessarily)i(p)36 b(ositiv)-36 b(e,)384 b(where)800 58455 y(the)393 b(term)g Fn(f)6708 58654 y Fj(n)7728 58455 y Fw(is)h(giv)-36 b(en)394 b(b)-36 b(y)394 b(the)f(n)-36 b(um)g(b)36 b(er)392 b(of)i(p)36 b(ositiv)-36 b(e)395 b(lab)36 b(els)394 b(min)-36 b(us)393 b(the)g(n)-36 b(um)g(b)36 b(er)392 b(of)i(negativ)-36 b(e)395 b(lab)36 b(els)394 b(at)800 60060 y(lev)-36 b(el)435 b Fn(n)f Fw(of)g(the)f(generating)h(tree.)2751 61665 y(Recen)-36 b(tly)398 b(w)-36 b(e)397 b(in)-36 b(v)g(estigated)398 b(the)f(relationship)g(b)36 b(et)-36 b(w)g(een)397 b(rational)h (generating)g(functions)f(and)g(suc-)800 63270 y(cession)404 b(rules)e(with)i(negativ)-36 b(e)404 b(lab)36 b(els)403 b(\(brie\260y)g Fo(gener)-66 b(alize)g(d)435 b(suc)-66 b(c)g(ession)436 b(rules)p Fw(\))404 b(b)-36 b(y)403 b(applying)g(the)g(same)800 64875 y(to)36 b(ols)463 b(that)e(w)-36 b(e)461 b(used)g(in)h(the)f(\257rst)g(part)g(of)h(the)f(pap)36 b(er.)662 b(F)-108 b(urthermore)460 b(w)-36 b(e)462 b(determined)e(an)h (algorithm)800 66480 y(to)509 b(pass)f(from)h(a)g(rational)g (generating)f(function)h(to)f(a)h(generalized)g(succession)f(rule.)803 b(Ho)-36 b(w)g(ev)g(er)509 b(this)800 68086 y(algorithm)577 b(has)g(a)g(rather)f(complex)i(description,)612 b(and)576 b(moreo)-36 b(v)g(er)578 b(it)e(do)36 b(es)577 b(not)g(giv)-36 b(e)577 b(an)g(answ)-36 b(er)577 b(to)800 69691 y(the)500 b(conjecture)h Fm(F)615 b Fw(=)483 b Fm(S)100 b Fw(.)780 b(Therefore,)518 b(for)501 b(the)f(sak)-36 b(e)502 b(of)f(simplicit)-36 b(y)-108 b(,)519 b(w)-36 b(e)501 b(only)g(presen)-36 b(t)500 b(the)g(follo)-36 b(wing)800 71296 y(examples.)p Black Black eop %%Page: 8 8 8 7 bop Black 0 TeXcolorgray Black 52150 -2672 a Fw(8)p Black Black 800 1424 a Fe(Example)499 b(4)p Black 650 w Fw(Let)572 b(us)g(consider)h(the)f(n)-36 b(um)g(b)36 b(er)570 b(sequence)j(1)p Fn(;)221 b Fw(2)p Fn(;)g Fm(\241)p Fw(10)p Fn(;)g Fw(22)p Fn(;)g Fm(\241)p Fw(26)p Fn(;)g Fm(\241)p Fw(10)p Fn(;)g Fw(134)p Fn(;)g(:)g(:)g(:)11 b Fw(,)608 b(de\257ned)800 3029 y(b)-36 b(y)434 b(the)f(recurrence)f (relation)18521 5850 y Fn(f)19162 6049 y Fk(0)20057 5850 y Fw(=)368 b(1)p Fn(;)591 b(f)23680 6049 y Fk(1)24575 5850 y Fw(=)369 b(2)p Fn(;)18521 7455 y(f)19162 7654 y Fj(n)20157 7455 y Fw(=)g Fm(\241)p Fw(3)p Fn(f)23862 7654 y Fj(n)p Ff(\241)p Fk(1)25986 7455 y Fm(\241)296 b Fw(4)p Fn(f)28606 7654 y Fj(n)p Ff(\241)p Fk(2)31542 7455 y Fn(n)369 b(>)g Fw(1)p Fn(:)2751 10298 y Fw(The)434 b(succession)f(rule)h(de\257ning)e(this)i(sequence)f(is)18442 12012 y Fg(8)18442 13208 y(<)18442 15599 y(:)20176 13119 y Fw(\(4\))20176 14724 y(\()p Fn(k)45 b Fw(\))369 b Fd(;)g Fw(\(1\))25637 14242 y Fj(k)24 b Ff(\241)p Fk(1)27409 14724 y Fw(\()p Fm(\241)p Fw(2)p Fn(k)340 b Fm(\241)295 b Fw(1\))20176 16329 y(\()p Fm(\241)p Fn(k)45 b Fw(\))369 b Fd(;)h Fw(\()p Fm(\241)p Fw(1\))27704 15847 y Fj(k)24 b Ff(\241)p Fk(1)29475 16329 y Fw(\(2)p Fn(k)340 b Fw(+)295 b(1\))p Fn(:)p Black 800 23397 a Fe(Example)499 b(5)p Black 650 w Fw(Odd-index)409 b(Fib)36 b(onacci)410 b(n)-36 b(um)g(b)36 b(ers)408 b(with)i(alternating)g(sign,)415 b(1)p Fn(;)221 b Fm(\241)p Fw(2)p Fn(;)g Fw(5)p Fn(;)g Fm(\241)p Fw(13)p Fn(;)g Fw(34)p Fn(;)g Fm(\241)p Fw(89)p Fn(;)g(:)g(:)g(:)10 b Fw(,)800 25002 y(are)434 b(de\257ned)e(b)-36 b(y)433 b(the)g(recurrence)g(relation)18846 27823 y Fn(f)19487 28022 y Fk(0)20382 27823 y Fw(=)369 b(1)p Fn(;)591 b(f)24006 28022 y Fk(1)24901 27823 y Fw(=)368 b Fm(\241)p Fw(2)p Fn(;)18846 29428 y(f)19487 29627 y Fj(n)20482 29428 y Fw(=)h Fm(\241)p Fw(3)p Fn(f)24187 29627 y Fj(n)p Ff(\241)p Fk(1)26311 29428 y Fm(\241)296 b Fn(f)28281 29627 y Fj(n)p Ff(\241)p Fk(2)31216 29428 y Fn(n)370 b(>)e Fw(1)p Fn(:)2751 32271 y Fw(A)434 b(succession)f(rule)h(de\257ning)e(this)i(sequence)f (is)19749 33985 y Fg(8)19749 35181 y(<)19749 37572 y(:)21483 35092 y Fw(\(2\))21483 36697 y(\()p Fn(k)45 b Fw(\))369 b Fd(;)g Fw(\()p Fm(\241)p Fw(1\))27977 36215 y Fj(k)24 b Ff(\241)p Fk(1)29749 36697 y Fw(\()p Fm(\241)p Fw(2)p Fn(k)45 b Fw(\))21483 38302 y(\()p Fm(\241)p Fn(k)g Fw(\))369 b Fd(;)g Fw(\(1\))27977 37820 y Fj(k)24 b Ff(\241)p Fk(1)29749 38302 y Fw(\(2)p Fn(k)45 b Fw(\))p Fn(:)2751 41219 y Fw(W)-108 b(e)611 b(p)36 b(oin)-36 b(t)610 b(out)g(that)g(the)g(rule)g (\()p 0 1 0 0 TeXcolorcmyk(5)p (#esempio.5) [[251 346 257 358] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\))h(is)f(v)-36 b(ery)611 b(similar)h(to)f(\()p 0 1 0 0 TeXcolorcmyk(3)p (#equation.3) [[368 346 374 358] [1 1 1 [3 3]] [0 0 1]] pdfm Black(\),)655 b(whic)-36 b(h)610 b(de\257nes)f(the)h(o)36 b(dd-indexed)800 42824 y(Fib)g(onacci)434 b(n)-36 b(um)g(b)36 b(ers.)800 47261 y Fp(References)p Black 800 50182 a Fw([GF)-36 b(GT])p Black 650 w(C.)736 b(Banderier,)810 b(M.)735 b(Bousquet-M)-36 b(\266)-614 b(elou,)811 b(A.)735 b(Denise,)811 b(P)-108 b(.)735 b(Fla)72 b(jolet,)812 b(D.)736 b(Gardy)-108 b(,)810 b(and)734 b(D.)2823 51787 y(Gouy)-36 b(ou-Beauc)g(hamps,)1300 b(Generating)589 b(functions)h(for)g(generating)g(trees,)629 b Fo(Discr)-66 b(ete)606 b(Math.)589 b Fe(246)2823 53392 y Fw(\(2002\),)435 b(29{55.)p Black 800 56104 a([BDFR])p Black 651 w(E.)535 b(Barcucci,)560 b(A.)534 b(Del)h(Lungo,)559 b(A.)534 b(F)-108 b(rosini,)560 b(and)533 b(S.)h(Rinaldi,)561 b(A)534 b(tec)-36 b(hnology)535 b(for)f(rev)-36 b(erse-)2823 57709 y(engineering)622 b(a)f(com)-36 b(binatorial)622 b(problem)f(from)h(a)g(rational)g(generating)f(function,)669 b Fo(A)-66 b(dv.)636 b(Appl.)2823 59314 y(Math.)433 b Fe(26)h Fw(\(2001\),)h(129{153.)p Black 800 62026 a([BR])p Black 651 w(E.)h(Barcucci)f(and)g(S.)g(Rinaldi,)584 b(Some)435 b(linear)g(recurrences)g(and)g(their)f(com)-36 b(binatorial)437 b(in)-36 b(terpre-)2823 63632 y(tation)434 b(b)-36 b(y)434 b(means)f(of)h(regular)g(languages,)578 b Fo(The)-66 b(or.)464 b(Comp.)g(Sci.)432 b Fe(255)i Fw(\(2001\),)h(679{686.)p Black 800 66344 a([BSS])p Black 650 w(J.)295 b(Bonin,)323 b(L.)295 b(Shapiro,)322 b(and)295 b(R.)g(Simion,)378 b(Some)295 b Fn(q)48 b Fw(-analogues)295 b(of)g(the)g(Sc)-36 b(hr\304)-650 b(oder)293 b(n)-36 b(um)g(b)36 b(ers)293 b(arising)2823 67949 y(from)453 b(com)-36 b(binatorial)453 b(statistics)g(on)g(lattice)g(paths,)637 b Fo(J.)481 b(Statistic)-66 b(al)481 b(Planning)f(and)j(Infer)-66 b(enc)g(e)931 b Fe(34)2823 69554 y Fw(\(1993\))435 b(35{55.)p Black Black eop %%Page: 9 9 9 8 bop Black 0 TeXcolorgray Black 52150 -2672 a Fw(9)p Black Black 800 1424 a([BDLPP])p Black 651 w(E.)474 b(Barcucci,)485 b(A.)474 b(Del)h(Lungo)e(E.)h(P)-36 b(ergola,)486 b(and)473 b(R.)h(Pinzani,)485 b(ECO:)474 b(a)g(metho)36 b(dology)475 b(for)2823 3029 y(the)433 b(en)-36 b(umeration)433 b(of)h(com)-36 b(binatorial)435 b(ob)72 b(jects,)434 b Fo(J.)465 b(Di\256er)-66 b(enc)g(e)462 b(Eq.)i(Appl.)433 b Fe(5)h Fw(\(1999\),)h(435{490.)p Black 800 5741 a([FPPR])p Black 651 w(L.)441 b(F)-108 b(errari,)444 b(E.)d(P)-36 b(ergola,)445 b(R.)d(Pinzani,)i(and)d(S.)g (Rinaldi,)k(An)c(algebraic)h(c)-36 b(haracterization)442 b(of)2823 7346 y(the)433 b(set)h(of)g(succession)g(rules,)g Fo(The)-66 b(or.)463 b(Comp.)i(Sci.)432 b Fe(281)i Fw(\(2002\),)h (351{367.)p Black 800 10058 a([PP])p Black 651 w(E.)1487 b(P)-36 b(ergola)1488 b(and)e(R.)h(Pinzani,)3980 b(A)1485 b(com)-36 b(binatorial)1488 b(in)-36 b(terpretation)1486 b(of)i(the)2823 11663 y(Area)1346 b(of)f(Sc)-36 b(hr\304)-650 b(oder)1344 b(paths,)3520 b Fo(Ele)-66 b(ctr)g(onic)1300 b(J.)j(Combinatorics)1343 b Fe(6)i Fw(\(1999\),)1574 b(#R40.)p 0 1 0 0 TeXcolorcmyk 2823 13269 a Fa (http://www.combinatorics.org/Volume)p 26845 13269 411 45 v 477 w(6/Abstracts/v6i1r40.html)p [[97 598 465 610] [1 1 1 [3 3]] [0 0 1]] (http://www.combinatorics.org/Volume_6/Abstracts/v6i1r40.html) pdfm Black Black 800 15981 a Fw([SL])p Black 650 w(N.)1969 b(J.)f(A.)g(Sloane)1301 b Fo(The)1875 b(On-Line)f(Encyclop)-66 b(e)g(dia)1874 b(of)h(Inte)-66 b(ger)1873 b(Se)-66 b(quenc)g(es)p Fw(,)p 0 1 0 0 TeXcolorcmyk 2823 17586 a Fa (http://www.research.att.com/~njas/sequences/index.html)p [[97 559 430 571] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/~njas/sequences/index.html) pdfm Black Fw(.)p Black 800 20298 a([SS])p Black 650 w(A.)614 b(Salomaa)g(and)f(M.)g(Soittola,)1158 b Fo(A)-33 b(utomata-The)-66 b(or)g(etic)627 b(Asp)-66 b(e)g(cts)629 b(of)h(F)-100 b(ormal)630 b(Power)h(Series)p Fw(,)2823 21903 y(Springer-V)-108 b(erlag,)433 b(1978.)p Black 800 24615 a([Z])p Black 651 w(D.)479 b(Zeilb)36 b(erger,)722 b(Self-a)-36 b(v)g(oiding)480 b(w)-36 b(alks,)491 b(the)478 b(language)h(of)h(science,)490 b(and)478 b(Fib)36 b(onacci)479 b(n)-36 b(um)g(b)36 b(ers,)721 b Fo(J.)2823 26220 y(Stat.)464 b(Infer)-66 b(enc)g(e)461 b(and)k(Planning)432 b Fe(54)i Fw(\(1996\))h(135{138.)p 800 29364 52000 45 v 800 31615 a(2000)g Fo(Mathematics)464 b(Subje)-66 b(ct)463 b(Classi\257c)-66 b(ation)p Fw(:)577 b(05A15)434 b(.)800 33220 y Fo(Keywor)-66 b(ds:)597 b(suc)-66 b(c)g(ession)465 b(rules,)g(gener)-66 b(ating)462 b(tr)-66 b(e)g(es,)463 b(r)-66 b(ational)464 b(gener)-66 b(ating)462 b(functions)p 800 34851 V 800 37175 a Fw(\(Concerned)433 b(with)h(sequences)p 0 1 0 0 TeXcolorcmyk 433 w(A001519)p 16603 37388 4878 54 v [[221 382 265 394] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=A001519) pdfm Black 0 1 0 0 TeXcolorcmyk 436 w(A005246)p 21914 37388 V [[269 382 313 394] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=A005246) pdfm Black 0 1 0 0 TeXcolorcmyk 435 w(A002315)p 27224 37388 V [[317 382 361 394] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=A002315) pdfm Black 2 w(.\))800 39580 y(Receiv)-36 b(ed)460 b(Decem)-36 b(b)36 b(er)459 b(23,)467 b(2002;)474 b(revised)459 b(v)-36 b(ersion)460 b(receiv)-36 b(ed)459 b(April)h(22,)466 b(2003.)657 b(Published)458 b(in)i Fo(Journal)800 41185 y(of)465 b(Inte)-66 b(ger)462 b(Se)-66 b(quenc)g(es)432 b Fw(April)h(24,)i(2003.)p 800 42816 52000 45 v 800 45067 a(Return)e(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 311 338 323] [1 1 1 [3 3]] [0 0 1]] (http://www.math.uwaterloo.ca/JIS/) pdfm Black(.)p Black Black eop %%Trailer end end