821:
1859:
405:
1529:
1364:
75:. A function's WZ counterpart may be used to find an equivalent and much simpler sum. Although finding WZ pairs by hand is impractical in most cases,
940:
1622:
816:{\displaystyle {\begin{aligned}\sum _{k=-\infty }^{\infty }&{}=\lim _{M\to \infty }\sum _{k=-M}^{M}\\&{}=\lim _{M\to \infty }\sum _{k=-M}^{M}\\&{}=\lim _{M\to \infty }\\&{}=0-0\\&{}=0.\end{aligned}}}
1016:
1627:
410:
281:
220:
385:
1605:
1144:
1955:
1375:
1214:
1182:
832:
1854:{\displaystyle {\begin{aligned}F(n,k)&={\frac {(-1)^{k}{n \choose k}{2k \choose k}4^{n-k}}{2n \choose n}},\\G(n,k)&=R(n,k)F(n,k-1).\end{aligned}}}
951:
79:
provides a method to find a function's WZ counterpart, and can be implemented in a
1879:
To prove that the constant in the right-hand side of the identity is 1, substitute
226:
112:
1918:
292:
1965:
1540:
1066:
1524:{\displaystyle \sum _{k=0}^{\infty }{\frac {(-1)^{k}{n \choose k}{2k \choose k}4^{n-k}}{2n \choose n}}=1.}
106:
form a WZ pair if and only if the following two conditions hold:
17:
80:
1999:
1359:{\displaystyle \sum _{k=0}^{\infty }(-1)^{k}{n \choose k}{2k \choose k}4^{n-k}={2n \choose n}.}
92:
48:
44:
76:
72:
1152:
64:
8:
1610:
to verify that the left-hand side does not depend on
935:{\displaystyle \sum _{k=-\infty }^{\infty }F(n+1,k)=\sum _{k=-\infty }^{\infty }F(n,k),}
1959:
396:
1929:
1914:
1904:
56:
1896:
52:
1895:
47:
that can be used to certify certain combinatorial
1983:
59:, and are instrumental in the evaluation of many
1977:
1993:
32:
1908:
1900:
28:
1060:
form a WZ pair, then they satisfy the relation
1369:
Divide the identity by its right-hand side:
68:
60:
1027:. Its value can be found by substituting
1011:{\displaystyle \sum _{k=-\infty }^{\infty }F(n,k)={\text{const}}.}
1986:
provides details on the WZ method of identity certification.
1208:
A Wilf–Zeilberger pair can be used to verify the identity
1021:
The constant does not depend on
1980:
gives a method for generating WZ pairs when they exist.
1625:
1543:
1378:
1217:
1155:
1069:
954:
835:
408:
295:
229:
115:
1853:
1599:
1523:
1358:
1176:
1138:
1010:
934:
815:
379:
275:
214:
1347:
1329:
1301:
1283:
1274:
1261:
276:{\displaystyle \lim _{M\to \pm \infty }G(n,M)=0.}
1991:
704:
601:
498:
231:
215:{\displaystyle F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k),}
380:{\displaystyle \sum _{k=-\infty }^{\infty }=0}
1763:
1745:
1720:
1702:
1693:
1680:
1508:
1490:
1465:
1447:
1438:
1425:
286:Together, these conditions ensure that
1600:{\displaystyle R(n,k)={\frac {2k-1}{2n+1}}}
51:. WZ pairs are named after
1958:, an analog of WZ method for evaluating
1930:"What Is . . . a Wilf-Zeilberger Pair?"
1876:form a Wilf–Zeilberger pair.
14:
1992:
1927:
1139:{\displaystyle G(n,k)=R(n,k)F(n,k-1),}
71:, and in general any
43:, is a pair of
24:
1749:
1706:
1684:
1494:
1451:
1429:
1395:
1333:
1287:
1265:
1234:
974:
969:
906:
901:
855:
850:
714:
611:
508:
432:
427:
315:
310:
244:
25:
2011:
1971:
1036:for a particular
1966:List of mathematical identities
1841:
1823:
1817:
1805:
1792:
1780:
1668:
1658:
1645:
1633:
1559:
1547:
1413:
1403:
1249:
1239:
1171:
1159:
1130:
1112:
1106:
1094:
1085:
1073:
994:
982:
926:
914:
881:
863:
770:
767:
752:
743:
725:
719:
711:
688:
685:
673:
664:
646:
640:
608:
585:
582:
570:
561:
543:
537:
505:
485:
482:
470:
461:
443:
437:
368:
365:
353:
344:
326:
320:
264:
252:
238:
206:
194:
185:
167:
158:
146:
137:
119:
13:
1:
1889:
86:
81:symbolic manipulation program
7:
1949:
10:
2016:
1956:Almkvist–Zeilberger method
1534:Use the proof certificate
1203:
1184:is a rational function of
1886: for instance.
37:Wilf–Zeilberger pair
1984:Generatingfunctionology
1928:Tefera, Akalu (2010),
1855:
1601:
1525:
1399:
1360:
1238:
1178:
1177:{\displaystyle R(n,k)}
1140:
1012:
978:
936:
910:
859:
817:
639:
536:
436:
381:
319:
277:
216:
1856:
1602:
1526:
1379:
1361:
1218:
1179:
1141:
1013:
955:
937:
887:
836:
818:
616:
513:
413:
390:because the function
382:
296:
278:
217:
73:hypergeometric series
65:binomial coefficients
1623:
1541:
1376:
1215:
1198:WZ proof certificate
1153:
1067:
952:
833:
406:
293:
227:
113:
31:, specifically
1978:Gosper's algorithm
1960:definite integrals
1851:
1849:
1597:
1521:
1356:
1196:and is called the
1174:
1136:
1008:
932:
813:
811:
718:
615:
512:
377:
273:
248:
212:
77:Gosper's algorithm
1768:
1761:
1718:
1691:
1595:
1513:
1506:
1463:
1436:
1345:
1299:
1272:
1003:
703:
600:
497:
230:
16:(Redirected from
2007:
1944:
1934:
1924:
1905:Doron Zeilberger
1860:
1858:
1857:
1852:
1850:
1769:
1767:
1766:
1757:
1748:
1742:
1741:
1740:
1725:
1724:
1723:
1714:
1705:
1698:
1697:
1696:
1683:
1676:
1675:
1656:
1606:
1604:
1603:
1598:
1596:
1594:
1580:
1566:
1530:
1528:
1527:
1522:
1514:
1512:
1511:
1502:
1493:
1487:
1486:
1485:
1470:
1469:
1468:
1459:
1450:
1443:
1442:
1441:
1428:
1421:
1420:
1401:
1398:
1393:
1365:
1363:
1362:
1357:
1352:
1351:
1350:
1341:
1332:
1322:
1321:
1306:
1305:
1304:
1295:
1286:
1279:
1278:
1277:
1264:
1257:
1256:
1237:
1232:
1183:
1181:
1180:
1175:
1145:
1143:
1142:
1137:
1017:
1015:
1014:
1009:
1004:
1001:
977:
972:
941:
939:
938:
933:
909:
904:
858:
853:
822:
820:
819:
814:
812:
802:
797:
781:
776:
717:
699:
694:
638:
633:
614:
596:
591:
535:
530:
511:
493:
435:
430:
386:
384:
383:
378:
318:
313:
282:
280:
279:
274:
247:
221:
219:
218:
213:
57:Doron Zeilberger
21:
2015:
2014:
2010:
2009:
2008:
2006:
2005:
2004:
1990:
1989:
1974:
1952:
1932:
1921:
1897:Marko Petkovsek
1892:
1884: = 0,
1870: and
1848:
1847:
1795:
1774:
1773:
1762:
1750:
1744:
1743:
1730:
1726:
1719:
1707:
1701:
1700:
1699:
1692:
1679:
1678:
1677:
1671:
1667:
1657:
1655:
1648:
1626:
1624:
1621:
1620:
1581:
1567:
1565:
1542:
1539:
1538:
1507:
1495:
1489:
1488:
1475:
1471:
1464:
1452:
1446:
1445:
1444:
1437:
1424:
1423:
1422:
1416:
1412:
1402:
1400:
1394:
1383:
1377:
1374:
1373:
1346:
1334:
1328:
1327:
1326:
1311:
1307:
1300:
1288:
1282:
1281:
1280:
1273:
1260:
1259:
1258:
1252:
1248:
1233:
1222:
1216:
1213:
1212:
1206:
1154:
1151:
1150:
1068:
1065:
1064:
1054: and
1043:
1034:
1030:n = n
1000:
973:
959:
953:
950:
949:
905:
891:
854:
840:
834:
831:
830:
810:
809:
801:
795:
794:
780:
774:
773:
707:
698:
692:
691:
634:
620:
604:
595:
589:
588:
531:
517:
501:
492:
488:
431:
417:
409:
407:
404:
403:
314:
300:
294:
291:
290:
234:
228:
225:
224:
114:
111:
110:
100: and
89:
63:involving
53:Herbert S. Wilf
23:
22:
15:
12:
11:
5:
2013:
2003:
2002:
1988:
1987:
1981:
1973:
1972:External links
1970:
1969:
1968:
1963:
1951:
1948:
1947:
1946:
1925:
1919:
1891:
1888:
1862:
1861:
1846:
1843:
1840:
1837:
1834:
1831:
1828:
1825:
1822:
1819:
1816:
1813:
1810:
1807:
1804:
1801:
1798:
1796:
1794:
1791:
1788:
1785:
1782:
1779:
1776:
1775:
1772:
1765:
1760:
1756:
1753:
1747:
1739:
1736:
1733:
1729:
1722:
1717:
1713:
1710:
1704:
1695:
1690:
1687:
1682:
1674:
1670:
1666:
1663:
1660:
1654:
1651:
1649:
1647:
1644:
1641:
1638:
1635:
1632:
1629:
1628:
1608:
1607:
1593:
1590:
1587:
1584:
1579:
1576:
1573:
1570:
1564:
1561:
1558:
1555:
1552:
1549:
1546:
1532:
1531:
1520:
1517:
1510:
1505:
1501:
1498:
1492:
1484:
1481:
1478:
1474:
1467:
1462:
1458:
1455:
1449:
1440:
1435:
1432:
1427:
1419:
1415:
1411:
1408:
1405:
1397:
1392:
1389:
1386:
1382:
1367:
1366:
1355:
1349:
1344:
1340:
1337:
1331:
1325:
1320:
1317:
1314:
1310:
1303:
1298:
1294:
1291:
1285:
1276:
1271:
1268:
1263:
1255:
1251:
1247:
1244:
1241:
1236:
1231:
1228:
1225:
1221:
1205:
1202:
1173:
1170:
1167:
1164:
1161:
1158:
1147:
1146:
1135:
1132:
1129:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1105:
1102:
1099:
1096:
1093:
1090:
1087:
1084:
1081:
1078:
1075:
1072:
1041:
1032:
1019:
1018:
1007:
999:
996:
993:
990:
987:
984:
981:
976:
971:
968:
965:
962:
958:
943:
942:
931:
928:
925:
922:
919:
916:
913:
908:
903:
900:
897:
894:
890:
886:
883:
880:
877:
874:
871:
868:
865:
862:
857:
852:
849:
846:
843:
839:
824:
823:
808:
805:
800:
798:
796:
793:
790:
787:
784:
779:
777:
775:
772:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
739:
736:
733:
730:
727:
724:
721:
716:
713:
710:
706:
702:
697:
695:
693:
690:
687:
684:
681:
678:
675:
672:
669:
666:
663:
660:
657:
654:
651:
648:
645:
642:
637:
632:
629:
626:
623:
619:
613:
610:
607:
603:
599:
594:
592:
590:
587:
584:
581:
578:
575:
572:
569:
566:
563:
560:
557:
554:
551:
548:
545:
542:
539:
534:
529:
526:
523:
520:
516:
510:
507:
504:
500:
496:
491:
489:
487:
484:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
439:
434:
429:
426:
423:
420:
416:
412:
411:
388:
387:
376:
373:
370:
367:
364:
361:
358:
355:
352:
349:
346:
343:
340:
337:
334:
331:
328:
325:
322:
317:
312:
309:
306:
303:
299:
284:
283:
272:
269:
266:
263:
260:
257:
254:
251:
246:
243:
240:
237:
233:
222:
211:
208:
205:
202:
199:
196:
193:
190:
187:
184:
181:
178:
175:
172:
169:
166:
163:
160:
157:
154:
151:
148:
145:
142:
139:
136:
133:
130:
127:
124:
121:
118:
88:
85:
9:
6:
4:
3:
2:
2012:
2001:
2000:Combinatorics
1998:
1997:
1995:
1985:
1982:
1979:
1976:
1975:
1967:
1964:
1961:
1957:
1954:
1953:
1942:
1938:
1931:
1926:
1922:
1920:1-56881-063-6
1916:
1913:. AK Peters.
1912:
1911:
1906:
1902:
1898:
1894:
1893:
1887:
1885:
1883:
1877:
1875:
1874:
1869:
1868:
1844:
1838:
1835:
1832:
1829:
1826:
1820:
1814:
1811:
1808:
1802:
1799:
1797:
1789:
1786:
1783:
1777:
1770:
1758:
1754:
1751:
1737:
1734:
1731:
1727:
1715:
1711:
1708:
1688:
1685:
1672:
1664:
1661:
1652:
1650:
1642:
1639:
1636:
1630:
1619:
1618:
1617:
1615:
1614:
1591:
1588:
1585:
1582:
1577:
1574:
1571:
1568:
1562:
1556:
1553:
1550:
1544:
1537:
1536:
1535:
1518:
1515:
1503:
1499:
1496:
1482:
1479:
1476:
1472:
1460:
1456:
1453:
1433:
1430:
1417:
1409:
1406:
1390:
1387:
1384:
1380:
1372:
1371:
1370:
1353:
1342:
1338:
1335:
1323:
1318:
1315:
1312:
1308:
1296:
1292:
1289:
1269:
1266:
1253:
1245:
1242:
1229:
1226:
1223:
1219:
1211:
1210:
1209:
1201:
1199:
1195:
1194:
1189:
1188:
1168:
1165:
1162:
1156:
1133:
1127:
1124:
1121:
1118:
1115:
1109:
1103:
1100:
1097:
1091:
1088:
1082:
1079:
1076:
1070:
1063:
1062:
1061:
1059:
1058:
1053:
1052:
1046:
1044:
1040:
1035:
1031:
1026:
1025:
1005:
997:
991:
988:
985:
979:
966:
963:
960:
956:
948:
947:
946:
929:
923:
920:
917:
911:
898:
895:
892:
888:
884:
878:
875:
872:
869:
866:
860:
847:
844:
841:
837:
829:
828:
827:
806:
803:
799:
791:
788:
785:
782:
778:
764:
761:
758:
755:
749:
746:
740:
737:
734:
731:
728:
722:
708:
700:
696:
682:
679:
676:
670:
667:
661:
658:
655:
652:
649:
643:
635:
630:
627:
624:
621:
617:
605:
597:
593:
579:
576:
573:
567:
564:
558:
555:
552:
549:
546:
540:
532:
527:
524:
521:
518:
514:
502:
494:
490:
479:
476:
473:
467:
464:
458:
455:
452:
449:
446:
440:
424:
421:
418:
414:
402:
401:
400:
398:
395:
394:
374:
371:
362:
359:
356:
350:
347:
341:
338:
335:
332:
329:
323:
307:
304:
301:
297:
289:
288:
287:
270:
267:
261:
258:
255:
249:
241:
235:
223:
209:
203:
200:
197:
191:
188:
182:
179:
176:
173:
170:
164:
161:
155:
152:
149:
143:
140:
134:
131:
128:
125:
122:
116:
109:
108:
107:
105:
104:
99:
98:
94:
84:
82:
78:
74:
70:
66:
62:
58:
54:
50:
46:
42:
38:
34:
33:combinatorics
30:
19:
1943:(4): 508–509
1940:
1936:
1909:
1901:Herbert Wilf
1881:
1880:
1878:
1872:
1871:
1866:
1865:
1863:
1612:
1611:
1609:
1533:
1368:
1207:
1197:
1192:
1191:
1186:
1185:
1148:
1056:
1055:
1050:
1049:
1047:
1038:
1037:
1029:
1028:
1023:
1022:
1020:
944:
825:
392:
391:
389:
285:
102:
101:
96:
95:
90:
41:WZ pair
40:
36:
26:
1937:AMS Notices
826:Therefore,
29:mathematics
1890:References
397:telescopes
87:Definition
69:factorials
49:identities
39:, or
1836:−
1735:−
1662:−
1575:−
1480:−
1407:−
1396:∞
1381:∑
1316:−
1243:−
1235:∞
1220:∑
1125:−
975:∞
970:∞
967:−
957:∑
907:∞
902:∞
899:−
889:∑
856:∞
851:∞
848:−
838:∑
789:−
762:−
747:−
715:∞
712:→
668:−
628:−
618:∑
612:∞
609:→
565:−
525:−
515:∑
509:∞
506:→
465:−
433:∞
428:∞
425:−
415:∑
348:−
316:∞
311:∞
308:−
298:∑
245:∞
242:±
239:→
189:−
141:−
93:functions
91:Two
55:and
45:functions
35:, a
18:WZ theory
1994:Category
1950:See also
1907:(1996).
1616:, where
1048:If
945:that is
27:In
1204:Example
1917:
1149:where
1933:(PDF)
1002:const
1915:ISBN
1903:and
1864:Now
1190:and
61:sums
1910:A=B
705:lim
602:lim
499:lim
232:lim
1996::
1941:57
1939:,
1935:,
1899:;
1519:1.
1200:.
1045:.
807:0.
399::
271:0.
83:.
67:,
1962:.
1945:.
1923:.
1882:n
1873:G
1867:F
1845:.
1842:)
1839:1
1833:k
1830:,
1827:n
1824:(
1821:F
1818:)
1815:k
1812:,
1809:n
1806:(
1803:R
1800:=
1793:)
1790:k
1787:,
1784:n
1781:(
1778:G
1771:,
1764:)
1759:n
1755:n
1752:2
1746:(
1738:k
1732:n
1728:4
1721:)
1716:k
1712:k
1709:2
1703:(
1694:)
1689:k
1686:n
1681:(
1673:k
1669:)
1665:1
1659:(
1653:=
1646:)
1643:k
1640:,
1637:n
1634:(
1631:F
1613:n
1592:1
1589:+
1586:n
1583:2
1578:1
1572:k
1569:2
1563:=
1560:)
1557:k
1554:,
1551:n
1548:(
1545:R
1516:=
1509:)
1504:n
1500:n
1497:2
1491:(
1483:k
1477:n
1473:4
1466:)
1461:k
1457:k
1454:2
1448:(
1439:)
1434:k
1431:n
1426:(
1418:k
1414:)
1410:1
1404:(
1391:0
1388:=
1385:k
1354:.
1348:)
1343:n
1339:n
1336:2
1330:(
1324:=
1319:k
1313:n
1309:4
1302:)
1297:k
1293:k
1290:2
1284:(
1275:)
1270:k
1267:n
1262:(
1254:k
1250:)
1246:1
1240:(
1230:0
1227:=
1224:k
1193:k
1187:n
1172:)
1169:k
1166:,
1163:n
1160:(
1157:R
1134:,
1131:)
1128:1
1122:k
1119:,
1116:n
1113:(
1110:F
1107:)
1104:k
1101:,
1098:n
1095:(
1092:R
1089:=
1086:)
1083:k
1080:,
1077:n
1074:(
1071:G
1057:G
1051:F
1042:0
1039:n
1033:0
1024:n
1006:.
998:=
995:)
992:k
989:,
986:n
983:(
980:F
964:=
961:k
930:,
927:)
924:k
921:,
918:n
915:(
912:F
896:=
893:k
885:=
882:)
879:k
876:,
873:1
870:+
867:n
864:(
861:F
845:=
842:k
804:=
792:0
786:0
783:=
771:]
768:)
765:M
759:,
756:n
753:(
750:G
744:)
741:1
738:+
735:M
732:,
729:n
726:(
723:G
720:[
709:M
701:=
689:]
686:)
683:k
680:,
677:n
674:(
671:G
665:)
662:1
659:+
656:k
653:,
650:n
647:(
644:G
641:[
636:M
631:M
625:=
622:k
606:M
598:=
586:]
583:)
580:k
577:,
574:n
571:(
568:F
562:)
559:k
556:,
553:1
550:+
547:n
544:(
541:F
538:[
533:M
528:M
522:=
519:k
503:M
495:=
486:]
483:)
480:k
477:,
474:n
471:(
468:F
462:)
459:k
456:,
453:1
450:+
447:n
444:(
441:F
438:[
422:=
419:k
393:G
375:0
372:=
369:]
366:)
363:k
360:,
357:n
354:(
351:F
345:)
342:k
339:,
336:1
333:+
330:n
327:(
324:F
321:[
305:=
302:k
268:=
265:)
262:M
259:,
256:n
253:(
250:G
236:M
210:,
207:)
204:k
201:,
198:n
195:(
192:G
186:)
183:1
180:+
177:k
174:,
171:n
168:(
165:G
162:=
159:)
156:k
153:,
150:n
147:(
144:F
138:)
135:k
132:,
129:1
126:+
123:n
120:(
117:F
103:G
97:F
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.