Пара Уилф – Зейлбергер

В математике , особенно в комбинаторике , пара Уилфа-Цейлбергера или пара WZ — это пара функций , которые можно использовать для подтверждения определенных комбинаторных тождеств . Пары WZ названы в честь Герберта С. Уилфа и Дорона Зейлбергера и играют важную роль в вычислении многих сумм , включающих биномиальные коэффициенты , факториалы и вообще любые гипергеометрические ряды . Аналог функции WZ можно использовать для нахождения эквивалентной и гораздо более простой суммы. Хотя поиск пар WZ вручную в большинстве случаев непрактичен, алгоритм Госпера предоставляет метод поиска аналога WZ функции и может быть реализован в программе символьных манипуляций .

Определение

Две функции F и G образуют пару WZ тогда и только тогда, когда выполняются следующие два условия:

F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k),

\lim _{M\to \pm \infty }G(n,M)=0.

В совокупности эти условия гарантируют, что

\sum _{k=-\infty }^{\infty }[F(n+1,k)-F(n,k)]=0

потому что функция G телескопирует :

{\begin{aligned}\sum _{k=-\infty }^{\infty }[F(n+1,k)-F(n,k)]&{}=\lim _{M\to \infty }\sum _{k=-M}^{M}[F(n+1,k)-F(n,k)]\\&{}=\lim _{M\to \infty }\sum _{k=-M}^{M}[G(n,k+1)-G(n,k)]\\&{}=\lim _{M\to \infty }[G(n,M+1)-G(n,-M)]\\&{}=0-0\\&{}=0.\end{aligned}}

Поэтому,

\sum _{k=-\infty }^{\infty }F(n+1,k)=\sum _{k=-\infty }^{\infty }F(n,k),

то есть

\sum _{k=-\infty }^{\infty }F(n,k)={\text{const}}.

Константа не зависит от n .Его значение можно найти, подставив n = n ₀для конкретного n ₀ .

Если F и G образуют пару WZ, то они удовлетворяют соотношению

G(n,k)=R(n,k)F(n,k-1),

где $R(n,k)$ является рациональной функцией от n и k и называется сертификатом доказательства WZ .

Пара Уилфа – Цейлбергера может использоваться для проверки личности.

\sum _{k=0}^{\infty }(-1)^{k}{n \choose k}{2k \choose k}4^{n-k}={2n \choose n}.

Разделим тождество на его правую часть:

\sum _{k=0}^{\infty }{\frac {(-1)^{k}{n \choose k}{2k \choose k}4^{n-k}}{2n \choose n}}=1.

Используйте подтверждающий сертификат

R(n,k)={\frac {2k-1}{2n+1}}

чтобы убедиться, что левая часть не зависит от n ,где

{\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}}

Теперь F и G образуют пару Вилфа–Цейлбергера.

Чтобы доказать, что константа в правой части тождества равна 1, подставьте n = 0 , например, .

Алгоритм Госпера дает метод генерации пар WZ, если они существуют.
Генерирующая функция предоставляет подробную информацию о методе сертификации личности WZ.