数列

フィボナッチ数列とは，1,1,2,3,5,8,13,21 のように，各項が「前の2つを足した値」になるような数列のこと。

$S_1=\displaystyle\sum_{k=1}^nk=\dfrac{1}{2}n(n+1)$

$S_2=\displaystyle\sum_{k=1}^nk^2=\dfrac{1}{6}n(n+1)(2n+1)$

$S_3=\displaystyle\sum_{k=1}^nk^3=\{\dfrac{1}{2}n(n+1)\}^2$

$S_4=\displaystyle\sum_{k=1}^nk^4=\dfrac{1}{30}n(n+1)(2n+1)(3n^2+3n-1)$

$S_5=\displaystyle\sum_{k=1}^nk^5=\dfrac{1}{12}n^2(n+1)^2(2n^2+2n-1)$

数列 $a_n$ に対して，その母関数を

$f(x)=\displaystyle\sum_{k=0}^{\infty}a_kx^k$

と定義する。

任意の自然数 $p$ に対して，

$S_n=\displaystyle\sum_{k=1}^nk^pr^k$

は2通りの方法で計算できる。

$a_0=2, a_{n+1}=a_n^2-a_n+1$

で定義される数列をシルベスターの数列と言う

漸化式の $a_n$ や $a_{n-1}$ の係数に $n$ が含まれている場合，両辺に何かしらかけたり割ったりして $f(n+1)a_{n+1}$ と $f(n)a_n$ を作り出せばうまくいくことが多い

$\displaystyle\sum_{k=1}^nf_k(x)$ を計算したいときに

$f_k(x)=g_k(x)-g_{k+1}(x)$ と分解できればOK

• 有理数の連分数展開はユークリッドの互除法に対応している
• 有理数 $\iff$ 連分数展開が有限回で終わる

等比数列とは，$1,3,9,27,81$ のように「一定の比率で変化していく」ような数列のことです。 $1+3+9+27+81$ のような等比数列の和は， 等比数列の和の公式 を使って計算することができます。

数列の極限は，

1．（有限の値に）収束する

2A．正の無限大に発散する

2B．負の無限大に発散する

3．振動する

のいずれかである。2と3の場合をいずれも発散すると言う。

無限等比級数とは，無限に続く等比数列の和のことです。

例えば，

$1+\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{8}+\cdots$

は無限に続く等比数列の和なので，無限等比級数です。

初項が $a$ ，公差が $d$ ，項数が $n$ であるような等差数列の和は， $S=\dfrac{1}{2}n(2a+(n-1)d)$

数列 $a_n$ の一般項を求めるために，階差数列 $b_n=a_{n+1}-a_{n}$ を用いるとうまくいくことがある。

$0$ 以上 $1$ 以下であり，分母が $n$ 以下であるような既約分数を小さい順に並べた数列を（$n$ に対応する）ファレイ数列という。

$n$ 段のハノイの塔の最短手数は $2^n-1$

$p_0=3,p_1=0,p_2=2$,

$p_n=p_{n-2}+p_{n-3}\:(n\geq 3)$

によって定まる数列 $p_n$ をペラン数列と言う。

円周上に $n$ 個の頂点を打ち，その全ての2頂点間を線分で結ぶ。このとき，円は $M$ 個の領域に分割されるとする。

$M$ の最大値は $a_n=\dfrac{1}{24}(n^4-6n^3+23n^2-18n+24)$

シグマ記号の公式：

シグマ記号 $\Sigma$ は「たくさんの足し算」を簡潔に表すための記号。シグマ記号に関連して，以下の公式が成立する： $$\begin{aligned} \sum_{k=1}^{n} a &= na \\ \sum_{k=1}^{n} k &= \dfrac{1}{2} n(n+1) \\ \sum_{k=1}^{n} k^2 &= \dfrac{1}{6}n(n+1)(2n+1) \\ \sum_{k=1}^{n} k^3 &= \left\{\dfrac{1}{2} n(n+1)\right\}^2\\ \sum_{k=1}^{n} r^{k-1} &= \dfrac{1-r^n}{1-r} \quad (r \neq 1)\\ \end{aligned}$$