Proving equivalence of two sums involving Krawtchuk polynomials and binomial co-efficients

Question

I seem to have chanced upon a new characterization for Kravchuk polynomials. [http://en.wikipedia.org/wiki/Kravchuk_polynomials].

To begin with, let us define the function $\omega(n,p)$ as [Assuming $\binom{a}{b}=0$ when $b>a$].,

$\omega \left( {n,p} \right) = \sum\limits_{i = 0}^{\,\frac{{n - 1}}{2}} {{{\left( { - 1} \right)}^i}} \left( {\begin{array}{*{20}{c}} {n - p} \\ i \end{array}} \right)\sum\limits_{k = 0}^{\left( {\frac{{n - 1}}{2}} \right) - i} {\left( {\begin{array}{*{20}{c}} p \\ k \end{array}} \right)} $.

The result I seek to prove is, for $0 \leqslant p \leqslant n - 1$, $\omega \left( {n,p} \right) = {\rm K}\left( {n - 1,\left( {\frac{{n - 1}}{2}} \right),n - p - 1} \right)$, where, ${\rm K}(.,.,.,)$ is the Kravchuk polynomial defined by, $\begin{gathered} {\rm K}\left( {N,k,x} \right) = \sum\limits_{j = 0}^{\,k} {{{\left( { - 1} \right)}^j}} \left( {\begin{array}{*{20}{c}} x \\ j \end{array}} \right)\left( {\begin{array}{*{20}{c}} {N - x} \\ {k - j} \end{array}} \right) \\ \quad \quad \quad \quad \;\, = \sum\limits_{j = 0}^{\,k} {{{\left( { - 2} \right)}^j}} \left( {\begin{array}{*{20}{c}} {N - j} \\ {k - j} \end{array}} \right)\left( {\begin{array}{*{20}{c}} x \\ j \end{array}} \right) \\ \quad \quad \quad \quad \;\, = \sum\limits_{j = 0}^k {{{\left( { - 1} \right)}^j}{2^{k - j}}\left( {\begin{array}{*{20}{c}} {N - k + j} \\ j \end{array}} \right)\left( {\begin{array}{*{20}{c}} {N - x} \\ {k - j} \end{array}} \right)} \\ \end{gathered} $.

So, in short, I need to prove that the summation on the LHS is the same as one of the 3 on the RHS:

$\begin{gathered} \sum\limits_{i = 0}^{\,\frac{{n - 1}}{2}} {{{\left( { - 1} \right)}^i}} \left( {\begin{array}{*{20}{c}} {n - p} \\ i \end{array}} \right)\sum\limits_{k = 0}^{\left( {\frac{{n - 1}}{2}} \right) - i} {\left( {\begin{array}{*{20}{c}} p \\ k \end{array}} \right)} = \sum\limits_{j = 0}^{\,\frac{{n - 1}}{2}} {{{\left( { - 1} \right)}^j}} \left( {\begin{array}{*{20}{c}} {n - p - 1} \\ j \end{array}} \right)\left( {\begin{array}{*{20}{c}} p \\ {\left( {\frac{{n - 1}}{2}} \right) - j} \end{array}} \right) \quad \quad \quad \quad \;\quad \quad \quad \quad \;\,\quad \quad = \sum\limits_{j = 0}^{\,k} {{{\left( { - 2} \right)}^j}} \left( {\begin{array}{*{20}{c}} {n - 1 - j} \\ {\left( {\frac{{n - 1}}{2}} \right) - j} \end{array}} \right)\left( {\begin{array}{*{20}{c}} {n - p - 1} \\ j \end{array}} \right) \quad \quad \quad \quad \;\quad \quad \quad \quad \;\quad \quad = \sum\limits_{j = 0}^k {{{\left( { - 1} \right)}^j}{2^{\left( {\frac{{n - 1}}{2}} \right) - j}}\left( {\begin{array}{*{20}{c}} {\left( {\frac{{n - 1}}{2}} \right) + j} \\ j \end{array}} \right)\left( {\begin{array}{*{20}{c}} p \\ {\left( {\frac{{n - 1}}{2}} \right) + j} \end{array}} \right)} \end{gathered} $.

Any help/clues/tricks would be much appreciated. I tried using the 2f1 hyper-geometric function based results for the partial 'pascal-sum' on the LHS and it all became real messy soon without achieving much headway.

In case you want to verify this numerically, here is a MATLAB script for the same: clear all; clc; % k=0,1,..., n. % n being positive integer % x : variable

n=15; for p=0:n-1

N=n-1;
k=(n-1)/2;

x=n-p-1;

% q=2;
for j=0:(n-1)/2
    s_RHS(j+1)=(-1)^j*nCk(n-p,j)*T_mn(p,(n-1)/2-j);
    % The Kravchuk polynomial has following alternative expressions:
    s_LHS_1(j+1) = (-1)^j * nCk(x,j)* nCk((n-1)-(n-p-1),((n-1)/2)-j);
    s_LHS_2(j+1)=(-2)^j * nCk((n-1)-j,((n-1)/2)-j)* nCk((n-p-1),j);
    s_LHS_3(j+1)=(-1)^j* 2^(((n-1)/2)-j)* nCk(((n-1)/2)+j,j)* nCk(p,((n-1)/2)-j) ;
end
[s_RHS' s_LHS_1' s_LHS_2' s_LHS_3']
[  sum([s_RHS' s_LHS_1' s_LHS_2' s_LHS_3'])]

end

% function x=nCk(n,k) % if(k>n) % x=0; % else % x=nchoosek(n,k); % end

Thanks!

Answer 1

2f1 hypergeometric function??? I wish I had the slightest idea of how to use it for anything I need. :-). Anyway, any time you see double summation versus single summation, the chances that it is just a telescopic sum in disguise are about 20%, so you can always try to bet a decent amount of your time on that. This case is no exception:

$$ \sum_{i+k=q}(-1)^i{n-p-1\choose i}{p\choose k}-\sum_{i+k=q-1}(-1)^i{n-p-1\choose i}{p\choose k} \\ \sum_{i+k=q}(-1)^i\left[{n-p-1\choose i}{p\choose k}+{n-p-1\choose i-1}{p\choose k}\right] \\ =\sum_{i+k=q}(-1)^i{n-p\choose i}{p\choose k} $$ (I just paired $(i,k)$ with $(i-1,k)$ with the usual convention that ${m\choose -1}=0$). Now add from $q=0$ to $q=\frac{n-1}2$ to get the identity you want with Sum I in your list on the right hand side.