実践演習 極限・微分積分系

最大公約数についての数列【2012年度 東京都立大学】

問題はこちら(画像をクリックするとPDFファイルで開きます。)

最大公約数についての数列を考え、和などを考える問題です。

標準的なレベルの問題で、野球で例えるなら135km/h 真ん中ちょい高めのストレートって感じですかね。

要するに長打が狙える打ちごろの球なので、できれば打ち損じることなくはじき返してほしいですが、記述面で書きづらさを感じるかもしれません。

(以下ネタバレ注意)

 

+ クリック(タップ)して続きを読む

(1) について

最大公約数に迫る一つの大きな武器が

ユークリッドの互除法

です。

二つの整数 \(K\) ,  \(L\) の最大公約数を \(G (K \ , \ L)\) と表すことにします。

\(n^{2}+3=(n+1)(n-1)+4\)

ですから、

\(G(n^{2}+3 \ , \ n+1)=G(n+1 \ , \ 4)\)

が成り立ち、結局は

\(d_{n}=G(n+1 \ , \ 4)\)

ということになります。

特に \(d_{n}\) が 4 の約数であるということが言えるため、

\(d_{n}\) は \(1\) ,  \(2\) ,  \(4\) のいずれかである

ということが言えます。

(2) について

\(d_{n}\) がとり得る値の種類は分かりましたが、どのような規則性で \(1\) ,  \(2\) ,  \(4\) が現れるのかについては実験してみないと分かりません。

実験してみると

  • \(d_{1}=G(4 \ , \ 2)=2\)
  • \(d_{2}=G(7 \ , \ 3)=1\)
  • \(d_{3}=G(12 \ , \ 4)=4\)
  • \(d_{4}=G(19 \ , \ 5)=1\)
  • \(d_{5}=G(28 \ , \ 6)=2\)
  • \(d_{6}=G(39 \ , \ 7)=1\)
  • \(d_{7}=G(52 \ , \ 8)=4\)
  • \(d_{8}=G(67 \ , \ 9)=1\)
  • \(d_{9}=G(84 \ , \ 10)=2\)

となり、ここから

数列 \(\{d_{n}\}\) は \(2\) ,  \(1\) ,  \(4\) ,  \(1\)  の繰り返しである

ということが予想できます。

ひとまず、この周期性を認めれば

\(\displaystyle \sum_{n=1}^{610}d_{n}=\displaystyle \sum_{m=1}^{152}(d_{4m-3}+d_{4m-2}+d_{4m-1}+d_{4m})+d_{609}+d_{610}\)

ということになり、解決します。

周期性の証明について

方針1

\(n\) を \(4\) で割った余りで分類して

\(d_{4m-3}\) ,  \(d_{4m-2}\) ,  \(d_{4m-1}\) ,  \(d_{4m}\)

をそれぞれ求めてしまう。

方針2

\(d_{n+4}=d_{n}\) を示す。

という2路線あると思います。

特に方針2で進めようとした場合、ユークリッドの互除法についてのしっかりした理解が求められます。

このあたりは【戦略2】の中で触れていますが、説明については少し簡略化してあります。

これについては以下の

参考ユークリッドの互除法【原理の証明とイメージ】【2005年度 広島市立大学】

問題はこちら(画像をクリックするとPDFファイルで開きます。) 2つの正整数の最大公約数を求めるときに用いられる「ユークリッドの互除法」と呼ばれるアルゴリズムについて、原理と証明を考えてみます。 古典 ...

続きを見る

でしっかり述べていますので、【戦略2】を読んで「ん?なんで?」と思った場合、そちらを参考にしてください。

(3) について

チェザロ平均と呼ばれる初項から第 \(n\) 項までの平均の極限を考える問題です。

これについても2路線の方針が考えられます。

方針1

\(S_{n}=\displaystyle \sum_{k=1}^{n}d_{k}\) とおき

\(n\) を \(4\) で割った余りで分類して

\(S_{4M}\) ,  \(S_{4M+1}\) ,  \(S_{4M+2}\) ,  \(S_{4M+3}\)

をそれぞれ求める。

これは(2) の方針1の延長のような考え方です。

また

方針2

不等号を繋いで(評価して)

はさみうちの原理で仕留める

ということも考えられます。

\(S_{n}\) をバシッと等号で繋ごうと思うと、\(4\)で割った余りで分類した場合分けが必要になり、それを嫌ったわけです。

まとめ

ある程度手を動かせば要領は掴みやすいでしょう。

ただ、掴んだ要領を記述、表現、説明する部分で個人差が出やすいと思います。

【解答】は一つの参考例にしてください。

解答はコチラ

-実践演習, 極限・微分積分系
-, ,

© 2022 MathClinic