数列 $\lbrace p_n \rbrace$, $\lbrace q_n \rbrace$ に対し $$a _ {n+1}=p_n a_n+q_n$$ を線形漸化式というとき, 数列 $\lbrace a_n \rbrace$ の一般項を求めてみたい. ここで $p_n=0$ となる $n$ があれば, それは初項 $q_n$ の線形漸化式とみなせるので任意の $n$ に対し $p_n\neq 0$ とした場合に帰着する. そのとき $$a_n=\sum _ {l=0}^{n-1}\prod _ {k=l+1}^{n-1}p_kq_l+a_0\prod _ {m=0}^{n-1}p_m$$ であることを示す.
注意.
総和記号・総乗記号において和・積がとれない場合は空和・空積としそれぞれ $0$, $1$ と定める. これは本記事限りのものではなく一般的な約束である.
証明.
$P_n\coloneqq\displaystyle\prod _ {k=0}^n p_k (\neq0)$ で両辺を割り $$\frac{a _ {n+1}}{P_n}=\frac{a_n}{P _ {n-1}}+\frac{q_n}{P_n}$$ となるので $n\geq1$ で $$\frac{a_n}{P _ {n-1}}=\sum _ {l=0} ^ {n-1} \frac{q_l}{P_l}+\frac{a_0}{P_{-1}}$$ が成り立ち, これは $n=0$ でも成立している. よって $$a_n=\sum _ {l=0}^{n-1} \frac{P_{n-1}}{P_l}q_l+a_0P _ {n-1}=\sum _ {l=0}^{n-1}\prod _ {k=l+1}^{n-1}p_kq_l+a_0\prod _ {m=0}^{n-1}p_m$$
