ここで扱う数列は離散的な現象を扱う際に威力を発揮する。数列はいろいろなところに応用されている。例えば、単利の計算には等差数列が、複利の計算には等比数列が応用できる。
数を一列に並べたもの数列 （sequence of numbers）という。数列のそれぞれの数を項 という。
10
,
9
,
8
,
7
,
6
,
5
,
4
,
3
,
2
,
1
,
0
{\displaystyle 10,9,8,7,6,5,4,3,2,1,0}
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
,
⋯
{\displaystyle 1,2,3,4,5,6,7,8,9,\cdots }
1
,
3
,
5
,
7
,
9
,
11
,
13
,
⋯
{\displaystyle 1,3,5,7,9,11,13,\cdots }
1
,
3
,
9
,
27
,
81
,
⋯
{\displaystyle 1,3,9,27,81,\cdots }
1番目から数えて、第1項、第2項、第3項のように、n 番目の項を第 n 項という。特に第1項は初項 （first term）ともいう。以下、特に断りのない限り n は 1 以上の自然数とする。
第
n
{\displaystyle n}
a
n
{\displaystyle a_{n}}
{
a
n
}
{\displaystyle \{a_{n}\}}
{
a
n
}
{\displaystyle \{a_{n}\}}
a
1
,
a
2
,
a
3
,
a
4
,
⋯
{\displaystyle a_{1},a_{2},a_{3},a_{4},\cdots }
である。 数列
{
a
n
}
{\displaystyle \{a_{n}\}}
n 項
a
n
{\displaystyle a_{n}}
n の式で表すとき、この式を数列
{
a
n
}
{\displaystyle \{a_{n}\}}
一般項 （general term）という。たとえば、数列 1, 2, 3, 4, 5, ... の一般項は
a
n
=
n
{\displaystyle a_{n}=n}
a
n
=
2
n
{\displaystyle a_{n}=2n}
項の数が有限である数列を有限数列 （finite sequence of numbers）という。有限数列の最後の項を末項 （final term）といい、項の総数を項数 （arity）という。末項が存在しない数列を無限数列 （infinite sequence of numbers）という。数列 1, 2, 3, 4, 5, ... は無限数列である。
解答
第1項から順に
−
2
,
1
,
4
,
7
,
10
{\displaystyle -2,1,4,7,10}
第1項から順に
3
,
9
,
27
,
81
,
243
{\displaystyle 3,9,27,81,243}
第1項から順に
1
,
4
,
27
,
256
,
3125
{\displaystyle 1,4,27,256,3125}
演習問題
1
,
4
,
9
,
16
,
25
,
⋯
{\displaystyle 1,4,9,16,25,\cdots }
2
,
4
,
8
,
16
,
32
,
⋯
{\displaystyle 2,4,8,16,32,\cdots }
解答
n
2
{\displaystyle n^{2}}
n
5
−
15
n
4
+
85
n
3
−
224
n
2
+
274
n
−
120
{\displaystyle n^{5}-15n^{4}+85n^{3}-224n^{2}+274n-120}
[ 1]
2
n
{\displaystyle 2^{n}}
数列
{
a
n
}
{\displaystyle \{a_{n}\}}
d
{\displaystyle d}
n
{\displaystyle n}
a
n
+
1
=
a
n
+
d
{\displaystyle a_{n+1}=a_{n}+d}
{
a
n
}
{\displaystyle \{a_{n}\}}
等差数列 （arithmetic progression (sequence)）といい、
d
{\displaystyle d}
公差 (common difference)という。
a
n
+
1
=
a
n
+
d
{\displaystyle a_{n+1}=a_{n}+d}
a
n
+
1
−
a
n
=
d
{\displaystyle a_{n+1}-a_{n}=d}
差 が等 しい数列である。
例えば、
2
,
5
,
8
,
11
,
14
,
⋯
{\displaystyle 2,5,8,11,14,\cdots }
初項
a
1
{\displaystyle a_{1}}
d
{\displaystyle d}
{
a
n
}
{\displaystyle \{a_{n}\}}
a
2
=
a
1
+
d
{\displaystyle a_{2}=a_{1}+d}
a
3
=
a
2
+
d
=
a
1
+
2
d
{\displaystyle a_{3}=a_{2}+d=a_{1}+2d}
a
4
=
a
3
+
d
=
a
1
+
3
d
{\displaystyle a_{4}=a_{3}+d=a_{1}+3d}
a
5
=
a
4
+
d
=
a
1
+
4
d
{\displaystyle a_{5}=a_{4}+d=a_{1}+4d}
a
6
=
a
5
+
d
=
a
1
+
5
d
{\displaystyle a_{6}=a_{5}+d=a_{1}+5d}
... なので、一般項は
a
n
=
a
1
+
(
n
−
1
)
d
{\displaystyle a_{n}=a_{1}+(n-1)d}
a
1
{\displaystyle a_{1}}
d
{\displaystyle d}
{
a
n
}
{\displaystyle \{a_{n}\}}
S
n
{\displaystyle S_{n}}
S
n
=
a
1
+
(
a
1
+
d
)
+
(
a
1
+
2
d
)
+
⋯
+
(
a
n
−
d
)
+
a
n
{\displaystyle S_{n}=a_{1}+(a_{1}+d)+(a_{1}+2d)+\cdots +(a_{n}-d)+a_{n}}
である。 これを逆順に並び替えて
S
n
=
a
n
+
(
a
n
−
d
)
+
(
a
n
−
2
d
)
+
⋯
+
(
a
1
+
d
)
+
a
1
{\displaystyle S_{n}=a_{n}+(a_{n}-d)+(a_{n}-2d)+\cdots +(a_{1}+d)+a_{1}}
を得る。この2つをそれぞれ足すと
2
S
n
=
n
(
a
1
+
a
n
)
{\displaystyle 2S_{n}=n(a_{1}+a_{n})}
S
n
=
n
2
(
a
1
+
a
n
)
{\displaystyle S_{n}={\frac {n}{2}}(a_{1}+a_{n})}
a
n
=
a
1
+
(
n
−
1
)
d
{\displaystyle a_{n}=a_{1}+(n-1)d}
S
n
=
n
2
(
2
a
1
+
(
n
−
1
)
d
)
{\displaystyle S_{n}={\frac {n}{2}}(2a_{1}+(n-1)d)}
である。
演習問題
S
n
{\displaystyle S_{n}}
解答
a
n
=
2
n
+
1
{\displaystyle a_{n}=2n+1}
S
n
=
n
2
+
2
n
{\displaystyle S_{n}=n^{2}+2n}
a
,
b
,
c
{\displaystyle a,b,c}
c
−
b
=
b
−
a
{\displaystyle c-b=b-a}
2
b
=
a
+
c
{\displaystyle 2b=a+c}
また、
2
b
=
a
+
c
{\displaystyle 2b=a+c}
c
−
b
=
b
−
a
{\displaystyle c-b=b-a}
a
,
b
,
c
{\displaystyle a,b,c}
以上より、
2
b
=
a
+
c
⟺
{\displaystyle 2b=a+c\iff }
a
,
b
,
c
{\displaystyle a,b,c}
演習問題
2
,
2
x
−
1
,
x
2
{\displaystyle 2,2x-1,x^{2}}
x
{\displaystyle x}
解答
2
(
2
x
−
1
)
=
x
2
+
2
{\displaystyle 2(2x-1)=x^{2}+2}
x
=
2
{\displaystyle x=2}
演習問題
150以下の自然数の内、7で割った余りが2である自然数の和を求めよ。
数列
{
a
n
}
{\displaystyle \{a_{n}\}}
r
{\displaystyle r}
n
{\displaystyle n}
a
n
+
1
=
r
a
n
{\displaystyle a_{n+1}=ra_{n}}
等比数列 （geometric progression）といい、
r
{\displaystyle r}
公比 （common ratio）という。
a
n
+
1
=
r
a
n
{\displaystyle a_{n+1}=ra_{n}}
a
n
+
1
a
n
=
r
{\displaystyle {\frac {a_{n+1}}{a_{n}}}=r}
比 が等 しい数列である。
例えば、
3
,
6
,
12
,
24
,
48
,
⋯
{\displaystyle 3,6,12,24,48,\cdots }
初項
a
1
{\displaystyle a_{1}}
r
{\displaystyle r}
{
a
n
}
{\displaystyle \{a_{n}\}}
a
2
=
a
1
r
{\displaystyle a_{2}=a_{1}r}
a
3
=
a
2
r
=
a
1
r
2
{\displaystyle a_{3}=a_{2}r=a_{1}r^{2}}
a
4
=
a
3
r
=
a
1
r
3
{\displaystyle a_{4}=a_{3}r=a_{1}r^{3}}
a
5
=
a
4
r
=
a
1
r
4
{\displaystyle a_{5}=a_{4}r=a_{1}r^{4}}
a
6
=
a
5
r
=
a
1
r
5
{\displaystyle a_{6}=a_{5}r=a_{1}r^{5}}
のようになることから、等比数列の一般項は
a
n
=
a
1
r
n
−
1
{\displaystyle a_{n}=a_{1}r^{n-1}}
a
1
{\displaystyle a_{1}}
r
{\displaystyle r}
(
≠
1
)
{\displaystyle (\neq 1)}
{
a
n
}
{\displaystyle \{a_{n}\}}
S
n
{\displaystyle S_{n}}
S
n
=
a
1
+
a
1
r
+
a
1
r
2
+
⋯
+
a
1
r
n
−
2
+
a
1
r
n
−
1
{\displaystyle S_{n}=a_{1}+a_{1}r+a_{1}r^{2}+\cdots +a_{1}r^{n-2}+a_{1}r^{n-1}}
である。両辺に
r
{\displaystyle r}
r
S
n
=
a
1
r
+
a
1
r
2
+
a
1
r
3
+
⋯
+
a
1
r
n
−
1
+
a
1
r
n
{\displaystyle rS_{n}=a_{1}r+a_{1}r^{2}+a_{1}r^{3}+\cdots +a_{1}r^{n-1}+a_{1}r^{n}}
を得る。
(2) - (1) より
r
S
n
−
S
n
=
a
1
r
n
−
a
1
{\displaystyle rS_{n}-S_{n}=a_{1}r^{n}-a_{1}}
S
n
=
a
1
(
r
n
−
1
)
r
−
1
{\displaystyle S_{n}={\frac {a_{1}(r^{n}-1)}{r-1}}}
また
r
=
1
{\displaystyle r=1}
S
n
{\displaystyle S_{n}}
S
n
=
n
a
1
{\displaystyle S_{n}=na_{1}}
[ 2]
演習問題
S
n
{\displaystyle S_{n}}
解答
a
n
=
3
⋅
4
n
−
1
{\displaystyle a_{n}=3\cdot 4^{n-1}}
S
n
=
4
n
−
1
{\displaystyle S_{n}=4^{n}-1}
それぞれ 0 ではない数
a
,
b
,
c
{\displaystyle a,b,c}
b
a
=
c
b
{\displaystyle {\frac {b}{a}}={\frac {c}{b}}}
b
2
=
a
c
{\displaystyle b^{2}=ac}
また、
b
2
=
a
c
{\displaystyle b^{2}=ac}
b
a
=
c
b
{\displaystyle {\frac {b}{a}}={\frac {c}{b}}}
a
,
b
,
c
{\displaystyle a,b,c}
よって、
b
2
=
a
c
⟺
{\displaystyle b^{2}=ac\iff }
a
,
b
,
c
{\displaystyle a,b,c}
ここで、総和を効率よく表せる表記法について学ぼう。
数列
{
a
n
}
{\displaystyle \{a_{n}\}}
∑
k
=
m
n
a
k
{\displaystyle \sum _{k=m}^{n}a_{k}}
∑
k
=
m
n
a
k
=
a
m
+
a
m
+
1
+
a
m
+
2
+
⋯
+
a
n
−
1
+
a
n
{\displaystyle \sum _{k=m}^{n}a_{k}=a_{m}+a_{m+1}+a_{m+2}+\cdots +a_{n-1}+a_{n}}
である。[ 3]
例えば、
∑
k
=
2
4
(
k
2
−
2
k
)
=
(
2
2
−
2
⋅
2
)
+
(
3
2
−
2
⋅
3
)
+
(
4
2
−
2
⋅
4
)
{\displaystyle \sum _{k=2}^{4}(k^{2}-2k)=(2^{2}-2\cdot 2)+(3^{2}-2\cdot 3)+(4^{2}-2\cdot 4)}
ちなみにこの Σ はギリシア文字のシグマの大文字である。これは、Sum(和)を意味するラテン語 Summa の頭文字 S に対応するギリシャ文字である。
{
a
n
}
{\displaystyle \{a_{n}\}}
{
b
n
}
{\displaystyle \{b_{n}\}}
[ 4]
c
{\displaystyle c}
∑
k
=
m
n
(
a
k
+
b
k
)
=
(
a
m
+
b
m
)
+
(
a
m
+
1
+
b
m
+
1
)
+
⋯
+
(
a
n
+
b
n
)
=
(
a
m
+
a
m
+
1
+
⋯
+
a
n
)
+
(
b
m
+
b
m
+
1
+
⋯
+
b
n
)
=
∑
k
=
m
n
a
k
+
∑
k
=
m
n
b
k
{\displaystyle {\begin{aligned}\sum _{k=m}^{n}(a_{k}+b_{k})&=(a_{m}+b_{m})+(a_{m+1}+b_{m+1})+\cdots +(a_{n}+b_{n})\\&=(a_{m}+a_{m+1}+\cdots +a_{n})+(b_{m}+b_{m+1}+\cdots +b_{n})\\&=\sum _{k=m}^{n}a_{k}+\sum _{k=m}^{n}b_{k}\end{aligned}}}
[ 5]
また、
∑
k
=
m
n
c
a
k
=
c
a
m
+
c
a
m
+
1
+
⋯
+
c
a
n
=
c
(
a
m
+
a
m
+
1
+
⋯
+
a
n
)
=
c
∑
k
=
m
n
a
k
{\displaystyle {\begin{aligned}\sum _{k=m}^{n}ca_{k}&=ca_{m}+ca_{m+1}+\cdots +ca_{n}\\&=c(a_{m}+a_{m+1}+\cdots +a_{n})\\&=c\sum _{k=m}^{n}a_{k}\end{aligned}}}
である。
ここで、
∑
k
=
1
n
k
=
1
+
2
+
⋯
+
n
{\displaystyle \sum _{k=1}^{n}k=1+2+\cdots +n}
等差数列 で習ったことを思い出せば、
∑
k
=
1
n
k
{\displaystyle \sum _{k=1}^{n}k}
∑
k
=
1
n
k
=
1
2
n
(
n
+
1
)
{\displaystyle \sum _{k=1}^{n}k={\frac {1}{2}}n(n+1)}
また、等比数列の和を総和記号を使って書き直せば、
∑
k
=
1
n
a
r
k
−
1
=
a
(
r
n
−
1
)
r
−
1
{\displaystyle \sum _{k=1}^{n}ar^{k-1}={\frac {a(r^{n}-1)}{r-1}}}
∑
k
=
1
n
k
2
{\displaystyle \sum _{k=1}^{n}k^{2}}
(
k
+
1
)
3
−
k
3
=
3
k
2
+
3
k
+
1
{\displaystyle (k+1)^{3}-k^{3}=3k^{2}+3k+1}
k
{\displaystyle k}
n
{\displaystyle n}
2
3
−
1
3
=
3
⋅
1
2
+
3
⋅
1
+
1
{\displaystyle 2^{3}-1^{3}=3\cdot 1^{2}+3\cdot 1+1}
3
3
−
2
3
=
3
⋅
2
2
+
3
⋅
2
+
1
{\displaystyle 3^{3}-2^{3}=3\cdot 2^{2}+3\cdot 2+1}
4
3
−
3
3
=
3
⋅
3
2
+
3
⋅
3
+
1
{\displaystyle 4^{3}-3^{3}=3\cdot 3^{2}+3\cdot 3+1}
⋮
{\displaystyle \vdots }
(
n
+
1
)
3
−
n
3
=
3
n
2
+
3
n
+
1
{\displaystyle (n+1)^{3}-n^{3}=3n^{2}+3n+1}
n
{\displaystyle n}
左辺はほとんどが打ち消し合い、
(
n
+
1
)
3
−
1
{\displaystyle (n+1)^{3}-1}
(
n
+
1
)
3
−
1
=
3
∑
k
=
1
n
k
2
+
3
∑
k
=
1
n
k
+
n
{\displaystyle (n+1)^{3}-1=3\sum _{k=1}^{n}k^{2}+3\sum _{k=1}^{n}k+n}
である。ここで
∑
k
=
1
n
k
=
1
2
n
(
n
+
1
)
{\displaystyle \sum _{k=1}^{n}k={\frac {1}{2}}n(n+1)}
∑
k
=
1
n
k
2
{\displaystyle \sum _{k=1}^{n}k^{2}}
∑
k
=
1
n
k
2
=
1
6
n
(
n
+
1
)
(
2
n
+
1
)
{\displaystyle \sum _{k=1}^{n}k^{2}={\frac {1}{6}}n(n+1)(2n+1)}
を得る。
同様に
∑
k
=
1
n
k
3
{\displaystyle \sum _{k=1}^{n}{k^{3}}}
(
k
+
1
)
4
−
k
4
=
4
k
3
+
6
k
2
+
4
k
+
1
{\displaystyle (k+1)^{4}-k^{4}=4k^{3}+6k^{2}+4k+1}
k
{\displaystyle k}
n
{\displaystyle n}
(
n
+
1
)
4
−
1
=
4
∑
k
=
1
n
k
3
+
6
∑
k
=
1
n
k
2
+
4
∑
k
=
1
n
k
+
n
{\displaystyle (n+1)^{4}-1=4\sum _{k=1}^{n}k^{3}+6\sum _{k=1}^{n}k^{2}+4\sum _{k=1}^{n}k+n}
4
∑
k
=
1
n
k
3
=
(
n
+
1
)
4
−
1
−
6
⋅
1
6
n
(
n
+
1
)
(
2
n
+
1
)
−
4
⋅
1
2
n
(
n
+
1
)
−
n
=
(
n
4
+
4
n
3
+
6
n
2
+
4
n
)
−
(
2
n
3
+
3
n
2
+
n
)
−
2
(
n
2
+
n
)
−
n
=
n
4
+
2
n
3
+
n
2
=
n
2
(
n
2
+
2
n
+
1
)
=
n
2
(
n
+
1
)
2
{\displaystyle {\begin{aligned}4\sum _{k=1}^{n}k^{3}&=(n+1)^{4}-1-6\cdot {\frac {1}{6}}n(n+1)(2n+1)-4\cdot {\frac {1}{2}}n(n+1)-n\\&=(n^{4}+4n^{3}+6n^{2}+4n)-(2n^{3}+3n^{2}+n)-2(n^{2}+n)-n\\&=n^{4}+2n^{3}+n^{2}\\&=n^{2}(n^{2}+2n+1)\\&=n^{2}(n+1)^{2}\end{aligned}}}
なので、
∑
k
=
1
n
k
3
=
1
4
n
2
(
n
+
1
)
2
=
{
1
2
n
(
n
+
1
)
}
2
{\displaystyle \sum _{k=1}^{n}k^{3}={\frac {1}{4}}n^{2}(n+1)^{2}=\left\{{\frac {1}{2}}n(n+1)\right\}^{2}}
[ 6]
演習問題
∑
k
=
1
n
(
k
2
+
3
k
−
2
)
{\displaystyle \sum _{k=1}^{n}(k^{2}+3k-2)}
∑
k
=
1
n
2
k
{\displaystyle \sum _{k=1}^{n}2^{k}}
数列
{
a
n
}
{\displaystyle \{a_{n}\}}
b
n
=
a
n
+
1
−
a
n
{\displaystyle b_{n}=a_{n+1}-a_{n}}
で与えられる数列
{
b
n
}
{\displaystyle \{b_{n}\}}
{
a
n
}
{\displaystyle \{a_{n}\}}
階差数列 という。
{
a
n
}
{\displaystyle \{a_{n}\}}
{
b
n
}
{\displaystyle \{b_{n}\}}
a
1
{\displaystyle a_{1}}
{
a
n
}
{\displaystyle \{a_{n}\}}
階差数列の定義から
b
1
=
a
2
−
a
1
{\displaystyle b_{1}=a_{2}-a_{1}}
b
2
=
a
3
−
a
2
{\displaystyle b_{2}=a_{3}-a_{2}}
b
3
=
a
4
−
a
3
{\displaystyle b_{3}=a_{4}-a_{3}}
⋮
{\displaystyle \vdots }
b
n
−
1
=
a
n
−
a
n
−
1
{\displaystyle b_{n-1}=a_{n}-a_{n-1}}
である。
それぞれの式を足し合わせれば
a
n
−
a
1
=
∑
k
=
1
n
−
1
b
k
{\displaystyle a_{n}-a_{1}=\sum _{k=1}^{n-1}b_{k}}
つまり
a
n
=
a
1
+
∑
k
=
1
n
−
1
b
k
(
n
≥
2
)
{\displaystyle a_{n}=a_{1}+\sum _{k=1}^{n-1}b_{k}\quad (n\geq 2)}
を得る。
解答
a
1
=
3
{\displaystyle a_{1}=3}
a
2
=
b
1
+
a
1
=
7
{\displaystyle a_{2}=b_{1}+a_{1}=7}
a
3
=
b
2
+
a
2
=
13
{\displaystyle a_{3}=b_{2}+a_{2}=13}
a
4
=
b
3
+
a
3
=
21
{\displaystyle a_{4}=b_{3}+a_{3}=21}
である。
{
b
n
}
{\displaystyle \{b_{n}\}}
{
a
n
}
{\displaystyle \{a_{n}\}}
a
n
=
a
1
+
∑
k
=
1
n
−
1
b
k
{\displaystyle a_{n}=a_{1}+\sum _{k=1}^{n-1}b_{k}}
であることを思いだそう。
これを元に計算すれば、
n
≧
2
{\displaystyle n\geqq 2}
a
n
=
3
+
∑
k
=
1
n
−
1
(
2
k
+
2
)
=
3
+
(
n
−
1
)
n
+
2
(
n
−
1
)
=
n
2
+
n
+
1
{\displaystyle a_{n}=3+\sum _{k=1}^{n-1}(2k+2)=3+(n-1)n+2(n-1)=n^{2}+n+1}
である。
a
1
=
3
{\displaystyle a_{1}=3}
n
=
1
{\displaystyle n=1}
自然数 1, 2, 3, 4, 5, ... は無限に存在するので、任意の自然数に関しての命題を証明するとき、1つ1つの自然数を列挙していくことは不可能である。そこで、ここでは任意の自然数に関して成り立つ命題を有限の手順で証明する方法を考える。
自然数
n
{\displaystyle n}
P
(
n
)
{\displaystyle P(n)}
[ 8]
任意の自然数 k について
P
(
k
)
⟹
P
(
k
+
1
)
{\displaystyle P(k)\Longrightarrow P(k+1)}
P
(
1
)
{\displaystyle P(1)}
2. の条件より n = 1 について P は真であるから、1. の条件より n + 1 = 1 + 1 = 2 についても P は真である。これより n = 2 について P は真であるから、n + 1 = 2 + 1 = 3 についても P が真であることがいえ、以下同様にすべての自然数に対して P は真であると結論できる。
このような証明法を数学的帰納法 （mathematical induction）という。
数学的帰納法を用いて
∑
k
=
1
n
k
=
n
(
n
+
1
)
2
{\displaystyle \sum _{k=1}^{n}k={\frac {n(n+1)}{2}}}
を導出する。まずn=1のとき、
(
lhs
)
=
1
{\displaystyle ({\textrm {lhs}})=1}
(lhsは左辺の意味。)
,そして
(
rhs
)
=
1
(
1
+
1
)
2
=
1
{\displaystyle {\begin{matrix}({\textrm {rhs}})={\frac {1(1+1)}{2}}\\=1\end{matrix}}}
(rhsは右辺の意味。)
となり、確かに正しいことが分かる。次にn = lのときこのことが正しいと仮定する。このとき、
∑
k
=
1
l
+
1
k
=
∑
k
=
1
l
k
+
(
l
+
1
)
=
l
(
l
+
1
)
2
+
(
l
+
1
)
=
(
l
+
1
)
(
l
2
+
1
)
=
1
2
(
l
+
1
)
(
l
+
2
)
=
1
2
(
l
+
1
)
{
(
l
+
1
)
+
1
}
{\displaystyle {\begin{matrix}\sum _{k=1}^{l+1}k=\sum _{k=1}^{l}k~+(l+1)\\={\frac {l(l+1)}{2}}+(l+1)\\=(l+1)({\frac {l}{2}}+1)\\={\frac {1}{2}}(l+1)(l+2)\\={\frac {1}{2}}(l+1)\{(l+1)+1\}\end{matrix}}}
となり、n = l+1 のときにも、この式が正しいことが示された。よって数学的帰納法より、この式は1以上の全てのnについて成立する。
フィボナッチ数列 は
1
,
1
,
2
,
3
,
5
,
8
,
13
,
21
,
⋯
{\displaystyle 1,1,2,3,5,8,13,21,\cdots }
フィボナッチ数列の漸化式
a
1
=
1
{\displaystyle a_{1}=1}
a
2
=
1
{\displaystyle a_{2}=1}
a
n
+
2
=
a
n
+
1
+
a
n
{\displaystyle a_{n+2}=a_{n+1}+a_{n}}
は隣接三項間漸化式であるが、
a
n
+
2
−
a
n
+
1
−
a
n
=
0
{\displaystyle a_{n+2}-a_{n+1}-a_{n}=0}
x
2
−
x
−
1
=
0
{\displaystyle x^{2}-x-1=0}
である。これを解くと、
α
=
1
+
5
2
{\displaystyle \alpha ={\frac {1+{\sqrt {5}}}{2}}}
黄金比 φ として知られる）
β
=
1
−
5
2
{\displaystyle \beta ={\frac {1-{\sqrt {5}}}{2}}}
公比 β の等比数列の一般項に初項
a
1
=
1
,
a
2
=
1
{\displaystyle a_{1}=1,a_{2}=1}
a
n
+
1
−
α
a
n
=
(
a
2
−
α
a
1
)
β
n
−
1
a
n
+
1
−
α
a
n
=
(
1
−
α
)
β
n
−
1
a
n
+
1
−
α
a
n
=
β
n
{\displaystyle {\begin{array}{lcl}a_{n+1}-\alpha a_{n}&=&(a_{2}-\alpha a_{1})\beta ^{n-1}\\a_{n+1}-\alpha a_{n}&=&(1-\alpha )\beta ^{n-1}\\a_{n+1}-\alpha a_{n}&=&\beta ^{n}\end{array}}}
ただし α + β = 1 より 1 - α = β という関係を使った。これは α と β を入れ換えても成り立つため、次の連立方程式が得られる。
{
a
n
+
1
−
β
a
n
=
α
n
a
n
+
1
−
α
a
n
=
β
n
{\displaystyle {\begin{cases}a_{n+1}-\beta a_{n}&=\alpha ^{n}\\a_{n+1}-\alpha a_{n}&=\beta ^{n}\\\end{cases}}}
辺々を引いて
a
n
{\displaystyle a_{n}}
α
a
n
−
β
a
n
=
α
n
−
β
n
(
α
−
β
)
a
n
=
α
n
−
β
n
a
n
=
1
α
−
β
(
α
n
−
β
n
)
{\displaystyle {\begin{array}{lcl}\alpha a_{n}-\beta a_{n}&=&\alpha ^{n}-\beta ^{n}\\(\alpha -\beta )a_{n}&=&\alpha ^{n}-\beta ^{n}\\a_{n}&=&{\frac {1}{\alpha -\beta }}(\alpha ^{n}-\beta ^{n})\end{array}}}
ここで
α
−
β
=
5
{\displaystyle \alpha -\beta ={\sqrt {5}}}
a
n
=
1
5
{
(
1
+
5
2
)
n
−
(
1
−
5
2
)
n
}
{\displaystyle a_{n}={\frac {1}{\sqrt {5}}}\left\{\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right\}}
これはフィボナッチ数列の一般項を求める公式（ビネ の公式、Binet's formula）として知られている。
^ 二番目の式は
n
2
+
(
n
−
1
)
(
n
−
2
)
(
n
−
3
)
(
n
−
4
)
(
n
−
5
)
{\displaystyle n^{2}+(n-1)(n-2)(n-3)(n-4)(n-5)}
^
S
n
=
a
1
+
a
1
⋅
1
+
⋯
+
a
1
⋅
1
n
−
1
=
n
a
1
{\displaystyle S_{n}=a_{1}+a_{1}\cdot 1+\cdots +a_{1}\cdot 1^{n-1}=na_{1}}
^ 変数
k
{\displaystyle k}
i
{\displaystyle i}
l
{\displaystyle l}
∑
i
=
m
n
a
i
{\displaystyle \sum _{i=m}^{n}a_{i}}
∑
l
=
m
n
a
l
{\displaystyle \sum _{l=m}^{n}a_{l}}
a
m
+
⋯
+
a
n
{\displaystyle a_{m}+\cdots +a_{n}}
i
,
j
,
k
,
n
{\displaystyle i,j,k,n}
^ 複素数について既に学んでいる読者は複素数としてもよい
^ この式変形は足し算の順序を変えただけである。
^ これは 1 から n までの自然数の和を2乗したものになっている。
^ この式は
a
n
+
1
=
p
a
n
+
q
{\displaystyle a_{n+1}=pa_{n}+q}
a
n
+
1
,
a
n
{\displaystyle a_{n+1},a_{n}}
c
{\displaystyle c}
^ つまり、
P
(
n
)
{\displaystyle P(n)}
P
(
1
)
,
P
(
2
)
,
P
(
3
)
,
⋯
{\displaystyle P(1),P(2),P(3),\cdots }
k
{\displaystyle k}
P
(
k
)
{\displaystyle P(k)}
P
(
k
)
{\displaystyle P(k)}
P
(
n
)
{\displaystyle P(n)}
n
>
2
{\displaystyle n>2}
P
(
1
)
,
P
(
2
)
{\displaystyle P(1),P(2)}
1
>
2
{\displaystyle 1>2}
2
>
2
{\displaystyle 2>2}
P
(
m
)
{\displaystyle P(m)}
