数学の命題示しました

主に組合せ論について,読んだ本で出てきたことや,考えたことを書きます.

cosのn倍角公式〜チェビシェフ多項式の話1

概要
 \cos n倍角公式 (第一種チェビシェフ多項式)を求める方法を四通り紹介します.

\cos n\theta (n\in\mathbb{Z}_{\geq 0})は以下のように\cos\theta多項式として表せます.
 \cos 0 = 1,
 \cos \theta = \cos\theta,
 \cos 2\theta = 2\cos^2\theta-1,
 \cos 3\theta = 4\cos^3\theta-3\cos\theta,
 \vdots
その具体的な式形を\cos n倍角公式と呼ぶと思いますが,文脈によっては「第一種チェビシェフ多項式」と呼ぶこともあります.

詳しい解説はWikipediaを見てください.
チェビシェフ多項式 - Wikipedia


この記事では,一般の(n\in\mathbb{Z}_{\geq 0})について\cos n\theta\cos\theta多項式として表す具体的な式を,趣の異なる四通りの方法で求めてみようと思います.

以下では, \cos n\theta\cos\thetaで表す多項式 T_n(\cos\theta)と書くことにします.
つまり,\cos n\theta=T_n(\cos\theta)であり,
 T_0(x) = 1,
 T_1(x) = x,
 T_2(x) = 2x^2-1,
 T_3(x) = 4x^3-3x,
 \vdots
です.我々が知りたいのは T_n(x)です.

記号の約束

以下では,\lfloor x\rfloorxを超えない最大の整数を表し, \binom{n}{r}は二項係数 {}_nC_{r}を表すとします.

方法1:ド・モアブルの定理を使う

ド・モアブルの定理
 (\cos\theta+i\sin\theta)^n=\cos n\theta+i\sin n\theta
を使います.

命題
多項式 T_n(x)は以下で表される.
 T_n(x)=\displaystyle\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}x^{n-2k}(x^2-1)^k
証明
ド・モアブルの定理
 \cos n\theta+i\sin n\theta= (\cos\theta+i\sin\theta)^n
の右辺を展開して実部と虚部に分ける.

 (\cos\theta+i\sin\theta)^n=\displaystyle\sum_{k=0}^n\binom{n}{k}\cos^{n-k}\theta(i\sin\theta)^{k}
 =\displaystyle\sum_{0\leq k\leq n,\\k{\rm は偶数}}\binom{n}{k}(-1)^{\frac{k}{2}}\cos^{n-k}\theta\sin^k\theta+i\sum_{0\leq k\leq n,\\k{\rm は奇数}}\binom{n}{k}(-1)^{\frac{k-1}{2}}\cos^{n-k}\theta\sin^k\theta

実部を取り出すと,
 \cos n\theta=\displaystyle\sum_{0\leq k\leq n,\\k{\rm は偶数}}\binom{n}{k}(-1)^{\frac{k}{2}}\cos^{n-k}\theta\sin^k\theta


和の変数を kから \ell=\frac{k}{2}に変えて,\sin^2\theta=1-\cos^2\thetaを用いると
  \cos n\theta=\displaystyle\sum_{0\leq \ell\leq \lfloor\frac{n}{2}\rfloor}\binom{n}{2\ell}(-1)^{\ell}\cos^{n-2\ell}\theta\sin^{2\ell}\theta
=\displaystyle\sum_{0\leq \ell\leq \lfloor\frac{n}{2}\rfloor}\binom{n}{2\ell}(-1)^{\ell}\cos^{n-2\ell}\theta(1-\cos^2\theta)^\ell
 =\displaystyle\sum_{0\leq \ell\leq \lfloor\frac{n}{2}\rfloor}\binom{n}{2\ell}\cos^{n-2\ell}\theta(\cos^2\theta-1)^\ell
[証明終わり]

ド・モアブルの定理を使う証明方法は以下のサイトを参考に書きました.
チェビシェフの多項式(cosのn倍角の公式) | 数学の偏差値を上げて合格を目指す

方法2:漸化式を作って解く

 T_n(x)が満たすべき漸化式を立てて解きます.

命題 ( T_n(x)が満たす漸化式.)
 T_n(x)は以下の漸化式により定まる.
 T_0(x)=1,
 T_1(x)=x,
 T_{n+1}(x)=2xT_n(x)-T_{n-1}(x),\quad(n\geq 1).
証明
加法定理から
 \cos(n-1)\theta=\cos n\theta\cos\theta+\sin n\theta\sin\theta,
 \cos(n+1)\theta=\cos n\theta\cos\theta-\sin n\theta\sin\theta

