【数列】異なるk項の積の総和の考察1「異なる2項の積の総和を漸化式で一般化」

今回は、たまに大学入試でも出題される(有限)数列の「異なる2項の積の総和」の一般化を試みます。

以下の問題を考えます。

研究(異なるk項の積の総和)

$k$ を $1$ 以上の整数、 $n$ を $k$ 以上の整数とする。

$n$ 個の整数 $a_{1},a_{2},a_{3},\dots ,a_{n}$ から異なる $k$ 個の数選んで作る積の総和 $P_{n}(k)$ を求めたい。

【予備知識】

高校数学の数列の知識があれば十分です。

k=2のとき
k=3のとき
一般の場合は？
漸化式の活用1：解いてみる

k=2のとき

$k=2$ のときは以下のように考えられます。

$(a_{1}+a_{2}+a_{3})^2=a_{1}^2+a_{2}^2+a_{3}^2+2(a_{1}a_{2}+a_{2}a_{3}+a_{3}a_{1})$

この展開式から

$\displaystyle P_{3}(2)=\frac{1}{2}\left( \left(\sum_{i=1}^{3}a_{i}\right)^{2} -\sum_{i=1}^{3}a_{i}^{2}\right)$

を得ます。

$n=3$ の場合で考えましたが、一般の $n$ でも当然同様の展開式が成り立つことから

$\displaystyle P_{n}(2)=\frac{1}{2}\left( \left(\sum_{i=1}^{n}a_{i}\right)^{2} -\sum_{i=1}^{n}a_{i}^{2}\right)$

となり、 $k=2$ のときは解決です。

k=3のとき

やや複雑ですが、 $k=2$ のときと同様に"とりあえず3乗して余計なものを引き去る"という考え方をしてみましょう。

$\displaystyle (a_{1}+a_{2}+a_{3}\cdots +a_{n})^{3}=\sum_{i=1}^{n} a_{i}^{3}+3\sum_{i=1}^{n} \sum_{1\le j\le n , j\neq i}a_{i}^{2}a_{j}+6P_{n}(3)$

この式に加えて

$\displaystyle \sum_{i=1}^{n} \sum_{1\le j\le n , j\neq i}a_{i}^{2}a_{j}=\sum_{i=1}^{n}a_{i}^2\sum_{j=1}^{n}a_{j}-\sum_{i=1}^{n}a_{i}^3$

が成り立つことから

$\displaystyle P_{n}(3)=\frac{\displaystyle (\sum_{i=1}^{n} a_{i} )^{3}-3\sum_{i=1}^{n}a_{i}^{2}\sum_{i=1}^{n}a_{i}+2\sum_{i=1}^{n}a_{i}^{3} }{6}$

を得ます。

一般の場合は？

この調子で $k$ の値を上げていってもよいのですが、このままの考え方だと次第に膨大な計算を行わないといけないことが目に見えています。

とはいえ、 $P_{n}(k)$ を"閉じた式*1"で表すのはなかなか厳しそうです。

そこで、「漸化式」を作る作戦で行きます。

準備として $P_{n}(k)$ $(n\ge k)$ を拡張しておきます。

定義(異なるk項の積の総和の拡張)

(1)　 $k$ を $1$ 以上の整数、 $n$ を $k$ 以上の整数とする。 $n$ 個の整数 $a_{1},a_{2},a_{3},\dots ,a_{n}$ から異なる $k$ 個の数選んで作る積の総和を $P_{n}(k)$ とする。

(2)　任意の $0$ 以上の整数 $n$ について $P_{n}(0)=1$ とする。

(3)　 $0$ 以上の整数 $k$ , $n$ について $n\lt k$ のとき、 $P_{n}(k)=0$ とする。特に任意の正の整数 $k$ について $P_{0}(k)$ =0 となる。

$0!$ の定義と同様、今後の展開のために都合よく定義していますので、この定義に関しては深入りしません。

さていよいよ本題ですが、異なる $k$ 項の積の総和に関する漸化式を作っていこうと思います。

考え方の入り口はこんな感じです。

