与えられた2つの $n$ 次正方行列 $N$ と $U$ の $k$ 乗 $N^k$ と $U^k$ ($k \in \mathbb{N}$) を計算する問題です。 ここで、$N$ と $U$ は以下の行列です。 $N = \begin{bmatrix} 0 & & & \\ & 0 & & \\ & & \ddots & \\ & & & 0 \end{bmatrix}$ $U = \begin{bmatrix} 1 & 1 & & \\ & 1 & \ddots & \\ & & \ddots & 1 \\ & & & 1 \end{bmatrix}$ ただし、$N$ は対角成分が全て0の対角行列、$U$ は対角成分と右上隣の成分が1で、それ以外の成分が0の上三角行列です。

1. 問題の内容

与えられた2つの $n$ 次正方行列 $N$ と $U$ の $k$ 乗 $N^k$ と $U^k$ ($k \in \mathbb{N}$) を計算する問題です。

ここで、$N$ と $U$ は以下の行列です。

$N = \begin{bmatrix} 0 & & & \\ & 0 & & \\ & & \ddots & \\ & & & 0 \end{bmatrix}$

$U = \begin{bmatrix} 1 & 1 & & \\ & 1 & \ddots & \\ & & \ddots & 1 \\ & & & 1 \end{bmatrix}$

ただし、$N$ は対角成分が全て0の対角行列、$U$ は対角成分と右上隣の成分が1で、それ以外の成分が0の上三角行列です。

2. 解き方の手順

まず、$N$ の $k$ 乗を計算します。$N$ は対角成分がすべて0の対角行列なので、

$N^k = \begin{bmatrix} 0^k & & & \\ & 0^k & & \\ & & \ddots & \\ & & & 0^k \end{bmatrix} = \begin{bmatrix} 0 & & & \\ & 0 & & \\ & & \ddots & \\ & & & 0 \end{bmatrix} = O$

ただし、$O$ は全ての要素が0の $n$ 次正方行列（零行列）です。

次に、$U$ の $k$ 乗を計算します。$U$ は以下のように表されます。

$U = I + A$

ここで、$I$ は単位行列、$A$ は対角成分とその上の対角線上の成分が1で、それ以外の成分が0の行列です。

$A = \begin{bmatrix} 0 & 1 & & \\ & 0 & \ddots & \\ & & \ddots & 1 \\ & & & 0 \end{bmatrix}$

$A^2 = \begin{bmatrix} 0 & 0 & 1 & \\ & 0 & 0 & \ddots \\ & & 0 & 0 \\ & & & 0 \end{bmatrix}$

...

$A^{n-1} = \begin{bmatrix} 0 & 0 & \dots & 0 & 1 \\ & 0 & 0 & \dots & 0 \\ & & \ddots & & \vdots \\ & & & 0 & 0 \\ & & & & 0 \end{bmatrix}$

$A^n = O$

$U^k = (I + A)^k = \sum_{i=0}^k \binom{k}{i} A^i = I + \binom{k}{1} A + \binom{k}{2} A^2 + \dots + \binom{k}{n-1} A^{n-1}$

なぜならば、$A^i = 0$ for $i \ge n$ だからです。

よって、

$U^k = \begin{bmatrix} 1 & \binom{k}{1} & \binom{k}{2} & \dots & \binom{k}{n-1} \\ & 1 & \binom{k}{1} & \dots & \binom{k}{n-2} \\ & & \ddots & & \vdots \\ & & & 1 & \binom{k}{1} \\ & & & & 1 \end{bmatrix}$

ここで、$\binom{k}{i} = \frac{k!}{i!(k-i)!}$ です。

3. 最終的な答え

$N^k = O$ (零行列)

$U^k = \begin{bmatrix} 1 & \binom{k}{1} & \binom{k}{2} & \dots & \binom{k}{n-1} \\ & 1 & \binom{k}{1} & \dots & \binom{k}{n-2} \\ & & \ddots & & \vdots \\ & & & 1 & \binom{k}{1} \\ & & & & 1 \end{bmatrix}$