多項式と等比数列の積の形で表された数列の和を求めること

 先日,フモフモさん氏(twitter: @fumofumobun)により,一般項が  a_n = (p n + q) r^{n - 1}  (r \not= 1) の形で表された数列の和を爆速で計算する手法が Twitter に投稿されました。


 ハ!? ヤバ!!!!! と初見時は思ったもので,上の公式によって QOL の爆上げという大変な恩恵を享受してしまいました。そこで本記事ではこれを一般化し,( n N多項式)×(等比数列)の形で表された数列  \{ a_n \} の初項から第  n 項までの和を公式として表現することを試みます。本記事で紹介する公式による更なる QOL の向上はもはや不可避です。



目次

準備

  •  \mathbf{N} を正の整数全体の集合, \mathbf{Z} を整数全体の集合, \mathbf{C}複素数全体の集合とします。
  •  \binom{n}{r} を二項係数とします。すなわち

 {
    \displaystyle
    \binom{n}{r} = {}_{n\!}\mathrm{C}_r = \frac{n!}{r! (n - r)!}
}

 と定めます。

  • 関数  f \, \colon \, \mathbf{Z} \to \mathbf{C} に対し, f の後退差分  \nabla f \, \colon \, \mathbf{Z} \to \mathbf{C}

 \nabla f(n) = f(n) - f(n - 1) \quad (n \in \mathbf{Z}) \

 で定義します。*1

設定

 数列  \{ a_n \} の一般項が,

 {
    \begin{align*}
        a_n &= (p_N n^N + p_{N - 1} n^{N - 1} + \cdots + p_1 n + p_0) r^{n - 1} \\
            &= \left( \sum_{k = 0}^N p_k n^k \right) r^{n - 1} \quad (n = 1,\, 2,\, 3,\, \ldots)
    \end{align*}
}

で表されているとします。ただし, N は非負の整数で,各  p_k\ (k = 0,\, 1,\, \ldots,\, N) および  r複素数です。また, r \not= 0,\ r \not= 1 とします。この数列に対し,和

 \displaystyle S_n = \sum_{k = 1}^n a_k \
を計算することを試みます。

計算

 上の数列  \{ a_n \} に対し,

 a_n = \nabla f(n) \quad (n \in \mathbf{N}) \

を満たすような関数  f \, \colon \, \mathbf{Z} \to \mathbf{C} をまず見つけましょう。 \{ a_n \} の一般項の形から, f(n)

 {
    \begin{align*}
        f(n) &= (A_N n^N + A_{N - 1} n^{N - 1} + \cdots + A_1 n + A_0) r^n \\
            &= \left( \sum_{k = 0}^N A_k n^k \right) r^n
    \end{align*}
}

と表せることが推測されます。ここで,各  A_k複素数で,2行目の和における  n = 0 の場合について  0^0 = 1 と定めます。このとき,

 {
    \displaystyle
    f(n) = \left( \sum_{k = 0}^N r A_k n^k \right) r^{n - 1} 
}

であり,さらに

 {
    \begin{align*}
        f(n - 1) &= \left( \sum_{k = 0}^N A_k (n - 1)^k \right) r^{n - 1} \\
            &= r^{n - 1} \sum_{k = 0}^N A_k \left( \sum_{l = 0}^k \binom{k}{l} (-1)^{k - l} n^l \right) \\
            &= r^{n - 1} \sum_{k = 0}^N \sum_{l = 0}^k A_k \binom{k}{l} (-1)^{k - l} n^l \\
            &= r^{n - 1} \sum_{l = 0}^N \sum_{k = l}^N A_k \binom{k}{l} (-1)^{k - l} n^l \\
            &= r^{n - 1} \sum_{k = 0}^N \sum_{l = k}^N A_l \binom{l}{k} (-1)^{l - k} n^k \\
            &= \sum_{k = 0}^N \left( \sum_{l = k}^N A_l \binom{l}{k} (-1)^{l - k} n^k \right) r^{n - 1} \\
    \end{align*}
}

となります。よって,  \nabla f(n) を計算すると

 {
    \begin{align*}
        \nabla f(n) &= \sum_{k = 0}^N \left( r A_k n^k - \sum_{l = k}^N A_l \binom{l}{k} (-1)^{l - k} n^k \right) r^{n - 1} \\
            &=\left( r A_N n^N - A_N n^N \right) r^{n - 1} \\
            & \qquad {} + \sum_{k = 0}^{N - 1} \left( r A_k n^k - \sum_{l = k}^N A_l \binom{l}{k} (-1)^{l - k} n^k \right) r^{n - 1} \\
            &= (r - 1) A_N n^N r^{n - 1} \\
            & \qquad {} + \sum_{k = 0}^{N - 1} \left( r A_k - A_k - \sum_{l = k + 1}^N A_l \binom{l}{k} (-1)^{l - k} \right) n^k r^{n - 1} \\
            &= \Biggl\{ (r - 1) A_N n^N \\
            & \qquad {} + \sum_{k = 0}^{N - 1} \left( (r - 1) A_k - \sum_{l = k + 1}^N A_l \binom{l}{k} (-1)^{l - k} \right) n^k \Biggr\} r^{n - 1}
    \end{align*}
}