「順に並んだn+1個の数の中からk+1個を選んで積を考えていくとき、(1)最初のn個の中からk+1個を選んだ場合と(2)最初のn個からk個選んだうえで残り1個をn+1番目にする場合の2通りがある。」

"数列"っぽく記述してみましょう。

数列 $\{ a_{n} \}$ について、初項から第 $n$ 項までの $n$ 個の項 $a_{1},a_{2}, \dots , a_{n}$ に対して $P_{n}(k)$ を与えます。

$P_{n+1}(k+1)$ は $a_{1},a_{2}, \dots , a_{n}$ に $a_{n+1}$ を加えた $n+1$ 項で考えると以下のようになります。

(1)最初のn個の中からk+1個を選んだ場合の和は $P_{n}(k+1)$ と書けます。

( $n=k$ のときは定義(3)により $P_{n}(k+1)=0$ です。)

(2)最初のn個からk個選んだうえで残り1個をn+1番目にする場合の和は $P_{n}(k)a_{n+1}$ と書けます。

(定義(2)により $k=0$ のときも成立します。)

以上により、次の補題を得ます。

補題(異なるk項の積の総和の漸化式)

数列 $\{ a_{n} \}$ について、初項から第 $n$ 項までの $n$ 個の項 $a_{1},a_{2}, \dots , a_{n}$ に対して $P_{n}(k)$ を与える。このとき次の等式が成り立つ。

$P_{n+1}(k+1)=P_{n}(k+1)+P_{n}(k)a_{n+1}$

さらにこの等式は任意の $0$ 以上の整数 $n$ , $k$ で成り立つ。

このままでは"ありがたみ"はあまりなさそう…ですね。

そこでこの補題の2つの活用を見せたいと思います。

漸化式の活用1：解いてみる

解いてみ(ようとしてみ)ましょう。

補題を変形すると以下の形になります。

$P_{n+1}(k+1)-P_{n}(k+1)=P_{n}(k)a_{n+1}$

$k$ を固定した $n$ についての数列 $\{ P_{n}(k+1) \}$ を考えた場合、 $\{ P_{n}(k+1) \}$ の階差数列が $n$ についての数列 $\{ P_{n}(k)a_{n+1} \}$ と言い換えることが出来ます。

したがって $n\ge 1$ のとき

$\displaystyle P_{n}(k+1)=P_{0}(k+1)+\sum_{i=0}^{n-1} P_{i}(k)a_{i+1}$

$P_{0}(k+1)=0$ とΣの書き換えにより以下の定理を得ます。

定理(異なるk項の積の総和)

数列 $\{ a_{n} \}$ について、初項から第 $n$ 項までの $n$ 個の項 $a_{1},a_{2}, \dots , a_{n}$ について

$\displaystyle P_{n}(k+1)=\sum_{i=1}^{n} P_{i-1}(k)a_{i}$

が成り立つ。( $n$ は正の整数, $k$ は $0$ 以上の整数。)

(例)　 $a_{n}=n$ で表される数列 $\{ a_{n} \}$

math-topology.hatenablog.com

※以前のシリーズの内容を一部使います。証明等の詳細は上記の過去記事をご覧ください。

以下のような「下降冪」を導入します。

