京都大学 理系 2013年度 第2問 解説
問題編
問題
$N$ を $2$ 以上の自然数とし、 $a_n\ (n=1,2,\ldots)$ を次の性質(i), (ii) をみたす数列とする。
(i) $a_1=2^N-3$,
(ii) $n=1,2,\ldots$ に対して、
$a_n$ が偶数のとき $a_{n+1}=\dfrac{a_n}{2}$, $a_n$ が奇数のとき $a_{n+1}=\dfrac{a_n-1}{2}$ 。このときどのような自然数 $M$ に対しても\[ \sum_{n=1}^M a_n\leqq 2^{N+1}-N-5 \]が成り立つことを示せ。
考え方
問題文を読んだだけでは、どういう数列なのか、不等式の右辺がどういうものなのかがわかりにくいです。こういう場合は、まず、具体例で実験してみましょう。
$N=2,3,4,5$ くらいなら、計算しても、そんなに時間はかからないはずです。実際の値を見てみると、この数列の性質がわかってきます。これらをもとに、一般的な形でどういう式変形ができるかを考えていくといいでしょう。
解答編
問題
$N$ を $2$ 以上の自然数とし、 $a_n\ (n=1,2,\ldots)$ を次の性質(i), (ii) をみたす数列とする。
(i) $a_1=2^N-3$,
(ii) $n=1,2,\ldots$ に対して、
$a_n$ が偶数のとき $a_{n+1}=\dfrac{a_n}{2}$, $a_n$ が奇数のとき $a_{n+1}=\dfrac{a_n-1}{2}$ 。このときどのような自然数 $M$ に対しても\[ \sum_{n=1}^M a_n\leqq 2^{N+1}-N-5 \]が成り立つことを示せ。
解答
$N=2$ のとき、 $a_1=1$ で、 $n\geqq 2$ のときは $a_n=0$ となる。よって、このとき、\[ \sum_{n=1}^M a_n=1 \]であり、 $2^{2+1}-2-5=1$ なので、\[ \sum_{n=1}^M a_n\leqq 2^{N+1}-N-5 \]が成り立つ。
以下では、 $N\geqq 3$ とする。
$a_1=2^N-3$ は奇数なので、
\begin{eqnarray}
a_2=\frac{2^N-3-1}{2}=2^{N-1}-2
\end{eqnarray}である。 $N\geqq 3$ のとき、これは偶数であるから
\begin{eqnarray}
a_3=\frac{2^{N-1}-2}{2}=2^{N-2}-1
\end{eqnarray}である。
以下では、 $3\leqq n\leqq N+1$ のときに $a_n=2^{N-n+1}-1$ となることを示す。
(ア) $n=3$ のとき
先ほど示したように $a_3=2^{N-2}-1=2^{N-3+1}-1$ なので、たしかに成り立つ。
(イ) $n=k$ $(3\leqq k\leqq N)$ のとき、 $a_k=2^{N-k+1}-1$ とする
このとき、 $N-k+1$ は正の整数なので、 $a_k$ は奇数である。よって、
\begin{eqnarray}
a_{k+1}
&=&
\frac{2^{N-k+1}-1-1}{2}=2^{N-(k+1)+1}-1
\end{eqnarray}となり、 $n=k+1$ のときも $a_n=2^{N-n+1}-1$ が成り立つ。
(ア)(イ)より、 $3\leqq n\leqq N+1$ のときに $a_n=2^{N-n+1}-1$ となる。
これより、 $a_N=2^1-1=1$ であるから、 $a_{N+1}=\dfrac{1-1}{2}=0$ となる。よって、 $n\geqq N+1$ のときには $a_n=0$ となる。
以上から、特に、 $a_n\geqq 0$ がわかるので、
\begin{eqnarray}
& &
\sum_{n=1}^M a_n \\[5pt]
&\leqq &
\sum_{n=1}^{N} a_n \\[5pt]
&=&
(2^N-3)+(2^{N-1}-2)+\sum_{n=3}^{N} (2^{N-n+1}-1) \\[5pt]
&=&
-5+2^N+2^{N-1}+\sum_{n=1}^{N-2} (2^n-1) \\[5pt]
&=&
-5-(N-2)+\sum_{n=1}^{N} 2^n \\[5pt]
&=&
-N-3+\frac{2(2^N-1)}{2-1} \\[5pt]
&=&
2^{N+1}-N-5
\end{eqnarray}となる。
以上から、 $N$ が $2$ 以上の自然数のとき、どのような自然数 $M$ に対しても\[ \sum_{n=1}^M a_n\leqq 2^{N+1}-N-5 \]が成り立つ。
（終）
解説
途中の計算で出てくる\[\sum_{n=3}^{N} (2^{N-n+1}-1)\]は、指数部分に注目すると、 $N-2$ から $1$ まで順番に減っていくので、\[\sum_{n=1}^{N-2} (2^n-1)\]と一致することがわかります。
