総和（シグマ）を用いた漸化式を摂動法で一般化する

シグマを用いた漸化式を摂動法で一般化する

S_n=\sum_{k=0}^{n}a_k

のような総和の式を一般化するのに摂動法と言う方法があるらしいのですが情報が少ないので
手元の情報を元に記事を書いてみました

プログラミング的にも漸化式を一般化することでfor文で回すことなく$O(1)$にできるので大変おいしいはずです。この方法の正式名称はわかりませんが摂動法と教わったので以後摂動法と呼びます
次に以下のような方法でシグマの式を式変形します

実際に摂動法での式変形をしてみる

S_n=\sum_{k=0}^{n}a_k \\
S_{n+1}=S_n + a_{n+1} \\

以上のような式変形を行って一般化をしますので次に具体的な式でやってみましょう

S_n=\sum_{0\leq k \leq n}ax^k=ax^0+ax^1+ax^2・・・ax^n

単純に0からkまでの値を二乗して足していくだけの簡単な漸化式ですね(´・ω・｀)
次に総和$S_n$を式変形していきます,$a$は与えられた任意の定数と考えてください
もしかしたら見慣れない$\sum$の書き方だなと思われるかもしれませんが$0$から$n$まで繰り返すと言う意味です

for(int k=0 ; k<=n ;k++)
  a+=a*pow(x,k);

これと大体同じ意味です

S_n+ax^{n+1}=ax^0+\sum_{0 \leq k \leq n}ax^{k+1}

最初に示したように$S_{n+1}$の形にします

S_n+ax^{n+1}=a+x\sum_{0 \leq k \leq n}ax^{k}

なぜか上の式で$ax^0$が$a$に置き換わってますが$x^0 =1$なので$ax^0=a$が成り立ちます
ここで右辺に$\sum ax^{k}$が出てきたので$S_n$に置き換えます

S_n+ax^{n+1}=a+x\sum_{0 \leq k \leq n}ax^{k}\\
S_n+ax^{n+1}=a+xS_n

これで$S_n$に右辺も左辺も無事置き換えられたので式変形で一般化していきます

S_n+ax^{n+1}=a+xS_n \\
S_n -xS_n = a-ax^{n+1}\\
S_n(1-x)=a  -ax^{n+1}\\
S_n=\frac{a-ax^{n+1}}{1-x}

無事に一般化できましたね。

実際にプログラムとして走ってもらう

次にプログラミングで動かしてみましょう。
$n=10,a=2,x=3$とします
気分的にプログラム中のカウント変数iをしたので数式も一応添字はiにしておきます

S_n=\sum_{0 \leq i \leq n}2*3^i

もちろん一般式も

S_n=\frac{2-2*3^{10+1}}{1-3}

ちなみに関数電卓で検算したら177146になった
以下のソースで実行しました。my_pow()が累乗を行う自作関数です
インデント等々はスゴイ適当なので悪しからず。
コンパイラはgcc 5.4.0です

#include<stdio.h>
#define N 10
int my_pow(int a,int b){
int pow=a;
int i=0;
    if(b==0){
     return 1;
    }
    for(i=0;i < b-1;i++){
        a=a*pow;
        }
return a;
}

void main(){
int a=2;
int X=3;
int x1=0;
int x2=0;

    for(int i=0 ; i <= N ;i++){
        x1+= a * my_pow(X,i);
    }
        x2= (a - a * my_pow(X,N+1)) / (1-X);
printf("%d %d \n",x1,x2);

return ;
}

実行結果

177146 177146

やったぜ(´・ω・｀)
これでアホみたいにfor文をぶん回す必要がなくなりました。
（補足） 2018年7月26日に数式の一部に追記を追加
（補足）　同年11月14日に日本語がおかしい部分があったので修正