である.辺々足すと
 \cos(n-1)\theta + \cos(n+1)\theta = 2\cos\theta\cos n\theta
である.
よって, T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)が成立.
 T_0(x)=1,\ T_1(x)=xも, T_n(x)の定義より成立.
命題の漸化式を満たす多項式の列は一意に定まることから,それは T_n(x)である.
[証明終わり]

命題
多項式 T_n(x)は以下で表される.
 \displaystyle T_n(x)=\frac{\left(x+\sqrt{x^2-1}\right)^n+\left(x-\sqrt{x^2-1}\right)^n}{2}
証明
上で示した漸化式は行列を使うと以下のように書ける.
\begin{bmatrix}T_{n+1}\\T_{n}\end{bmatrix}=\begin{bmatrix}2x & -1 \\1 & 0 \end{bmatrix}\begin{bmatrix}T_{n}\\T_{n-1}\end{bmatrix}
初期値は T_0=1, T_1=xなので
\begin{bmatrix}T_{n+1}\\T_{n}\end{bmatrix}=\begin{bmatrix}2x & -1 \\1 & 0 \end{bmatrix}^n\begin{bmatrix}x\\1\end{bmatrix}
である.あとはこの行列
A\triangleq\begin{bmatrix}2x & -1 \\1 & 0 \end{bmatrix}
 n乗を求めればよい.行列 Aは,行列
P\triangleq\begin{bmatrix}1 & 1 \\x-\sqrt{x^2-1} & x+\sqrt{x^2-1} \end{bmatrix}
により対角化できて,
P^{-1}AP=\begin{bmatrix}x+\sqrt{x^2-1} & 0 \\0 & x-\sqrt{x^2-1} \end{bmatrix}
より,結局
A^n=\begin{bmatrix}\left(x+\sqrt{x^2-1}\right)^{n+1}-\left(x-\sqrt{x^2-1}\right)^{n+1} & -\left(x+\sqrt{x^2-1}\right)^{n}+\left(x-\sqrt{x^2-1}\right)^{n} \\\left(x-\sqrt{x^2-1}\right)\left(x+\sqrt{x^2-1}\right)^{n}-\left(x+\sqrt{x^2-1}\right)\left(x-\sqrt{x^2-1}\right)^{n} & -\left(x-\sqrt{x^2-1}\right)\left(x+\sqrt{x^2-1}\right)^{n}+\left(x+\sqrt{x^2-1}\right)\left(x-\sqrt{x^2-1}\right)^{n} \end{bmatrix}
となり, T_nが得られる.
[証明終わり]

この方法を解説しているサイトは,探した感じだと
チェビシェフ多項式の計算法
などがありました.

チェビシェフ多項式の母関数

多項式 \{T_n(x)\}_{n=0}^\inftyの母関数とは,二変数 t,nに関する形式的冪級数
 \displaystyle\sum_{n=0}^\infty T_n(x)t^n
のことです.これをチェビシェフ多項式の母関数と呼びましょう.
一般にある数列の性質を知りたいときには,その母関数のきれいな表示が分かると嬉しいことが多いです.
チェビシェフ多項式の母関数のきれいな表示を計算する方法は色々ありますが,ここでは上で求めた漸化式を使ってみます.

命題 (チェビシェフ多項式の母関数)
チェビシェフ多項式の母関数は以下のように表される.
 \displaystyle\sum_{n=0}^\infty T_n(x)t^n=\frac{1-tx}{1-2tx+t^2}.
証明
漸化式T_{n+2}=2xT_{n+1}-T_nの両辺に t^{n+2}をかけ, nについて和を取ると
 \displaystyle\sum_{n=0}^\infty T_{n+2}t^{n+2}=2tx\sum_{n=0}^{\infty}T_{n+1}t^{n+1}-t^2\sum_{n=0}^\infty T_nt^n.
ここから和の中身を揃え以下のようにする.
 \displaystyle\sum_{n=0}^\infty T_{n}t^{n}-T_0-T_1t=2tx\left(\sum_{n=0}^{\infty}T_{n}t^{n}-T_0\right)-t^2\sum_{n=0}^\infty T_nt^n.
初期値は T_0=1, T_1=xなので,
 \displaystyle\sum_{n=0}^\infty T_{n}t^{n}-1-tx=2tx\left(\sum_{n=0}^{\infty}T_{n}t^{n}-1\right)-t^2\sum_{n=0}^\infty T_nt^n.

これを \displaystyle\sum_{n=0}^\infty T_{n}t^{n}について解けば主張が得られる.
[証明終わり]

