Source: Wikipedia, the free encyclopedia.
In
hypergeometric series. 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,
Gosper's algorithm provides a sure method to find a function's WZ counterpart, and can be implemented in a
symbolic manipulation program .
Definition Two functions F G
F
(
n
+
1
,
k
)
−
F
(
n
,
k
)
=
G
(
n
,
k
+
1
)
−
G
(
n
,
k
)
,
{\displaystyle F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k),}
lim
M
→
±
∞
G
(
n
,
M
)
=
0.
{\displaystyle \lim _{M\to \pm \infty }G(n,M)=0.}
Together, these conditions ensure that
∑
k
=
−
∞
∞
[
F
(
n
+
1
,
k
)
−
F
(
n
,
k
)
]
=
0
{\displaystyle \sum _{k=-\infty }^{\infty }[F(n+1,k)-F(n,k)]=0}
because the function G telescopes :
∑
k
=
−
∞
∞
[
F
(
n
+
1
,
k
)
−
F
(
n
,
k
)
]
=
lim
M
→
∞
∑
k
=
−
M
M
[
F
(
n
+
1
,
k
)
−
F
(
n
,
k
)
]
=
lim
M
→
∞
∑
k
=
−
M
M
[
G
(
n
,
k
+
1
)
−
G
(
n
,
k
)
]
=
lim
M
→
∞
[
G
(
n
,
M
+
1
)
−
G
(
n
,
−
M
)
]
=
0
−
0
=
0.
{\displaystyle {\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}}}
Therefore,
∑
k
=
−
∞
∞
F
(
n
+
1
,
k
)
=
∑
k
=
−
∞
∞
F
(
n
,
k
)
,
{\displaystyle \sum _{k=-\infty }^{\infty }F(n+1,k)=\sum _{k=-\infty }^{\infty }F(n,k),}
that is
∑
k
=
−
∞
∞
F
(
n
,
k
)
=
const
.
{\displaystyle \sum _{k=-\infty }^{\infty }F(n,k)={\text{const}}.}
The constant does not depend on n n = n 0 n 0
If F G
G
(
n
,
k
)
=
R
(
n
,
k
)
F
(
n
,
k
−
1
)
,
{\displaystyle G(n,k)=R(n,k)F(n,k-1),}
where
R
(
n
,
k
)
{\displaystyle R(n,k)}
n k WZ proof certificate .
Example A Wilf–Zeilberger pair can be used to verify the identity
∑
k
=
0
∞
(
−
1
)
k
(
n
k
)
(
2
k
k
)
4
n
−
k
=
(
2
n
n
)
.
{\displaystyle \sum _{k=0}^{\infty }(-1)^{k}{n \choose k}{2k \choose k}4^{n-k}={2n \choose n}.}
Divide the identity by its right-hand side:
∑
k
=
0
∞
(
−
1
)
k
(
n
k
)
(
2
k
k
)
4
n
−
k
(
2
n
n
)
=
1.
{\displaystyle \sum _{k=0}^{\infty }{\frac {(-1)^{k}{n \choose k}{2k \choose k}4^{n-k}}{2n \choose n}}=1.}
Use the proof certificate
R
(
n
,
k
)
=
2
k
−
1
2
n
+
1
{\displaystyle R(n,k)={\frac {2k-1}{2n+1}}}
to verify that the left-hand side does not depend on n
F
(
n
,
k
)
=
(
−
1
)
k
(
n
k
)
(
2
k
k
)
4
n
−
k
(
2
n
n
)
,
G
(
n
,
k
)
=
R
(
n
,
k
)
F
(
n
,
k
−
1
)
.
{\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}}}
Now F G
To prove that the constant in the right-hand side of the identity is 1, substitute n = 0,
References See also External links 
![{\displaystyle \sum _{k=-\infty }^{\infty }[F(n+1,k)-F(n,k)]=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32805d72a6813d27800bc28679d4bc9886323aed)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74f2e62d325560fdd668464f8dcd8da05463cc5e)