となります。したがって, a_n = \nabla f(n) が任意の  n \in \mathbf{N} で成り立つことは,

 {
    \begin{align*}
        \sum_{k = 0}^N p_k n^k &= (r - 1) A_N n^N \\
            & \quad {} + \sum_{k = 0}^{N - 1} \left( (r - 1) A_k - \sum_{l = k + 1}^N A_l \binom{l}{k} (-1)^{l - k} \right) n^k
    \end{align*}
}

が任意の  n \in \mathbf{N} に対して成り立つことと同値です。これを  n についての恒等式とみて係数を比較すると,

 {
    \begin{align*}
        p_N &= (r - 1) A_N, \\
        p_k &= (r - 1) A_k - \sum_{l = k + 1}^N A_l \binom{l}{k} (-1)^{l - k} \quad (k = 0,\, 1,\, 2,\, \ldots,\, N - 1)
    \end{align*}
}

であればよいことが分かります。これより,

 {
    \begin{align*}
        A_N &= \frac{p_N}{r - 1}, \\
        A_k &=\frac{p_k + \sum_{l = k + 1}^N \binom{l}{k} (-1)^{l - k} A_l}{r - 1} \quad (k = 0,\, 1,\, 2,\, \ldots,\, N - 1)
    \end{align*}
}

が得られます。これら各  A_k は, k = N,\, N - 1,\, N - 2,\, \ldots,\, 2,\, 1,\, 0 の順に計算することができます。

 以上より,求める和  S_n は,

 {
    \begin{align*}
        S_n &= \sum_{k = 1}^n a_k \\
            &= \sum_{k = 1}^n (f(k) - f(k - 1)) \\
            &= f(n) - f(0) \\
            &= \left( \sum_{k = 0}^N A_k n^k \right) r^n - A_0
    \end{align*}
}

となります。

まとめ

  N を非負の整数, p_k\ (k = 0,\, 1,\, \ldots,\, N)複素数 r r \not= 0,\ r \not= 1 を満たす複素数とします。一般項が

 {
    \begin{align*}
        a_n &= (p_N n^N + p_{N - 1} n^{N - 1} + \cdots + p_1 n + p_0) r^{n - 1} \\
            &= \left( \sum_{k = 0}^N p_k n^k \right) r^{n - 1} \quad (n = 1,\, 2,\, 3,\, \ldots)
    \end{align*}
}

で表されている数列  \{ a_n \} について,その第  n 項までの和  S_n = \sum_{k = 1}^n a_k \ は,

 {
    \begin{align*}
        S_n &= \left( \sum_{k = 0}^N A_k n^k \right) r^n - A_0 \\
            &= (A_N n^N + A_{N - 1} n^{N - 1} + \cdots + A_1 n + A_0) r^{n} - A_0
    \end{align*}
}

と表せます。ここで,各係数  A_k

 {
    \begin{align*}
        A_N &= \frac{p_N}{r - 1}, \\
        A_k &=\frac{p_k + \sum_{l = k + 1}^N \binom{l}{k} (-1)^{l - k} A_l}{r - 1} \quad (k = N - 1,\, N - 2,\, \ldots,\, 2,\, 1,\, 0)
    \end{align*}
}

で与えられます。

具体例

 いくつかの具体例を以下に紹介します。

N = 1 の場合

 上で得られた式が,フモフモさん氏の公式の拡張となっていることを確かめましょう。 N = 1 の場合を考え,数列  \{ a_n \} の一般項が  a_n = (p_1 n + p_0) r^{n - 1} で与えられているとします。このとき,

 {
    \begin{align*}
        A_1 &= \frac{p_1}{r - 1}, \\
        A_0 &= \frac{p_0 + \binom{1}{0} (-1)^{1 - 0} A_1}{r - 1} = \frac{p_0 - A_1}{r - 1}
    \end{align*}
}

とすれば, \sum_{k = 1}^n a_k = ( A_1 n + A_0 ) r^n - A_0 が成り立ちます。これは確かにフモフモさん氏の公式と一致しています。

