 | 2015/02/21(Sat) 22:11:47 編集(投稿者)
(a[1], b[1]) = (2, 1) = 1です。
任意の自然数nに対して(a[n], b[n]) = 1と予想して、これを証明します。
2つの自然数u, vの最大公約数をgとすると、ある整数x, yが存在してg = xu+yvと表せます。
また、xu+yvと表せる整数はgの倍数となります。
# 上記は自明ではないですが、その証明をここに書くと長くなりますので省略します。
# 整数論の本などを参考にしてください。
ある整数x, yが存在して、x*a[n]+y*b[n] = 1だったと仮定すれば、
(a[n], b[n])は1の約数となりますので、(a[n], b[n]) = 1です。
a[n+1] = 2a[n]+3b[n], b[n+1] = a[n]+2b[n]
より、
2a[n+1]-3b[n+1] = 2(2a[n]+3b[n])-3(a[n]+2b[n]) = a[n]
-a[n+1]+2b[n+1] = -(2a[n]+3b[n])+2(a[n]+2b[n]) = b[n]
よって、
1 = x*a[n]+y*b[n] = x*(2a[n+1]-3b[n+1])+y*(-a[n+1]+2b[n+1]) = (2x-y)a[n+1]+(-3x+2y)b[n+1]
上記は
(a[n+1], b[n+1]) = 1
であることを表しています。
以上から、数学的帰納法により任意の自然数nに対して(a[n], b[n]) = 1です。
|