チェビシェフ多項式のきれいな表示を計算する他の方法として
ド・モルガンの定理を使う方法があり,以下のサイトで紹介されています.
チェビシェフの多項式

方法3:母関数を展開する

上で求めた母関数を再び
 \displaystyle\frac{1-tx}{1-2tx+t^2}=\sum_{n=0}^\infty (\cdots\cdots)t^{n}
の形に展開することで, T_n(x)を求めます.

命題
多項式 T_n(x)は以下で表される.
 \displaystyle T_n(x)=\sum_{\ 0\leq k\leq n\\n\equiv k\ {\rm mod} 2}2^{k-1}(-1)^{(n-k)/2}\left(\binom{(n+k)/2}{(n-k)/2}+\binom{(n+k)/2-1}{(n-k)/2-1}\right)x^k
但し,上記の和は nと偶奇が一致する kだけを足すという意味である.
証明
 \displaystyle\frac{1-tx}{1-2tx+t^2}=\frac{1-tx}{1+t^2}\frac{1}{1-\frac{2t}{1+t^2}x}
ここで関係式 \displaystyle \frac{1}{1-r}=\sum_{n=0}^\infty r^nを使うと,
 \displaystyle\frac{1-tx}{1+t^2}\frac{1}{1-\frac{2t}{1+t^2}x}=\frac{1-tx}{1+t^2}\sum_{n=0}^\infty\left(\frac{2t}{1+t^2}\right)^nx^n
 \displaystyle=\sum_{n=0}^\infty\left(\frac{(2t)^n(1-t^2)}{2(t+t^2)^{n+1}}\right)x^n+\frac{1}{2}

和の中身 \displaystyle\frac{(2t)^n(1-t^2)}{2(t+t^2)^{n+1}}について考える.
関係式 \displaystyle \frac{1}{(1-z)^{m+1}}=\sum_{n=0}^\infty \binom{m+n}{n}z^nを使うと,
 \displaystyle\frac{(2t)^n(1-t^2)}{2(t+t^2)^{n+1}}=\frac{(2t)^n(1-t^2)}{2}\sum_{k=0}^\infty \binom{n+k}{k}(-t^2)^k
 \displaystyle=\frac{(2t)^n}{2}\left\{\sum_{k=0}^\infty\binom{n+k}{k}(-1)t^{2k}-\sum_{k=0}^\infty\binom{n+k}{k}(-1)t^{2k+1}\right\}
 \displaystyle=2^{n-1}\sum_{k=0}^{\infty}\left(\binom{n+k}{k}+\binom{n+k-1}{k-1}\right)(-1)^kt^{2k+n}-\frac{1}{2}\delta_{n,0}

但し, \delta_{n,0}クロネッカーのデルタ ( i=jのとき \delta_{i,j}=1 i\neq jのとき \delta_{i,j}=0)であり,負の二項係数の値は \displaystyle\binom{r}{-1}= \delta_{r,-1}である.

以上の計算から
 \displaystyle\frac{1-tx}{1-2tx+t^2}=\sum_{n=0}^\infty\sum_{k=0}^{\infty}2^{n-1}\left(\binom{n+k}{k}+\binom{n+k-1}{k-1}\right)(-1)^kt^{2k}(tx)^n
が成立することがわかる.

上記の式は
 \displaystyle\sum_{n=0}^\infty\sum_{k=0}^{\infty}f(n,k)t^{2k}(tx)^n
という形の和であるが,和の内部変数 n,kをいじることで,この和を
 \displaystyle\sum_{n=0}^\infty\sum_{k=0}^{\infty}g(n,k)x^kt^n
という形に書き変えることを考える.

 \displaystyle\sum_{n=0}^\infty\sum_{k=0}^{\infty}f(n,k)t^{2k}(tx)^n=f(0,0)+f(1,0)tx+f(0,1)t^2+f(2,0)t^2x^2+\cdots
において, t^ix^jの係数を表にしてみた.空欄は 0を意味する.

f:id:iwalion:20191113100942p:plain
t^ix^jの係数

これを見るに,
 \displaystyle\sum_{n=0}^\infty\sum_{k=0}^{\infty}f(n,k)t^{2k}(tx)^n=\sum_{n=0}^\infty\sum_{\ 0\leq k\leq n\\n\equiv k\ {\rm mod}2}f\left(k,\frac{n-k}{2}\right)x^kt^n
