簡単な和から。



などというのはわりかしポピュラーかもしれませんね。
面積が 1/2 の長方形に、面積が 1/4 の正方形をくっつけて、
それに面積が 1/8 の長方形をくっつけて、と続けていくと、
だんだん面積が 1 の正方形に近づいていくというイメージも面白いです。

これの変形として、次のような和も計算出来ます。



実際、次のような式変形を観察すれば良いです：



右辺に、計算したかった元の和の 1/2 倍が現れるので、
これを左辺に移項すればよろしい、という仕組み。
「添え字を１つずらしても和が変わらない」という
無限和ならではの小細工が使えるあたりも楽しみの一つです。

より一般に



という和を計算するにはどうしましょう？
上の計算でやったような小細工の背後には、



という二項展開を使った一般的な式変形があります。
なお、二項係数（組み合わせの数）を表す記号として、
高校数学では使われない記号



をここでは採用しました。
高校で用いられる _pC_k に比べて、
この記号の方が数字が大きく表示されているので見やすいです。

さて、二項展開を用いると、



という計算が出来ます。
さりげなく和の順番の入れ替えが用いられていますが、
今は「和の順番、勝手に入れ替えても大丈夫？」といった配慮が
必要ない状況にあることが分かるので、
がんがん計算しました。

かくして、S(k) たちに関する漸化式



が得られました。
いくつか例を計算してみると、



といった具合。
いくらでも計算できちゃいます。