JavaScriptで入力値から数列の値を計算する方法

問題

数値 n を唯一の引数として受け取り、次の漸化式を満たす数列 u の第 n 項 u_n の値を求める JavaScript 関数を作成します。

数列 u の初期値は次のとおりです。

u1 = 0、u2 = 2

そして、隣接する 3 項は常に次の等式を満たすものとします。

6unun+1 − 5unun+2 + un+1un+2 = 0

アプローチ：一般項を見抜く

この漸化式には項同士の積が含まれており、一見すると複雑です。しかし、u_n = 2ⁿ という等比数列を代入してみると、この式が恒等的に成立することが分かります。

6 · 2n · 2n+1 − 5 · 2n · 2n+2 + 2n+1 · 2n+2
= 22n+1(6 − 10 + 4)
= 0

つまり、この数列の一般項は「2 のべき乗」です。したがって、ループで順番に計算する必要はなく、n が与えられれば 2ⁿ を一度計算するだけで答えが求まります。

コード例

以下が実際のコードです。

const num = 13;

const sequenceSum = (num = 1) => {
  const res = Math.pow(2, num);
  return res;
};

console.log(sequenceSum(num));

出力

8192

引数として 13 を渡しているため、2 の 13 乗である 8192 が出力されます。

より簡潔な書き方

ES2016 以降ではべき乗演算子 ** が使えるため、関数は 1 行で書けます。

const sequenceSum = (num = 1) => 2 ** num;

ポイントまとめ

• 複雑な漸化式に出会ったら、まず等比数列などの簡単な候補を代入して検証すると、一般項が見つかることがあります。
• 一般項が分かれば、逐次計算の代わりに Math.pow や ** 演算子による O(1) の計算で即座に答えを得られます。
• 大きな n に対しても高速に動作するため、実用面でも非常に有利です。