0
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.