これでいけそうです。

二項係数は通常の通り範囲外では[math]0[/math]とする。これにより

[math]\sum_{k=j}^{\left[\frac n 2\right]}\binom n{2k}\binom k j = \sum_{k=0}^{\infty}\binom n{2k}\binom k j[/math]

と書ける。非負整数[math]n,j[/math]と実数[math]x[/math]について、[math]a(n,j),b(n,j)[/math]と母関数[math]f_n(x)[/math]を

[math]a(n,j) := \sum_{k=0}^{\infty}\binom n{2k}\binom k j[/math]

[math]b(n,j) := 2^{n-2j}\binom {n-j}j - 2^{n-1-2j}\binom {n-1-j}j[/math]

[math]f_n(x) := \sum_{k=0}^{\infty}\binom n{2k}x^k[/math]

で定める。証明すべきことは、任意の非負整数[math]n,j[/math]について

[math]a(n,j) = b(n,j)[/math]

である。以下、[math]n,j[/math]は非負整数とする。母関数を微分することで

[math]a(n,j)=\frac{1}{j!}f^{(j)}_n(1)[/math]

が分かる。また、母関数を計算すると

[math]f_n(x) = \frac{1}{2}\left(\left(1+\sqrt{x}\right)^n+\left(1-\sqrt{x}\right)^n\right)[/math]

となる。この関数は漸化式

[math]f_{n+2}(x)-2f_{n+1}(x)-(x-1)f_n(x) = 0[/math]

を満たす。これを[math]j+1[/math]回微分すると、

[math]f^{(j+1)}_{n+2}(x)-2f^{(j+1)}_{n+1}(x)-(j+1)f^{(j)}_n(x)-(x-1)f^{(j+1)}_n(x)=0[/math]

になるため、漸化式

[math]a(n+2,0)-2a(n+1,0)=0[/math]

[math]a(n+2,j+1)-2a(n+1,j+1)-a(n,j)=0[/math]

が成り立つ。また

[math]f_0(x) = 1[/math]

[math]f_1(x) = 1[/math]

なので、

[math]a(0,0)=a(1,0)=1[/math]

[math]a(0,j+1)=a(1,j+1)=0[/math]

となる。

[math]b(n,j)[/math]も同じ漸化式と初期値を満たすため、任意の非負整数[math]n,j[/math]について

[math]a(n,j) = b(n,j)[/math]

である。