X^0 + X^1 + X^2 + … + X^n（Σx^k）を解く

tadanori

アルゴリズム×数学が基礎からしっかり身につく本の、053の問題を解くときに悩んだので書いておきます。

問題自体は053 – Sum of 4^Nになります。

問題

$4^0 + 4^1 + …+4^N$を求めなさい

結論ですが、この問題は、以下の式の結果が答えになります。

解答

$$\frac{4^{n+1} – 1}{3}$$

その他のAtCoderに役立つ記事の一覧は以下にあります。

はじめに

この問題の公式解説がないので、自力で解けない場合は、他人の提出結果を見て参考にすることになると思います。ただ、プログラムを見てもなぜそうなるのかがわかりません。

ここでは、問題を一般化した以下について、解き方を解説したいと思います。

$$
x^0 + x^1 + … x^n = \sum_{k=0}^{n}{x^k}
$$

数学的な解法

まず、上の式を$s$とおきます。

$$\begin{eqnarray}
s = \sum_{k=0}^{n}{x^k} &=& x^0 + x^1 + x^2 + … + x^n\\
&=& 1 + x^1 + x^2 + … + x^n
\end{eqnarray}$$

ここで、$x\times s$を考えると、以下のようになります。

$$\begin{eqnarray}
xs &= & x(1 + x^1 + x^2 + … + x^n)\\
&=& x^1 + x^2 + x^3 + … + x^{n+1}\\
&=& (1 + x^1 + x^2 + x^3 + … + x^n) -1 + x^{n+1}\\
&=& s – 1 + x^{n+1}
\end{eqnarray}$$

これを$s$について解きます。

$$\begin{eqnarray}
(x-1)s = x^{n+1} – 1\\
s = \frac{x^{n+1}-1}{x-1}
\end{eqnarray}$$

以上で解くことができました。

結果

$$\sum_{k=0}^{n}{x^k} = \frac{x^{n+1}-1}{x-1}$$

Pythonで問題を解いてみる

pythonの場合、powがmod付きで計算できるので楽です。

まず、$4^{n+1}$を計算し、次に-1しています。

-1した結果が負になった場合は（mod演算なので0になる可能性がある）$10^9+7$だけ足しています。

div3は、逆元の計算です（フェルマーの小定理）。合同式で割り算の計算をする場合は、少し工夫が必要になります。1/3（逆元）を求めたので、これを乗じたら結果となります。

n = int(input())

mod = 10**9 + 7
ans = pow(4, n+1, mod)
ans -= 1
if ans < 0 : ans += mod
div3 = pow(3,  mod-2, mod)
ans = ans * div3 % mod
print(ans)