高校数学解説

k-ナッチ数列の加法定理を求める

フィボナッチ数列,k-ナッチ数列,累積帰納法

501

追記

添え字の間違いを直しました(2025/06/07 02:17)

フィボナッチ数列の加法定理

フィボナッチ数列というのはみなさん知っているかと思われます

${\begin{cases} F_{0} = 0 \\ F_{1} = 1 \\ F_{n + 1} = F_{n} + F_{n - 1} \end{cases}$

このフィボナッチ数列には加法定理があるらしく、

$\begin{array}{rcl} F_{m + n} & = & F_{m - 1} F_{n} + F_{m} F_{n + 1} \end{array}$

となるらしいです。

帰納法による証明や、一般項の公式を使ったり、三角関数表示したり、行列の冪乗表示から証明したりしているものがありましたが、帰納法で証明したいと思います。

しかし、この式を最初に思いついた人はどうやって思いついたんでしょうか？

それはわからないです。(調べてないから)
でもこうすると思いついけます。

発想

$\begin{array}{rcl} F_{n + 1} & = & F_{n} + F_{n - 1} \\ F_{n + 2} & = & F_{n + 1} + F_{n} \\ = & F_{n} + F_{n - 1} + F_{n} \\ = & 2 F_{n} + F_{n - 1} \\ F_{n + 3} & = & F_{n + 2} + F_{n + 1} \\ = & 2 F_{n} + F_{n - 1} + F_{n} + F_{n - 1} \\ = & 3 F_{n} + 2 F_{n - 1} \end{array}$

おや、見た感じに $F_{n}$ と $F_{n - 1}$ で表せそうですよね
じゃぁ、 $F_{n + k}$ が $F_{n}$ と $F_{n - 1}$ でこう表せるとします

$\begin{array}{rcl} F_{n + k} & = & a (k) F_{n} + b (k) F_{n - 1} \end{array}$

ここで $a (k)$ と $b (k)$ は何かいい感じの整数だとします。

最初の方は
$\begin{array}{rcl} F_{n + 0} & = & a (0) F_{n} + b (0) F_{n - 1} \\ = & 1 F_{n} + 0 F_{n - 1} \\ F_{n + 1} & = & a (1) F_{n} + b (1) F_{n - 1} \\ = & 1 F_{n} + 1 F_{n - 1} \end{array}$
なので、 $a (0) = 1, b (0) = 0, a (1) = 1, b (1) = 1$ と分かります。

ここで、この次の $F_{n + (k + 1)}$ を考えると、
$\begin{array}{rcl} F_{n + k + 1} & = & a (k + 1) F_{n} + b (k + 1) F_{n - 1} \end{array}$
しかも、こうもできます
$\begin{array}{rcl} F_{n + k + 1} & = & F_{n + k} + F_{n + k - 1} \\ = & a (k) F_{n} + b (k) F_{n - 1} + a (k - 1) F_{n} + b (k - 1) F_{n - 1} \\ = & (a (k) + a (k - 1)) F_{n} + (b (k) + b (k - 1)) F_{n - 1} \end{array}$
ほう。じゃあ
$\begin{array}{rcl} a (k + 1) & = & a (k) + a (k - 1) \\ b (k + 1) & = & b (k) + b (k - 1) \end{array}$
となってくれないと困りますね。

...
ん???
んん？？？

これってフィボナッチ数列そのものじゃないですか？

$\begin{array}{rcl} a (0) & = & 1, a (1) = 1 \\ a (k + 1) & = & a (k) + a (k - 1) \\ b (0) & = & 0, b (1) = 1 \\ b (k + 1) & = & b (k) + b (k - 1) \end{array}$

ってことは、 $b (k)$ はそのまんまフィボナッチ数列 $F_{k}$ だし、
$a (k)$ はそれの一つずれたもので、 $F_{k + 1}$ じゃないですか？

ということで、フィボナッチ数列の加法定理が

フィボナッチ数列の加法定理

$\begin{array}{rcl} F_{n + k} & = & F_{k + 1} F_{n} + F_{k} F_{n - 1} \end{array}$

となるんですね。

トリボナッチ数列

トリボナッチ数列というものがあります。

${\begin{cases} T_{0} = 0 \\ T_{1} = 0 \\ T_{2} = 1 \\ T_{n + 1} = T_{n} + T_{n - 1} + T_{n - 2} \end{cases}$

これはこんな感じの数列になります
$\begin{array}{r} 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591, 29249425, 53798080, 98950096, 181997601, 334745777, 615693474, 1132436852, \dots \end{array}$

このトリボナッチ数列にも同じように加法定理はあるのでしょうか？
ありそう。

発想

さっきと同じようにしてみます。

$\begin{array}{r} T_{n + k} = a_{1} (k) T_{n} + a_{2} (k) T_{n - 1} + a_{3} (k) T_{n - 2} \end{array}$

こう表されるとします。
すると、 $T_{n + k + 1}$ が $2$ 通りの方法で表されます。
$\begin{array}{rcl} T_{n + k + 1} & = & a_{1} (k + 1) T_{n} + a_{2} (k + 1) T_{n - 1} + a_{3} (k + 1) T_{n - 2} \\ T_{n + k + 1} & = & T_{n + k} + T_{n + k - 1} + T_{n + k - 2} \end{array}$
$\begin{array}{rclrclr} = & a_{1} (k) T_{n} + & a_{2} (k) T_{n - 1} + & a_{3} (k) T_{n - 2} \\ + & a_{1} (k - 1) T_{n} + & a_{2} (k - 1) T_{n - 1} + & a_{3} (k - 1) T_{n - 2} \\ + & a_{1} (k - 2) T_{n} + & a_{2} (k - 2) T_{n - 1} + & a_{3} (k - 2) T_{n - 2} \end{array}$
$\begin{array}{rcl} = & (a_{1} (k) + a_{1} (k - 1) + a_{1} (k - 2)) T_{n} \\ + (a_{2} (k) + a_{2} (k - 1) + a_{2} (k - 2)) T_{n - 1} \\ + (a_{3} (k) + a_{3} (k - 1) + a_{3} (k - 2)) T_{n - 2} \end{array}$

(できるだけわかりやすく書いたつもり)

これらが同じなので、 $T_{n}, T_{n - 1}, T_{n - 2}$ の係数を比較してあげると、

$\begin{array}{rcl} a_{1} (k + 1) & = & a_{1} (k) + a_{1} (k - 1) + a_{1} (k - 2) \\ a_{2} (k + 1) & = & a_{2} (k) + a_{2} (k - 1) + a_{2} (k - 2) \\ a_{3} (k + 1) & = & a_{3} (k) + a_{3} (k - 1) + a_{3} (k - 2) \end{array}$

となりました
きれい

こうなってくると初期値が重要ですよね
さっきは $F_{n + 0}, F_{n + 1}$ で考えたので、 $T_{n + 0}, T_{n + 1}, T_{n + 2}$ でやろうかな
と思っていたのですが、
$T_{n - 0}, T_{n - 1}, T_{n - 2}$ でやったほうが簡単だということに気づきました

$\begin{array}{rcl} T_{n - 0} & = & 1 T_{n} + 0 T_{n - 1} + 0 T_{n - 2} \\ T_{n - 1} & = & 0 T_{n} + 1 T_{n - 1} + 0 T_{n - 2} \\ T_{n - 2} & = & 0 T_{n} + 0 T_{n - 1} + 1 T_{n - 2} \end{array}$

たしかに簡単になった
$\begin{array}{rclrcl} a_{1} (0) & = & 1, & a_{2} (0) = 0 & , a_{3} (0) = 0 \\ a_{1} (- 1) & = & 0, & a_{2} (- 1) = 1 & , a_{3} (- 1) = 0 \\ a_{1} (- 2) & = & 0, & a_{2} (- 2) = 0 & , a_{3} (- 2) = 1 \end{array}$

なんかこう、図にしたい気分ですね
$a_{1} (0)$ とか書くとややこしいので、 $T_{n}, T_{n - 1}, T_{n - 2}$ の係数だけ書きます。
それがこう。

	$T_{n}$	$T_{n - 1}$	$T_{n - 2}$
$T_{n - 2}$	$0$	$0$	$1$
$T_{n - 1}$	$0$	$1$	$0$
$T_{n}$	$1$	$0$	$0$
$T_{n + 1}$	$1$	$1$	$1$
$T_{n + 2}$	$2$	$2$	$1$
$T_{n + 3}$	$4$	$3$	$2$
$T_{n + 4}$	$7$	$6$	$4$
$T_{n + 5}$	$13$	$11$	$7$
$T_{n + 6}$	$24$	$20$	$13$

htmlで書くのは大変ですね。(Mathlogの表のしましまデザインが気になった)
例えば、 $T_{n + 5} = 13 T_{n} + 11 T_{n - 1} + 7 T_{n - 2}$ を表しています。

この表を作るのは単純で、
$\begin{array}{r} T_{n + k + 1} = T_{n + k} + T_{n + k - 1} + T_{n + k - 2} \end{array}$
なので $T_{n + k + 1}$ の行を作りたかったら $T_{n + k}$ の行と $T_{n + k - 1}$ の行と $T_{n + k - 2}$ の行を縦に足せばいいんですね。
例えば $T_{n + 5}$ なら $T_{n + 4}$ と $T_{n + 3}$ と $T_{n + 2}$ 　つまり上の3行を縦に足せばよくて、
$\begin{array}{rcl} 2 + 4 + 7 & = & 13 \\ 2 + 3 + 6 & = & 11 \\ 1 + 2 + 4 & = & 7 \end{array}$
という感じです。
ここで気づいたことがあります。

気づいたこと

1つめ

一番右の列、 $T_{n - 2}$ がトリボナッチ数列じゃないですか？
最初こそ $1$ ですが、それさえ無視すれば $0, 0, 1, 1, 2, 4, 7, 13, \dots$ と、
確かにトリボナッチ数列になっています。

これはなぜかというと、 $T_{n - 1}, T_{n}, T_{n + 1}$ の行のときの $T_{n - 2}$ の列が

	$T_{n - 2}$
$T_{n - 1}$	$0$
$T_{n}$	$0$
$T_{n + 1}$	$1$

という風になっているからです。これはトリボナッチ数列の初期値

\begin{array}{r} T_{0} = 0, T_{1} = 0, T_{2} = 1 \end{array}

と完全に一致しています。
次の行も上の三つの値の和なので、完全にトリボナッチ数列と同じ構成方法になっているんですね。

$k$ との対応を考えると $T_{k + 1}$ になります。

	$T_{n - 2}$
$T_{n - 1}$	$0$
$T_{n}$	$0$
$T_{n + 1}$	$1$
$T_{n + 2}$	$1$
$T_{n + 3}$	$2$
$⋮$	$⋮$
$T_{n + k}$	$T_{k + 1}$

2つ目

気づいたことはもう一つあって、
よく見るとこういう関係があります。

	$T_{n}$	$T_{n - 1}$	$T_{n - 2}$
$T_{n - 2}$	$0$	$0$	$1$
$T_{n - 1}$	$0$	$1$	$0$
$T_{n}$	$1$	$0$	$0$
$T_{n + 1}$	$1$	$1$	$1$
$T_{n + 2}$	$2$	$2$	$1$
$T_{n + 3}$	$4$	$3$	$2$
$T_{n + 4}$	$7$	$6$	$4$
$T_{n + 5}$	$13$	$11$	$7$
$T_{n + 6}$	$24$	$20$	$13$

$T_{n - 2}$ の列の水色のところを足すと $T_{n - 1}$ の列の水色のところになり、
$T_{n - 2}$ の列の緑色のところを足すと $T_{n}$ の列の緑色のところになるんですよね。
これは他の場所でも成り立ちます。

	$T_{n}$	$T_{n - 1}$	$T_{n - 2}$
$T_{n - 2}$	$0$	$0$	$1$
$T_{n - 1}$	$0$	$1$	$0$
$T_{n}$	$1$	$0$	$0$
$T_{n + 1}$	$1$	$1$	$1$
$T_{n + 2}$	$2$	$2$	$1$
$T_{n + 3}$	$4$	$3$	$2$
$T_{n + 4}$	$7$	$6$	$4$
$T_{n + 5}$	$13$	$11$	$7$
$T_{n + 6}$	$24$	$20$	$13$

ほら。

証明

一つ目( $T_{n - 1}$ )

これはどうやったら証明できるのでしょうか？
真ん中の列について考えてみましょう

	$T_{n - 1}$
$T_{n - 2}$	$0$
$T_{n - 1}$	$1$
$T_{n}$	$0$
$T_{n + 1}$	$1$
$T_{n + 2}$	$2$
$T_{n + 3}$	$3$
$T_{n + 4}$	$6$
$T_{n + 5}$	$11$
$T_{n + 6}$	$20$

横に並べますか？
$\begin{array}{r} 0, 1, 0, 1, 2, 3, 6, 11, 20 \end{array}$

これは

$\begin{array}{r} - - - - 0 1 0 1 2 3 6 - - - - \end{array}$

こんな感じで前 $3$ つを足していってますね。
これを、
こうするとどうでしょう

$\begin{array}{r} 0 1 0 0 - - 1 \end{array}$

最初に足したやつをそのまま横に書くのではなく、一つ下の行に書きます。
横に書くのは $0$ にします。

そして、
$\begin{array}{r} - - 0 1 0 0 1 1 1 - - \end{array}$

両方の行で前 $3$ つを足して横に書きます。

もう一度。

$\begin{array}{r} - - 0 1 0 0 1 1 1 1 2 - - \end{array}$

もう一度。

$\begin{array}{r} - - 0 1 0 0 1 1 2 1 1 2 4 - - \end{array}$

もう一度。

$\begin{array}{r} - - 0 1 0 0 1 1 2 4 1 1 2 4 7 - - \end{array}$

もう一度。

$\begin{array}{r} - - 0 1 0 0 1 1 2 4 7 1 1 2 4 7 13 - - \end{array}$

気づきましたか？

これを縦に足すとさっきの数列になります。

$\begin{array}{rclrclrclrclrclrcl} 0 & 1 & 0 & 0 & 1 & 1 & 2 & 4 & 7 \\ + & 1 & 1 & 2 & 4 & 7 & 13 \end{array}$
$\begin{array}{rclrclrclrclrclrcl} 0 & 1 & 0 & 1 & 2 & 3 & 6 & 11 & 20 \end{array}$

まぁそりゃそうですよね。

さっきのをこう見ると分かります。
$\begin{array}{r} 0 1 0 0 - - + 1 \\ 0 1 0 1 - - \end{array}$

そして、

$\begin{array}{r} - - 0 1 0 0 1 1 1 + - - \\ 0 1 0 1 2 - - \end{array}$

もう一度。

$\begin{array}{r} - - 0 1 0 0 1 1 1 1 2 + - - \\ 0 1 0 1 2 3 - - \end{array}$

もう一度。

$\begin{array}{r} - - 0 1 0 0 1 1 2 1 1 2 4 + - - \\ 0 1 0 1 2 3 6 - - \end{array}$

もう一度。

$\begin{array}{r} - - 0 1 0 0 1 1 2 4 1 1 2 4 7 + - - \\ 0 1 0 1 2 3 6 11 - - \end{array}$

もう一度。

$\begin{array}{r} - - 0 1 0 0 1 1 2 4 7 1 1 2 4 7 13 + - - \\ 0 1 0 1 2 3 6 11 20 - - \end{array}$

「そりゃそうだな」　ってなりましたか？
そして、この分けた数列はトリボナッチ数列そのものになっています。

なぜなら、 $0 0 1$ となる部分があり、この後ずっと
前 $3$ つを足して横に書く
という操作をし続けるので、これはトリボナッチ数列の構成の仕方そのものになっているからです。

実際の項数を考えると

$\begin{array}{r} T_{0} T_{1} T_{2} T_{3} T_{4} T_{5} T_{6} \dots T_{k} 0 1 0 0 1 1 2 4 7 1 1 2 4 7 13 + T_{2} T_{3} T_{4} T_{5} T_{6} T_{7} \dots T_{k + 1} \\ 01012361120 T_{n - 2} T_{n - 1} T_{n} T_{n + 1} T_{n + 2} T_{n + 3} T_{n + 4} T_{n + 5} T_{n + 6} \dots T_{n + k} \end{array}$

よって真ん中の数列は $T_{k} + T_{k + 1}$ であることが分かりました

$\begin{array}{r} a_{2} (k) = T_{k} + T_{k + 1} \end{array}$

(書くのしんどい...)

証明2( $T_{n}$ )

もう一つの方も同じように証明できます
(これは証明なのか???)

	$T_{n}$	$T_{n - 1}$	$T_{n - 2}$
$T_{n - 2}$	$0$	$0$	$1$
$T_{n - 1}$	$0$	$1$	$0$
$T_{n}$	$1$	$0$	$0$
$T_{n + 1}$	$1$	$1$	$1$
$T_{n + 2}$	$2$	$2$	$1$
$T_{n + 3}$	$4$	$3$	$2$
$T_{n + 4}$	$7$	$6$	$4$
$T_{n + 5}$	$13$	$11$	$7$
$T_{n + 6}$	$24$	$20$	$13$

これの緑のところね。

水色はさっきやりました。

さっきと同じようにやりたいだけです。

$\begin{array}{r} 0 0 1 0 - - + 1 \\ 0 0 1 1 - - \end{array}$

ただ、もう一つ下の $3$ 行目に書いておきます。
そして、

$\begin{array}{r} 0 0 1 0 0 - - 1 1 1 - - \\ 0 0 1 1 2 - - \end{array}$

ということもしておきます。

よく見てください。両方の行で前 $3$ つを足しているだけです。

ただし $1$ 行目はそのまま横に書くのではなく、下の $2$ 行目に書いています。

$3$ 行目はそのまま横に書いています。

気づいた人もいるかもしれませんが、上の $2$ つの行はさっき証明したやつと全く同じ形をしています。

無視してどんどん行きましょう。

$\begin{array}{r} - - 0 0 1 0 0 1 1 1 - - 1 1 2 + - - \\ 0 0 1 1 2 4 - - \end{array}$

もう一度。

$\begin{array}{r} - - 0 0 1 0 0 1 1 1 1 2 - - 1 1 2 4 + - - \\ 0 0 1 1 2 4 7 - - \end{array}$

もう一度。

$\begin{array}{r} - - 0 0 1 0 0 1 1 2 1 1 2 4 - - 1 1 2 4 7 + - - \\ 0 0 1 1 2 4 7 13 - - \end{array}$

もう一度。

$\begin{array}{r} - - 0 0 1 0 0 1 1 2 4 1 1 2 4 7 - - 1 1 2 4 7 13 + - - \\ 0 0 1 1 2 4 7 13 24 - - \end{array}$

ということで、

$\begin{array}{r} T_{0} T_{1} T_{2} T_{3} T_{4} T_{5} \dots T_{k - 1} 0 0 1 0 0 1 1 2 4 T_{2} T_{3} T_{4} T_{5} T_{6} \dots T_{k} 1 1 2 4 7 T_{2} T_{3} T_{4} T_{5} T_{6} T_{7} \dots T_{k + 1} 1 1 2 4 7 13 \\ 00112471324 T_{n - 2} T_{n - 1} T_{n} T_{n + 1} T_{n + 2} T_{n + 3} T_{n + 4} T_{n + 5} T_{n + 6} \dots T_{n + k} \end{array}$

となり、一番左の列は $T_{k - 1} + T_{k} + T_{k + 1}$ だと分かりました。

$\begin{array}{r} a_{1} (k) = T_{k - 1} + T_{k} + T_{k + 1} \end{array}$

(知ってた)

結論

最終的に、表はこうなります。

	$T_{n}$	$T_{n - 1}$	$T_{n - 2}$
$T_{n - 2}$	$0$	$0$	$1$
$T_{n - 1}$	$0$	$1$	$0$
$T_{n}$	$1$	$0$	$0$
$T_{n + 1}$	$1$	$1$	$1$
$T_{n + 2}$	$2$	$2$	$1$
$T_{n + 3}$	$4$	$3$	$2$
$T_{n + 4}$	$7$	$6$	$4$
$T_{n + 5}$	$13$	$11$	$7$
$T_{n + 6}$	$24$	$20$	$13$
$T_{n + k}$	$T_{k - 1} + T_{k} + T_{k + 1}$	$T_{k} + T_{k + 1}$	$T_{k + 1}$

ということで、

トリボナッチ数列の加法定理

$\begin{array}{rcl} T_{n + k} & = & (T_{k - 1} + T_{k} + T_{k + 1}) T_{n} + (T_{k} + T_{k + 1}) T_{n - 1} + T_{k + 1} T_{n - 2} \end{array}$

が証明できました。

$k$ -ナッチ数列

$k$ -ナッチ数列というものがあります。

${\begin{cases} W_{i} = 0 (0 \leq i \leq k - 2) \\ W_{k - 1} = 1 \\ W_{n + 1} = W_{n} + W_{n - 1} + W_{n - 2} + \dots + W_{n - k + 1} \\ = \overset{k}{\sum_{i = 1}} W_{n - i + 1} \end{cases}$

まあ要は $k$ 個前まで足したやつを次の項にするというだけの、
フィボナッチ数列やトリボナッチ数列の拡張です。

この $k$ -ナッチ数列にも加法定理はあるのでしょうか。

あります。(唐突な断言)

まぁさっきと全く同じことをすればいいです。

さすがに表やグラフは書きませんよ?

発想

発想もクソもないです。さっきと全く同じようにしてみます。

$\begin{array}{rcl} W_{n + m} & = & a_{1} (m) W_{n} + a_{2} (m) W_{n - 1} + a_{3} (m) W_{n - 2} + \dots + a_{k} (m) W_{n - k + 1} \\ = & \sum_{i = 1}^{k} a_{i} (m) W_{n - i + 1} \end{array}$

こう表されるとします。

すると、 $W_{n + m + 1}$ が $2$ 通りの方法で表されます。

$\begin{array}{rcl} W_{n + m + 1} & = & a_{1} (m + 1) W_{n} + a_{2} (m + 1) W_{n - 1} + a_{3} (m + 1) W_{n - 2} + \dots + a_{k} (m + 1) W_{n - k + 1} \\ W_{n + m + 1} & = & W_{n + m} + W_{n + m - 1} + W_{n + m - 2} + \dots + W_{n + m - k + 1} \end{array}$
$\begin{array}{rclrclrc} = & a_{1} (m) W_{n} + & a_{2} (m) W_{n - 1} + & a_{3} (m) W_{n - 2} + & \dots + & a_{k} (m) W_{n - k + 1} \\ + & a_{1} (m - 1) W_{n} + & a_{2} (m - 1) W_{n - 1} + & a_{3} (m - 1) W_{n - 2} + & \dots + & a_{k} (m - 1) W_{n - k + 1} \\ + & a_{1} (m - 2) W_{n} + & a_{2} (m - 2) W_{n - 1} + & a_{3} (m - 2) W_{n - 2} + & \dots + & a_{k} (m - 2) W_{n - k + 1} \\ + & a_{1} (m - 3) W_{n} + & a_{2} (m - 3) W_{n - 1} + & a_{3} (m - 3) W_{n - 2} + & \dots + & a_{k} (m - 3) W_{n - k + 1} \\ ⋮ \\ + & a_{1} (m - k + 1) W_{n} + & a_{2} (m - k + 1) W_{n - 1} + & a_{3} (m - k + 1) W_{n - 2} + & \dots + & a_{k} (m - k + 1) W_{n - k + 1} \end{array}$
$\begin{array}{rcl} = & (a_{1} (m) + a_{1} (m - 1) + a_{1} (m - 2) + \dots + a_{1} (m - k + 1)) W_{n} \\ + (a_{2} (m) + a_{2} (m - 1) + a_{2} (m - 2) + \dots + a_{2} (m - k + 1)) W_{n - 1} \\ + (a_{3} (m) + a_{3} (m - 1) + a_{3} (m - 2) + \dots + a_{3} (m - k + 1)) W_{n - 2} \\ ⋮ \\ + (a_{k} (m) + a_{k} (m - 1) + a_{k} (m - 2) + \dots + a_{k} (m - k + 1)) W_{n - k + 1} \end{array}$

(できるだけわかりやすく書いたつもり(無理がある))

こういう時のためにシグマがあるんじゃないですか

$\begin{array}{rcl} W_{n + m + 1} & = & \sum_{i = 1}^{k} a_{i} (m + 1) W_{n - i + 1} \\ W_{n + m + 1} & = & \sum_{j = 1}^{k} W_{n + m - j + 1} \\ = & \sum_{j = 1}^{k} \sum_{i = 1}^{k} a_{i} (m - j + 1) W_{n - i + 1} \\ = & \sum_{i = 1}^{k} \sum_{j = 1}^{k} a_{i} (m - j + 1) W_{n - i + 1} \\ = & \sum_{i = 1}^{k} W_{n - i + 1} \sum_{j = 1}^{k} a_{i} (m - j + 1) \end{array}$

これらが同じなので、 $W_{n - i + 1}$ の係数を比較してあげると、

$\begin{array}{r} a_{i} (m + 1) = \sum_{j = 1}^{k} a_{i} (m - j + 1) (1 \leq i \leq k) \end{array}$

となりました

しんぷる

というかこれは $k$ -ナッチ数列の定義と全く同じ構造をしています。
$\begin{array}{rcl} W_{n + 1} & = & \sum_{i = 1}^{k} W_{n - i + 1} \\ a_{i} (m + 1) & = & \sum_{j = 1}^{k} a_{i} (m - j + 1) \end{array}$

初期値が重要なんでした

$\begin{array}{rcl} W_{n - i} & = & 0 W_{n} + 0 W_{n - 1} + 0 W_{n - 2} + \dots + 0 W_{n - i - 1} + 1 W_{n - i} + 0 W_{n - i + 1} + \dots + 0 W_{n - k + 1} \\ ∴ a_{i + 1} (- i) & = & 1 (0 \leq i \leq k - 1) \\ a_{j + 1} (- i) & = & 0 (i \neq j, 0 \leq i \leq k - 1, 0 \leq j \leq k - 1) \end{array}$

となります。

トリボナッチ数列から学んだこと

まとめて書くのは便利ですが、やはり具体性がなくなりますね。

先ほどのトリボナッチ数列の結果から、このような予想が立ちます。

1つめ

$\begin{array}{rcl} a_{k} (m) & = & W_{k + m - 2} \end{array}$

これは一番右の列( $a_{k} (m)$ )がそのまま元の数列と同じものだという、
気づいたこと $1$ に対応するものです

2つめ

$\begin{array}{rcl} a_{k - i} (m) & = & \sum_{t = 0}^{i} a_{k} (m - t) (0 \leq i \leq k - 1) \end{array}$

これは気づいたこと2に対応するものです。表のやつ。

証明

証明とは。

1つめ

1つ目は余裕ですね。

$a_{k} ()$ の情報は

$\begin{array}{r} a_{i} (m + 1) = \sum_{j = 1}^{k} a_{i} (m - j + 1) (1 \leq i \leq k) \end{array}$
から、 $i = k$ としたらいいですね。
$\begin{array}{r} a_{k} (m + 1) = \sum_{j = 1}^{k} a_{k} (m - j + 1) \end{array}$

これは、 $k$ -ナッチ数列と同じ構造をしているのでした。(さっき言った)

初期値が重要なんです(さっき言った)

$\begin{array}{rcl} a_{i + 1} (- i) & = & 1 (0 \leq i \leq k - 1) \\ a_{j + 1} (- i) & = & 0 (i \neq j, 0 \leq i \leq k - 1, 0 \leq j \leq k - 1) \end{array}$

なので、

$\begin{array}{rcl} a_{k} (1 - k) & = & 1 \end{array}$
$\begin{array}{rclrc} a_{k} (- i) & = & 0 & (i \neq k - 1, 0 \leq i \leq k - 1) \\ \to a_{k} (- i) & = & 0 & (0 \leq i \leq k - 2) \\ \to a_{k} (i) & = & 0 & (2 - k \leq i \leq 0) \end{array}$

と分かります。

ここで、

$\begin{array}{r} a_{k} (m + 1) = \sum_{j = 1}^{k} a_{k} (m - j + 1) \end{array}$

さっきのこの式に $m = 0$ をぶち込みます
すると、

$\begin{array}{rcl} a_{k} (1) & = & \sum_{j = 1}^{k} a_{k} (1 - j) \\ = & a_{k} (0) + a_{k} (- 1) + a_{k} (- 2) + \dots + a_{k} (2 - k) + a_{k} (1 - k) \\ = & 0 + 0 + 0 + \dots + 0 + 1 \\ = & 1 \end{array}$

となりました。

ここで $k$ -ナッチ数列の定義を見てみましょう

${\begin{cases} W_{i} = 0 (0 \leq i \leq k - 2) \\ W_{k - 1} = 1 \\ W_{n + 1} = \overset{k}{\sum_{i = 1}} W_{n - i + 1} \end{cases}$

この式を改めて、 $W_{n} = X_{n - k + 2}$ に変えてみましょう

${\begin{cases} X_{i - k + 2} = 0 (0 \leq i \leq k - 2) \\ X_{k - 1 - k + 2} = 1 \\ X_{n + 1 - k + 2} = \overset{k}{\sum_{i = 1}} X_{n - i + 1 - k + 2} \end{cases}$

$(0 \leq i \leq k - 2)$ は $(2 - k \leq i - k + 2 \leq 0)$ と変形できるので、

${\begin{cases} X_{i} = 0 (2 - k \leq i \leq 0) \\ X_{1} = 1 \\ X_{n - k + 3} = \overset{k}{\sum_{i = 1}} X_{n - i - k + 3} \end{cases}$

あと $n - k$ は $m - 2$ に変えておきます

${\begin{cases} X_{i} = 0 (2 - k \leq i \leq 0) \\ X_{1} = 1 \\ X_{m + 1} = \overset{k}{\sum_{i = 1}} X_{m - i + 1} \end{cases}$

はい。これでさっきの $a_{k} ()$ と同じものになりました

$\begin{array}{rcl} a_{k} (i) = 0 (2 - k \leq i \leq 0) \\ a_{k} (1) = 1 \\ a_{k} (m + 1) = \sum_{j = 1}^{k} a_{k} (m - j + 1) \end{array}$

よって $a_{k} (m) = X_{m} = W_{m + k - 2}$ というのが証明できました。

$\begin{array}{r} a_{k} (m) = X_{m} = W_{m + k - 2} \end{array}$

2つめ

これも式をいじって証明したい。

トリボナッチ数列では、最初の足し算を一つ下の行に　分けて　書いて足していましたね。
最初の足し算を分けることで分けたやつそれぞれがトリボナッチ数列に対応していました。

なので分ける方針を考えます

ベクトルか
数が並んでいればなんでもいいのですがね。

まず初期値から

特定の定数 $p$ で考えてみます。( $0 \leq p \leq k - 1$ ) 素数じゃないよ

$\begin{array}{rcl} a_{i + 1} (- i) & = & 1 (0 \leq i \leq k - 1) \\ a_{j + 1} (- i) & = & 0 (i \neq j, 0 \leq i \leq k - 1, 0 \leq j \leq k - 1) \end{array}$

2つあるうちの上のやつで $i$ を $k - p - 1$ にすると

$\begin{array}{rcl} a_{k - p} (1 + p - k) & = & 1 \end{array}$

下のやつでは $j$ を $k - p - 1$ にすると、

$\begin{array}{rcl} a_{k - p} (- i) & = & 0 (i \neq k - p - 1, 0 \leq i \leq k - 1) \\ \to a_{k - p} (i) & = & 0 (i \neq 1 + p - k, 1 - k \leq i \leq 0) \end{array}$

となります。

次はこれ

$\begin{array}{rcl} a_{i} (m + 1) & = & \sum_{j = 1}^{k} a_{i} (m - j + 1) (1 \leq i \leq k) \end{array}$

の $i$ へ $k - p$ を代入します

$\begin{array}{rcl} a_{k - p} (m + 1) & = & \sum_{j = 1}^{k} a_{k - p} (m - j + 1) \\ = & a_{k - p} (m) + a_{k - p} (m - 1) + a_{k - p} (m - 2) + \dots + a_{k - p} (m - k + 2) + a_{k - p} (m - k + 1) \end{array}$

戦略

逆に言えば $a_{k} (m) = W_{m + k - 2}$ というのをさっき証明したので、

$\begin{array}{rcl} a_{k - p} (m) & = & \sum_{t = 0}^{p} a_{k} (m - t) \end{array}$

じゃなくてもう直接

$\begin{array}{rcl} a_{k - p} (m) & = & \sum_{t = 0}^{p} W_{m - t + k - 2} \end{array}$

を示したらいいんじゃないですかね？

初期値に注意して計算すれば示せるはずです。
$\begin{array}{r} a_{k - p} (- k + 1) a_{k - p} (- k + 2) a_{k - p} (- k + 3) \dots a_{k - p} (- k + p + 1) \dots a_{k - p} (1) a_{k - p} (0) 000 \underset{(ここだけ)}{1} 00 \end{array}$

こういう感じです。
$a_{k - p} (1)$ は $- k + 1 \sim 0$ で、上に書いたやつらの和なので $1$ になります。

$a_{k - p} (2)$ は $- k + 2 \sim 1$ までの和です。つまり
$a_{k - p} (1)$ と $a_{k - p} (- k + p + 1)$ の $1$ の和なので、
$\begin{array}{rcl} a_{k - p} (2) & = & a_{k - p} (1) + 1 \end{array}$
です。

$a_{k - p} (3)$ は $- k + 3 \sim 2$ までの和で、
$a_{k - p} (1), a_{k - p} (2)$ と、 $a_{k - p} (- k + p + 1)$ の $1$ の和なので、
$\begin{array}{rcl} a_{k - p} (3) & = & a_{k - p} (2) + a_{k - p} (1) + 1 \end{array}$

このままずっとこうなりますね。
一般に、 $a_{k - p} (i)$ は $- k + i \sim i - 1$ までの和で、
$a_{k - p} (1), a_{k - p} (2), \dots, a_{k - p} (i - 1)$ までの和と、 $a_{k - p} (- k + p + 1)$ の $1$ の和なので
$\begin{array}{rcl} a_{k - p} (i) & = & a_{k - p} (1) + a_{k - p} (2) + \dots + a_{k - p} (i - 1) + 1 \end{array}$
となります。

どこまで続くかというと、 $a_{k - p} (p + 1)$ です。

$a_{k - p} (p + 1)$ は $- k + p + 1 \sim p$ までの和で、

$a_{k - p} (1), a_{k - p} (2), \dots, a_{k - p} (p)$ の和と、 $a_{k - p} (- k + p + 1)$ の $1$ の和です。
ギリギリ入ります
$\begin{array}{rcl} a_{k - p} (p + 1) & = & a_{k - p} (1) + a_{k - p} (2) + \dots + a_{k - p} (p) + 1 \\ = & 1 + \sum_{i = 1}^{p} a_{k - p} (i) \end{array}$

なのでさっきのは $1 \leq i \leq p + 1$ として

$\begin{array}{rcl} a_{k - p} (i) & = & a_{k - p} (1) + a_{k - p} (2) + \dots + a_{k - p} (i - 1) + 1 \end{array}$

となります。

ここまでを見て、これが $\overset{p}{\sum_{t = 0}} W_{i - t + k - 2}$ と等しいと言えないでしょうか？

示したい等式の右辺から左辺を導きたい。
$\begin{array}{rcl} a_{k - p} (m) & = & \sum_{t = 0}^{p} W_{m - t + k - 2} \end{array}$

右辺に $m = 1$ を入れると、

$\begin{array}{r} W_{k - 1} + W_{k - 2} + W_{k - 3} + \dots + W_{k - p - 1} \end{array}$

これは $W_{k - 1}$ だけ $1$ で、他は $0$ なので
$1$ となって $a_{k - p} (1)$ と等しいです。
( $W_{0} \sim W_{k - 2}$ は全部 $0$ という定義)

ここで言いたいことがあって、
$W_{k - p - 1}$ の後、 $W_{k - p - 2}, W_{k - p - 3}, W_{k - p - 4}, \dots, W_{0}$ までも全て $0$ なんですから、

$\begin{array}{rcl} W_{k - 1} + W_{k - 2} + W_{k - 3} + \dots + W_{k - p - 1} \\ = & W_{k - 1} + W_{k - 2} + W_{k - 3} + \dots + W_{k - p - 1} + W_{k - p - 2} + \dots + W_{0} \\ = & W_{k} \end{array}$
と言えます。

よって、
$\begin{array}{r} a_{k - p} (1) = W_{k} \end{array}$
と言えます。

$m = 2$ を入れると、

$\begin{array}{rcl} W_{k} + W_{k - 1} + W_{k - 2} + W_{k - 3} + \dots + W_{k - p} \\ = & a_{k - p} (1) + W_{k - 1} + W_{k - 2} + W_{k - 3} + \dots + W_{k - p} \end{array}$

ここで、先ほども言いましたが $W_{k - 1}$ だけが $1$ で、他は $0$ なので
$\begin{array}{r} a_{k - p} (1) + 1 \end{array}$
となり、これは $a_{k - p} (2)$ と等しいです。

また言いたいことなのですが、 $W_{k - p}$ の後、 $W_{k - p - 1}, W_{k - p - 2}, \dots, W_{0}$ はやっぱり $0$ なので、

$\begin{array}{rcl} W_{k} + W_{k - 1} + W_{k - 2} + W_{k - 3} + \dots + W_{k - p} \\ = & W_{k} + W_{k - 1} + W_{k - 2} + W_{k - 3} + \dots + W_{k - p} + W_{k - p - 1} + W_{k - p - 2} + \dots + W_{1} \\ = & W_{k + 1} \end{array}$

よって、
$a_{k - p} (2) = W_{k + 1}$ と言えます。

もう一つ行きましょう。 $m = 3$ を入れます。
$\begin{array}{rcl} W_{k + 1} + W_{k} + W_{k - 1} + W_{k - 2} + \dots + W_{k - p + 1} \\ = & a_{k - p} (2) + a_{k - p} (1) + W_{k - 1} + W_{k - 2} + W_{k - 3} + \dots + W_{k - p + 1} \end{array}$

また言いますが、 $W_{k - 1}$ だけが $1$ で、他は $0$ なので
$\begin{array}{r} a_{k - p} (2) + a_{k - p} (1) + 1 \end{array}$
となり、これは $a_{k - p} (3)$ と等しいです。

またまた言いたいことなのですが、 $W_{k - p + 1}$ の後、 $W_{k - p}, W_{k - p - 1}, W_{k - p - 2}, \dots, W_{0}$ はやっぱり $0$ なので、

$\begin{array}{rcl} W_{k + 1} + W_{k} + W_{k - 1} + W_{k - 2} + W_{k - 3} + \dots + W_{k - p + 1} \\ = & W_{k + 1} + W_{k} + W_{k - 1} + W_{k - 2} + W_{k - 3} + \dots + W_{k - p + 1} + W_{k - p} + W_{k - p - 1} + \dots + W_{2} \\ = & W_{k + 2} \end{array}$

よって、
$a_{k - p} (3) = W_{k + 2}$ と言えます。

はい一般化～
仮定として( $2 \leq i \leq p + 1$ )

$a_{k - p} (1) = W_{k}, a_{k - p} (2) = W_{k + 1}, a_{k - p} (3) = W_{k + 2}, \dots, a_{k - p} (i - 1) = W_{k + i - 2}$

が成り立っているとします。

$m = i$ を代入すると

$\begin{array}{rcl} W_{k + i - 2} + W_{k + i - 3} + W_{k + i - 4} + \dots + W_{k - p + i - 2} \\ = & a_{k - p} (i - 1) + a_{k - p} (i - 2) + a_{k - p} (i - 3) + \dots + a_{k - p} (1) + W_{k - 1} + \dots + W_{k - p + i - 2} \end{array}$

となって、 $W_{k - 1} = 1$ かつ、 $W_{k - 2} \sim W_{0}$ までは $0$ なので、

$\begin{array}{rcl} = & a_{k - p} (i - 1) + a_{k - p} (i - 2) + a_{k - p} (i - 3) + \dots + a_{k - p} (1) + 1 \end{array}$
となり、これは $a_{k - p} (i)$ に等しいです。

また、 $W_{k - p + i - 2}$ の後、 $W_{k - p + i - 3}, W_{k - p + i - 4}, \dots, W_{0}$ までも $0$ なので、

$\begin{array}{rcl} W_{k + i - 2} + W_{k + i - 3} + W_{k + i - 4} + \dots + W_{k - p + i - 2} \\ = & W_{k + i - 2} + W_{k + i - 3} + W_{k + i - 4} + \dots + W_{k - p + i - 2} + W_{k - p + i - 3} + \dots + W_{i - 1} \\ = & W_{k + i - 1} \end{array}$

と言えるので、

$\begin{array}{rcl} a_{k - p} (i) & = & W_{k + i - 1} \end{array}$
と言えます。

よっしゃぁ

あとは累積帰納法によって、すべての $2 \leq i \leq p + 1$ に対して

$\begin{array}{rcl} a_{k - p} (i) & = & W_{k + i - 2} + W_{k + i - 3} + W_{k + i - 4} + \dots + W_{k - p + i - 2} \end{array}$

と分かりました。

( $0 \leq p \leq k - 1$ )なので、予想はあってたということです。

$\begin{array}{rcl} a_{k - i} (m) & = & \sum_{t = 0}^{i} W_{k + m - t - 2} \\ = & \sum_{t = 0}^{i} a_{k} (m - t) (0 \leq i \leq k - 1) \end{array}$

これで、全貌がつかめました。

まとめて

まとめると、

$\begin{array}{rcl} a_{k - i} (m) & = & \sum_{t = 0}^{i} W_{k + m - t - 2} \end{array}$

なので、 $i$ を $k - i$ に改めると、
$\begin{array}{rcl} a_{i} (m) & = & \sum_{t = 0}^{k - i} W_{k + m - t - 2} \end{array}$
$t$ が $0 \sim k - i$ なので、 $k - t$ は $k \sim i$ より、
$\begin{array}{rcl} a_{i} (m) & = & \sum_{t = i}^{k} W_{t + m - 2} \end{array}$

これを

$\begin{array}{rcl} W_{n + m} & = & \sum_{i = 1}^{k} a_{i} (m) W_{n - i + 1} \end{array}$

へぶち込めば！

k

-ナッチ数列の加法定理

$\begin{array}{rcl} W_{n + m} & = & \sum_{i = 1}^{k} W_{n - i + 1} \sum_{t = i}^{k} W_{t + m - 2} \end{array}$

となりました(えぐ)

おわり

おわりです。

投稿日：18日前

更新日：15日前

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

Y.K.

166

8079

掛け算が苦手

他の人のコメント

コメントはありません。

読み込み中

Y.K.

k-ナッチ数列の加法定理を求める

追記
フィボナッチ数列の加法定理
発想
トリボナッチ数列
発想
気づいたこと
証明
結論
$k$-ナッチ数列
発想
トリボナッチ数列から学んだこと
証明
まとめて
おわり

k-ナッチ数列の加法定理を求める

追記

フィボナッチ数列の加法定理

発想

トリボナッチ数列

発想

気づいたこと

1つめ

2つ目

証明

一つ目(Tn−1)

証明2(Tn)

結論

k-ナッチ数列

発想

トリボナッチ数列から学んだこと

1つめ

2つめ

証明

1つめ

2つめ

戦略

まとめて

おわり

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

一つ目( $T_{n - 1}$ )

証明2( $T_{n}$ )

$k$ -ナッチ数列