になりそう.
このことは数学的帰納法で示す必要があるが,省略する.
これを使って上で得た和の内部変数を取り替えれば,

 \displaystyle\frac{1-tx}{1-2tx+t^2}=\sum_{n=0}^\infty\sum_{\ 0\leq k\leq n\\n\equiv k\ {\rm mod} 2}2^{k-1}(-1)^{(n-k)/2}\left(\binom{(n+k)/2}{(n-k)/2}+\binom{(n+k)/2-1}{(n-k)/2-1}\right)x^kt^n
を得る.

一方, \displaystyle\sum_{n=0}^\infty T_n(x)t^n=\frac{1-tx}{1-2tx+t^2}
だったので,これらを比較すれば主張を得る.
[証明終わり]

方法4:母関数からチェビシェフの微分方程式を作って解く

この方法は,私の理解があやふやな部分があり,また少々天下り的です.
チェビシェフ多項式の母関数
 \displaystyle T(x,t)\triangleq \sum_{n=0}^\infty T_n(x)t^n=\frac{1-tx}{1-2tx+t^2}
から,形式的冪級数
 \displaystyle\sum_{n=0}^\infty n^2T_n(x)t^n
がどんな表示を持つかが計算できます.計算には以下の方法を使います.

命題
 \displaystyle f(t)=\sum_{n=0}^\infty a_nt^nのとき, \displaystyle\sum_{n=0}^\infty na_nt^n=t\frac{df(t)}{dt}である.
証明
 \displaystyle f(t)=\sum_{n=0}^\infty a_nt^n=a_0+a_1t+a_2t^2+a_3t^3+\cdots
である.微分すると
 \displaystyle \frac{df(t)}{dt}=a_1+2a_2t+3a_3t^2+\cdots
となる.よって,
 \displaystyle t\frac{df(t)}{dt}=a_1t+2a_2t^2+3a_3t^3+\cdots=\sum_{n=0}^\infty na_nt^n.
[証明終わり]

これを何度も使えば,
 \displaystyle \sum_{n=0}^\infty n^2a_nt^n=t\frac{d}{dt}\left(t\frac{df(t)}{dt}\right), \sum_{n=0}^\infty n^3a_nt^n=t\frac{d}{dt}\left(t\frac{d}{dt}\left(t\frac{df(t)}{dt}\right)\right)
なども言えます.

チェビシェフ多項式の母関数の場合は,
 \displaystyle\sum_{n=0}^\infty n^2T_n(x)t^n=t\frac{\partial}{\partial t}\left(t\frac{\partial T(x,t)}{\partial t}\right)=-\frac{t^5x+2t^4x^2-4t^4-2t^2x^2+4t^2-tx}{(t^2-2tx+1)^3}
となります.

突然ですが,これが T(x,t) xでの一階と二階の偏微分
 \displaystyle\frac{\partial T(x,t)}{\partial x}=\sum_{n=0}^\infty\frac{d}{dx}T_n(x)t^n={\frac {-{t}^{3}+t}{ \left( {t}^{2}-2\,tx+1 \right) ^{2}}},
 \displaystyle\frac{\partial^2 T(x,t)}{\partial x^2}=\sum_{n=0}^\infty\frac{d^2}{dx^2}T_n(x)t^n={\frac {-4\,{t}^{4}+4\,{t}^{2}}{ \left( {t}^{2}-2\,tx+1 \right) ^{3}}}
の線形結合で書けないかを考えてみることにします.

恒等式
 \displaystyle A\frac{\partial T(x,t)}{\partial x}+B\frac{\partial^2 T(x,t)}{\partial x^2}+t\frac{\partial}{\partial t}\left(t\frac{\partial T(x,t)}{\partial t}\right)=0
が成立する条件を考えると, A=-x,\ B=1-x^2であればよいことがわかります.

つまり,
 \displaystyle \sum_{n=0}^\infty\left((1-x^2)\frac{d^2T_n(x)}{dx}-x\frac{dT_n(x)}{dx}+n^2T_n(x)\right)=0
が成立して,よって我々が求めたい多項式 T_n(x)は,微分方程式
 \displaystyle (1-x^2)\frac{d^2T_n(x)}{dx}-x\frac{dT_n(x)}{dx}+n^2T_n(x)=0
の解であることが分かります.

この微分方程式は「チェビシェフの微分方程式」と呼ばれていてWikipediaもあります.
チェビシェフ方程式 - Wikipedia

これを適切な初期条件のもと解けば T_n(x)が求まるはずなのですが,それはいつか書くことにします.

その他の方法について

チェビシェフ多項式についての話題は他の多くのサイトで扱われているので,本記事で紹介しない方法を扱っているサイトを挙げておきます.

shadowacademy.web.fc2.com

  • 基本対称式を使う方法について

qiita.com