例題. \displaystyle \sum_{k = 1}^n (3 k - 2) \cdot 3^{k - 1} を計算せよ。
解答. \displaystyle A_1 = \frac{3}{3 - 1} = \frac{3}{2} \displaystyle A_0 = \frac{-2 - \frac{3}{2}}{3 - 1} = -\frac{7}{4} より,

 {
    \begin{align*}
        \sum_{k = 1}^n (3 k - 2) \cdot 3^{k - 1} &= \left( \frac{3}{2} n - \frac{7}{4} \right) \cdot 3^n + \frac{7}{4} \\
            &= \frac{(6 n - 7) \cdot 3^n + 7}{4}.
    \end{align*}
}

N = 2 の場合

 数列  \{ a_n \} の一般項が  a_n = (p_2 n^2 + p_1 n + p_0) r^{n - 1} で与えられているとします。このとき,

 {
    \begin{align*}
        A_2 &= \frac{p_2}{r - 1}, \\
        A_1 &= \frac{p_1 - 2 A_2}{r - 1}, \\
        A_0 &= \frac{p_0 + A_2 - A_1}{r - 1} \\
    \end{align*}
}

とすれば, \sum_{k = 1}^n a_k = ( A_2 n^2 + A_1 n + A_0 ) r^n - A_0 が成り立ちます。

例題. \displaystyle \sum_{k = 1}^n (2 k^2 - 4 k + 3) \cdot 4^{k - 1} を計算せよ。
解答.
 {
    \begin{align*}
        A_2 &= \frac{2}{4 - 1} = \frac{2}{3}, \\
        A_1 &= \frac{-4 - 2 \cdot \frac{2}{3}}{4 - 1} = -\frac{16}{9}, \\
        A_0 &= \frac{3 + \frac{2}{3} - (-\frac{16}{9})}{4 - 1} = \frac{49}{27}
    \end{align*}
}

より,

 {
    \begin{align*}
        \sum_{k = 1}^n (2 k^2 - 4 k + 3) \cdot 4^{k - 1} &= \left( \frac{2}{3} n^2 - \frac{16}{9} n + \frac{49}{27} \right) \cdot 4^n - \frac{49}{27} \\
            &= \frac{(18 n^2 - 48 n + 49) \cdot 4^n - 49}{27}.
    \end{align*}
}

N = 3 の場合

 数列  \{ a_n \} の一般項が  a_n = (p_3 n^3 + p_2 n^2 + p_1 n + p_0) r^{n - 1} で与えられているとき,

 {
    \begin{align*}
        A_3 &= \frac{p_3}{r - 1}, \\
        A_2 &= \frac{p_2 - 3 A_3}{r - 1}, \\
        A_1 &= \frac{p_1 + 3 A_3 - 2 A_2}{r - 1} \\
        A_0 &= \frac{p_0 - A_3 + A_2 - A_1}{r - 1} \\
    \end{align*}
}

とすれば, \sum_{k = 1}^n a_k = ( A_3 n^3 + A_2 n^2 + A_1 n + A_0 ) r^n - A_0 が成り立ちます。

N = 4 の場合

 数列  \{ a_n \} の一般項が  a_n = (p_4 n^4 + p_3 n^3 + p_2 n^2 + p_1 n + p_0) r^{n - 1} で与えられているとき,

 {
    \begin{align*}
        A_4 &= \frac{p_4}{r - 1}, \\
        A_3 &= \frac{p_3 - 4 A_4}{r - 1}, \\
        A_2 &= \frac{p_2 + 6 A_4 - 3 A_2}{r - 1} \\
        A_1 &= \frac{p_1 - 4 A_4 + 3 A_2 - 2 A_1}{r - 1} \\
        A_0 &= \frac{p_0 + A_4 - A_2 + A_1 - A_0}{r - 1} \\
    \end{align*}
}

とすれば, \sum_{k = 1}^n a_k = ( A_4 n^4 + A_3 n^3 + A_2 n^2 + A_1 n + A_0 ) r^n - A_0 が成り立ちます。

 右辺の  A_4 の係数に着目すると,符号はマイナスから始まり,プラス,マイナス,プラスというようにかわりばんこに出現し,係数の絶対値には二項係数  \binom{4}{r}\ (r = 1,\, 2,\, 3,\, 4) がきれいに並んでいることがわかります。他の  A_3,\ A_2,\ A_1,\ A_0 も同様の規則で並んでおり,これを理解すれば公式を覚えることは容易いでしょう。


 質問や間違い等ございましたら,本記事へのコメント,もしくは私の Twitter (@hogehogehogege) までお気軽にお尋ねください~!


*1: \nabla は後退差分作用素 (backward difference operator) などと呼ばれます。