平成９年春 問４の解説をお願いします。

質問

こんにちは。
今、基本情報処理の受験勉強をしているのですが、「平成９年春　問４」の問題の解説を読んでも理解できなくて困っています。
どなたかもっとわかりやすく解説して頂けないでしょうか。

【問題】
０と１からなる長さ１から長さｎの記号列の総数は幾つあるか。

【解答】
２×（２ｎ－１）

どっから、２×（２ｎ－１）が出てきたのか理解できないです。

お願いします。

回答No.1

BLUEPIXY · ベストアンサー

ｎ＝３の場合を考えてみると
長さ1の記号列：0, 1
長さ2の記号列：00, 01, 10, 11
長さ3の記号列：000, 001, 010, 011, 100, 101, 110, 111
の様になります。
これから、
長さｎの記号列は、２＾ｎ（２のｎ乗）個あるとわかります。
長さ１から長さ３の記号列の総数はというと
２＾１＋２＾２＋２＾３となり、
これから
長さ１から長さｎの記号列の総数はというと
２＾１＋２＾２＋２＾３＋…＋２＾ｎ
になることがわかります。
これは、初項２、公比２の等比数列の和ですから公式から求めてもいいですが
Ｓｎ＝２＾１＋２＾２＋２＾３＋…＋２＾ｎ
Ｓｎ／２＝１＋２＾１＋２＾２＋２＾３＋…＋２＾（ｎ－１）
Ｓｎ－Ｓｎ／２＝２＾ｎ －１
Ｓｎ＝２×（２＾ｎ －１）
になります

お礼

ご回答ありがとうございます。
おかげさまで、理解できまいした。＼(^o^)／