Wilf–Zeilberger-par

Från Wikipedia
Hoppa till: navigering, sök

Inom matematiken, specifikt inom kombinatorik, är ett Wilf–Zeilberger-par eller WZ-par ett par av funktioner som satisfierar vissa krav och som kan användas till att verifiera flera kombinatoriska identiteter. WZ-paren är uppkallade efter Herbert S. Wilf och Doron Zeilberger.

Definition[redigera | redigera wikitext]

Två funktioner F och G bildar ett WZ-par om fäljande är satisfierat:

F(n+1,k)-F(n,k) = G(n,k+1)-G(n,k)\,
\lim_{M \to \pm\infty}G(n,M) = 0. \,

I så fall är

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

eftersom

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

Om F och G blidar ett WZ-par satisfierar de relationen

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

där R(n,k) är en rationell funktion av n och k.

Exempel[redigera | redigera wikitext]

Ett WZ-par kan användas till att verifiera identiteten

\sum_{k=-\infty}^\infty (-1)^k {n \choose k} {2k \choose k} 4^{n-k} = {2n \choose n}

genom att använda

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

Definiera följande funktioner:

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

Då bildar F och G ett WZ-par.

Referenser[redigera | redigera wikitext]

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Wilf–Zeilberger pair, 9 december 2013.