f(n)が○○の倍数であることを示す

概要

この記事では以下のような問題を機械的に解く方法を、$4$つの問題を通して紹介します。

発想

正の整数$n$に対して
$$\begin{array}{rl}f(0)+\sum _{k=1}^n(f(k)-f(k-1))& =f(0)+(f(1)-f(0))+(f(2)-f(1))+\cdots +(f(n-1)-f(n-2))+(f(n)-f(n-1))\\ & =f(n)\end{array}$$
が成り立ちます。したがって、$f(0)$および$f(n)-f(n-1)$が$6$の倍数であることを示せば$f(n)$が$6$の倍数であると分かります。同様に、$n$が負である場合は
$$\begin{array}{rl}f(0)+\sum _{k=1}^{-n}-(f(1-k)-f(-k))& =f(0)-(f(0)-f(-1))-(f(-1)-f(-2))-\cdots -(f(2+n)-f(1+n))-(f(1+n)-f(n))\\ & =f(n)\end{array}$$
$f(n)-f(n-1)$が$6$の倍数であれば$n=1-k$の場合を考えることにより$-(f(1-k)-f(-k))$も$6$の倍数であると分かり、$f(0)$が$6$の倍数であることと併せて$f(n)$も$6$の倍数であると分かります。

問題1

$f(n)=2n^3-3n^2+7n$とおきます。まず、$f(0)=0$が$6$の倍数であることは簡単に分かります。また、
$$\begin{array}{rl}f(n)-f(n-1)& =2(n^3-(n-1{)}^3)-3(n^2-(n-1{)}^2)+7(n-(n-1))\\ & =(6n^2-6n+2)-(6n-3)+7=6n^2-12n+12\\ & =6(n^2-2n+2)\end{array}$$
であるため、正の整数$n$に対して
$$f(n)=f(0)+\sum _{k=1}^n(f(k)-f(k-1))$$
は$6$の倍数です。同様に負の整数$n$に対して、
$$f(n)=f(0)+\sum _{k=1}^{-n}-(f(1-k)-f(-k))$$
は$6$の倍数です。以上より、任意の整数$n$について$f(n)$は整数であることが示されました。

問題2

記述量を抑えるという観点では、階差数列は天から降ってきたものとして書くのがよいでしょう。

$f(n)=n^5-5n^3+4n$とおきます。$f(n)=f(-n)$なので、$0\leqq n$の場合について示せば十分です。まず、$g_1(n)=120(n-2)$とおくと$0$以上の任意の整数$n$について$g_1(n)$は$120$の倍数であり、

$$g_2(n)=120+\sum _{k=1}^n{g}_1(k)=120+120(\frac{n(n+1)}{2}-2n)=60n^2-180n+120$$

は$120$の倍数の和なので$120$の倍数です。また、

$$g_3(n)=\sum _{k=1}^n{g}_2(k)=60\cdot \frac{n(n+1)(2n+1)}{6}-180\cdot \frac{n(n+1)}{2}+120n=20n^3-60n^2+40n$$

は$120$の倍数の和なので$120$の倍数です。また、

$$\begin{array}{rl}{g}_4(n)& =\sum _{k=1}^n{g}_3(k)=20\cdot \frac{n^2(n+1{)}^2}{4}-60\cdot \frac{n(n+1)(2n+1)}{6}+40\cdot \frac{n(n+1)}{2}\\ & =5n^4-10n^3-5n^2+10n\end{array}$$

は$120$の倍数の和なので$120$の倍数です。また、

$$\begin{array}{rl}{g}_4(n)& =\sum _{k=1}^n{g}_3(k)=5\cdot \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}-10\cdot \frac{n^2(n+1{)}^2}{4}-5\cdot \frac{n(n+1)(2n+1)}{6}+10\cdot \frac{n(n+1)}{2}\\ & =\frac{n(n+1)(2n+1)(3n^2+3n-6)}{6}-\frac{n(n+1)(5n^2+5n)}{2}+\frac{10n(n+1)}{2}\\ & =\frac{n(n+1)((2n^3+3n^2-3n-2)-(5n^2+5n)+10)}{2}\\ & =n(n+1)(n^3-n^2-4n+4)=n^5-5n^3+4n=f(n)\end{array}$$

