漸化式

一意性：$(a_n)$、$(a'_n)$ がともに解で初期値が等しいとする。$n$ についての強い帰納法（数学的帰納法 の記事の定理「強い帰納法」）で $a_n=a'_n$ を示す。$n< k$ なら初期値が等しい。$n\ge k$ で、$m< n$ のすべてで $a_m=a'_m$ なら、$a_n=F_n(a_{n-1},\dots,a_{n-k})=F_n(a'_{n-1},\dots,a'_{n-k})=a'_n$ である。
存在：$N\ge k-1$ について、長さ $N+1$ の列 $(a_0,\dots,a_N)$ で、$a_i=b_i$（$i< k$）かつ $k\le n\le N$ で $a_n=F_n(a_{n-1},\dots,a_{n-k})$ を満たすもの（長さ $N+1$ の部分解と呼ぶ）が存在することを $N$ に関する帰納法で示す。$N=k-1$ では $(b_0,\dots,b_{k-1})$ がそうである。長さ $N+1$ の部分解 $(a_0,\dots,a_N)$ があれば、$a_{N+1}:=F_{N+1}(a_N,\dots,a_{N+1-k})$ を付け加えたものは長さ $N+2$ の部分解である。一意性の議論と同じ帰納法により、長さの違う部分解どうしも共通の番号では値が一致する。そこで各 $n$ について、長さ $n+1$ 以上の任意の部分解の $n$ 番目の値を $a_n$ と定めると、$(a_n)_{n\ge0}$ は初期値 $b_i$ をもち、各 $n\ge k$ で漸化式を満たす（長さ $n+1$ の部分解の中で成り立っているから）。$\square$

1：$p=rp+c$ なので、漸化式から $p=rp+c$ を引くと $a_n-p=r(a_{n-1}-p)$ である。$n$ についての帰納法で $a_n-p=r^n(a_0-p)$ が従う（$n=0$ では両辺が等しく、$n-1$ で成り立てば $a_n-p=r\cdot r^{n-1}(a_0-p)$）。
2：$a_n-a_{n-1}=c$ なので、帰納法で $a_n=a_0+nc$ である。$\square$

$(a_n),(b_n)\in V$、$\lambda\in\mathbb{C}$ なら、$n\ge k$ で $a_n+\lambda b_n=\sum_{i=1}^kc_i(a_{n-i}+\lambda b_{n-i})$ なので $(a_n+\lambda b_n)\in V$ であり、零数列も $V$ に属する。よって $V$ は部分空間である。$\Phi$ は明らかに線形写像である。prop-rec-unique（$X=\mathbb{C}$、$F_n(y_1,\dots,y_k)=c_1y_1+\cdots+c_ky_k$）により、任意の初期値に対して解がただ 1 つあるので、$\Phi$ は全単射である。よって $\Phi$ は線形同型であり、$\dim V=\dim\mathbb{C}^k=k$ である（基底と次元）。$\square$

$(E-\alpha)\bigl(p(n)\beta^n\bigr)=p(n+1)\beta^{n+1}-\alpha p(n)\beta^n=\bigl(\beta p(n+1)-\alpha p(n)\bigr)\beta^n$ なので、$q(n):=\beta p(n+1)-\alpha p(n)$ である。$p$ の最高次の係数を $\ell\neq0$ とする。
1：$\beta=\alpha$ なら $q(n)=\alpha\bigl(p(n+1)-p(n)\bigr)$ である。$d=0$ なら $p$ は定数なので $q=0$ である。$d\ge1$ なら、二項定理により $(n+1)^d-n^d$ は $n^{d-1}$ の係数が $d$ の $d-1$ 次式であり、$j< d$ の $(n+1)^j-n^j$ は $j-1$ 次以下なので、$p(n+1)-p(n)$ は $n^{d-1}$ の係数が $d\ell\neq0$ の $d-1$ 次式である。$\alpha\neq0$ なので $q$ も $d-1$ 次である。
2：$q$ の $n^d$ の係数は $\beta\ell-\alpha\ell=(\beta-\alpha)\ell\neq0$ であり、$q$ の次数は $d$ 以下なので、ちょうど $d$ 次である。$\square$

代数学の基本定理により $\chi$ は複素数の範囲でこのように因数分解される。$\chi(0)=-c_k\neq0$ なので、どの $\alpha_j$ も $0$ でない。
(i) 各数列が解であること：$0\le s< m_j$ とする。lem-rec-shift の 1 を繰り返し使うと、$(E-\alpha_j)$ を 1 回施すごとに多項式の次数が 1 ずつ下がり、$s+1$ 回で $0$ になる。$s+1\le m_j$ なので $(E-\alpha_j)^{m_j}(n^s\alpha_j^n)=0$ である。$\chi(E)=\Bigl(\prod_{i\neq j}(E-\alpha_i)^{m_i}\Bigr)(E-\alpha_j)^{m_j}$ なので $\chi(E)(n^s\alpha_j^n)=0$、すなわち $n^s\alpha_j^n\in V$ である。
(ii) 線形独立であること：多項式 $p_j$（$\deg p_j< m_j$、または $p_j=0$）について、すべての $n\ge0$ で $\sum_{j=1}^rp_j(n)\alpha_j^n=0$ ならば、すべての $p_j$ が $0$ であることを $r$ に関する帰納法で示す。$r=1$ なら $p_1(n)\alpha_1^n=0$ と $\alpha_1\neq0$ から、すべての $n\ge0$ で $p_1(n)=0$ である。$0$ でない多項式の根は有限個なので $p_1=0$ である。$r\ge2$ のとき、両辺に $(E-\alpha_r)^{m_r}$ を施す。(i) と同じ理由で $j=r$ の項は $0$ になる。$j< r$ の項は、lem-rec-shift の 2 を $m_r$ 回使うと $q_j(n)\alpha_j^n$ の形になり、$p_j\neq0$ なら $q_j$ は $p_j$ と同じ次数の $0$ でない多項式、$p_j=0$ なら $q_j=0$ である。よってすべての $n$ で $\sum_{j< r}q_j(n)\alpha_j^n=0$ であり、帰納法の仮定から $q_j=0$、したがって $p_j=0$（$j< r$）である。残る $p_r(n)\alpha_r^n=0$ から、$r=1$ の場合と同様に $p_r=0$ である。
(iii) (i)(ii) により、$V$ の中に線形独立な $k$ 個の元がある。prop-rec-solution-space により $\dim V=k$ なので、これらは $V$ の基底である（基底と次元）。$\square$

$(a_n)$ が非斉次の解なら、$n\ge k$ で $a_n-b_n=\sum_{i=1}^kc_i(a_{n-i}-b_{n-i})$（$f(n)$ が打ち消し合う）なので $(a_n-b_n)\in V$ である。逆に $(h_n)\in V$ なら、$b_n+h_n=\sum_ic_i(b_{n-i}+h_{n-i})+f(n)$ なので $(b_n+h_n)$ は非斉次の解である。$\square$