$n^{\underline{k}}=\left\{ \begin{array}{l} n(n-1)(n-2)\cdots (n-k+1) \,\,\,\, (k\ge 1) \\ 1 \hspace{135pt} (k=0) \end{array} \right.$

すると

$\displaystyle \sum_{i=1}^{n} n^{\underline{k}}=\dfrac{1}{k+1}(n+1)^{\underline{k+1} }$

となります。

このことを踏まえて定理を繰り返し用います。

$P_{n}(1)=\dfrac{1}{2} (n+1)^{\underline{2} }$

　 $\displaystyle P_{n}(2)$

$=\displaystyle \sum_{i=1}^{n} P_{i-1}(1)a_{i}$

$=\displaystyle\frac{1}{2} \sum_{i=1}^{n} i^{\underline{2} } \cdot i$

$=\displaystyle\frac{1}{2} \sum_{i=1}^{n} i^{\underline{2} } ( (i-2) +2)$

$=\displaystyle\frac{1}{2} \sum_{i=1}^{n} ( i^{\underline{3} }+2i^{\underline{2} } )$

$=\displaystyle\frac{1}{8} (n+1)^{\underline{4} } +\frac{1}{3} (n+1)^{\underline{3} }$

$=\displaystyle\frac{1}{24}(n+1)n(n-1)(3n+2)$

　 $\displaystyle P_{n}(3)$

$=\displaystyle \sum_{i=1}^{n} P_{i-1}(2)a_{i}$

$=\displaystyle\frac{1}{24} \sum_{i=1}^{n} (3i^{\underline{4}}+8i^{\underline{3} } ) \cdot i$

$=\displaystyle\frac{1}{24} \sum_{i=1}^{n} (3i^{\underline{4}}\cdot i+8i^{\underline{3}} \cdot i )$

$=\displaystyle\frac{1}{24} \sum_{i=1}^{n} ( 3(i^{\underline{5}}+4i^{\underline{4}} )+ 8(i^{\underline{4}}+3i^{\underline{3}} ) )$

$=\displaystyle\frac{1}{24} \sum_{i=1}^{n} ( 3i^{\underline{5}}+ 20i^{\underline{4}}+24i^{\underline{3}})$

$=\displaystyle\frac{1}{48} (n+1)^{\underline{6} } +\frac{1}{6} (n+1)^{\underline{5} }+\frac{1}{4} (n+1)^{\underline{4} }$

$=\displaystyle\frac{1}{48}(n+1)^{2}n^{2}(n-1)(n-2)$

(例)　 $a_{n}=2^{n-1}$ で表される数列 $\{ a_{n} \}$

$P_{n}(1)=2^{n}-1$ です。

定理を繰り返し用います。

　 $\displaystyle P_{n}(2)$

$=\displaystyle \sum_{i=1}^{n} P_{i-1}(1)a_{i}$

$=\displaystyle \sum_{i=1}^{n} ( 2^{i-1}-1 )2^{i-1}$

$=\displaystyle \sum_{i=1}^{n} ( 4^{i-1}-2^{i-1} )$

$=\displaystyle \frac{4^{n}-1 }{3}- (2^{n}-1)$

$=\displaystyle \frac{1}{3}\cdot 4^{n}-2^{n} +\frac{2}{3}$

　 $\displaystyle P_{n}(3)$

$=\displaystyle \sum_{i=1}^{n} P_{i-1}(2)a_{i}$

$=\displaystyle \sum_{i=1}^{n} (\frac{1}{3}\cdot 4^{i-1}-2^{i-1} +\frac{2}{3}) 2^{i-1}$

$=\displaystyle \sum_{i=1}^{n} (\frac{1}{3}\cdot 8^{i-1}-4^{i-1} +\frac{2}{3}\cdot 2^{i-1} )$

$=\displaystyle \frac{8^{n}-1 }{21}-\frac{4^{n}-1 }{3} + \frac{2(2^{n}-1)}{3}$

$=\displaystyle \frac{1}{21}\cdot 8^{n}-\frac{1}{3}\cdot 4^{n}+\frac{2}{3}\cdot 2^{n} -\frac{8}{21}$

このように計算量は多少ありますがどちらの例も「単純計算」の繰り返しのため、非常に実用的です。*2

さて、思ったより長くなってしまったのでこの漸化式の活用のその2は次回扱おうと思います。

それでは最後までお読みいただきありがとうございました。

次回もどうぞよろしくお願いします。

*1:わからない人は綺麗にnとkの式で表される、ぐらいのニュアンスだと思っておいて問題ありません。

*2:表計算ソフトの関数でも簡単に順次求められそうです。計算機が活躍すること間違いなしです。

とぽろじい　～大人の数学自由研究～

高校数学から分かる新しい数学、大学で学ぶ数学を少しずつまとめていくブログです。ゆくゆくは本にまとめたいと思っています。

【数列】異なるk項の積の総和の考察1「異なる2項の積の総和を漸化式で一般化」

k=2のとき

k=3のとき

一般の場合は？

漸化式の活用1：解いてみる