は$120$の倍数の和なので$120$の倍数です。以上で示したかった命題が得られました。

問題3

$a^{p-1}-1$が$p$の倍数であることを示せばよいですが、$a$が$p$と互いに素であることからこれは$a(a^{p-1}-1)=a^p-a$が$p$の倍数であることと同値です。以下、任意の整数$n$について$n^p-n$が$p$の倍数であることを示しますが、例によって例のごとく$0<n$の場合を示せば十分です。$f(n)={\displaystyle \sum _{k=1}^{p-1}{}_p{C}_k{n}^k}$とおきます。

$${}_p{C}_k=\frac{p!}{k!(p-k)!}(k=1,2,3,\dots ,p-1)$$

であり、分子が$p$の倍数であって分母が$p$の倍数でないので分数全体としては$p$の倍数です。したがって$f(n)$は$p$の倍数であることが分かりました。ここで、

$$\sum _{k=1}^{n-1}f(k)=\sum _{k=1}^{n-1}((k+1{)}^p-(k^p+1))=\sum _{k=1}^n(((k+1{)}^p-(k+1))-(k^p-k))=n^p-n$$

であるので$n^p-n$が$p$の倍数であることが示されました。

問題4

$k$に関する数学的帰納法を使います。まず、連続する$1$個の整数の積は整数であって任意の整数は$1$の倍数なので、$k=1$の場合は明らかです。
$k$を$2$以上の整数とし、「連続する$(k-1)$個の整数の積は$(k-1)!$の倍数である」が成り立つことを仮定し、「連続する$k$個の整数の積は$k!$の倍数である」が成り立つことを示します。$k$個の整数がすべて負の数である場合は各々を$-1$倍することで$k$個の整数がすべて正の数である場合に帰着できます。$k$個の整数に正の数とそうでない数が混在している場合、その中には必ず$0$が含まれるため積は$0$となり、$k!$の倍数であることが分かります。
したがって示すべきは、正の整数$n$について
$$f_k(n)=n(n+1)(n+2)\dots (n+k-2)(n+k-1)$$
が$k!$の倍数であることです。

$$\begin{array}{rl}\sum _{i=1}^{n}k{f}_{k-1}(i)& =\sum _{i=1}^{n}ki(i+1)(i+2)\dots (i+k-2)\\ & =\sum _{i=1}^{n}i(i+1)(i+2)\dots ((i+k-1)-(i-1))\\ & =\sum _{i=1}^n(i(i+1)(i+2)\dots (i+k-1)-(i-1)i(i+1)\dots (i+k-2))\\ & =\sum _{i=1}^n(f_k(i)-f_k(i-1))=f_k(n)-f(0)=f_k(n)\end{array}$$

仮定より$f_{k-1}(n)$は$(k-1)!$の倍数なので$k{f}_{k-1}(n)$は$k!$の倍数であり、したがって$f_k(n)$は$k!$の倍数です。以上で証明が完了しました。

あとがき

$f(n)$は多項式でなくてもこの方法は使えますが、たくさん書くのは面倒冗長なので書きませんでした。最後の問題がメインだったので本来はそれだけの記事でもよかったのですが。なお、前述の証明と同様の方法で
$$\begin{array}{r}\sum _{i_k=1}^n\sum _{i_{k-1}=1}^{i_k}\dots \sum _{i_3=1}^{i_4}\sum _{i_2=1}^{i_3}\sum _{i_1=1}^{i_2}1=\frac{n(n+1)(n+2)\dots (n+k-1)}{k!}\end{array}$$
が示せます。美しいですね。