当ＨＰがいつもお世話になっているＨＮ「空舟」さんからの出題です。
（平成２６年９月９日付け）
久しぶりに問題を出してみます。オンライン整数列大辞典「A001835」の数列
a[0]=a[1]=1、 a[k+2]=4*a[k+1]-a[k]
に対して、a[(3k+1)/2] は 3でちょうどk回だけ割り切れることを示してください
（これは私が、3x-2 が平方数になるような整数 ｘ が、1、3に限ることを示すのに使った命題です）
（コメント） 数列を実際に書き上げてみると、
１，１，３，１１，４１，１５３，５７１，２１３１，７９５３，２９６８１，１１０７７１，
４１３４０３，１５４２８４１，５７５７９６１，２１４８９００３，８０１９８０５１，・・・
確かに数列は、「a[(3k+1)/2] は 3でちょうどk回だけ割り切れる」となっているように見える。
（例） ２１４８９００３＝３*７１６３００１＝３*３*２３８７６６７＝３*３*３*７９５８８９
７＋９＋５＋８＋８＋９＝４６ なので、７９５８８９は３で割り切れない。
ＧＡＩ さんが考察されました。（平成２６年９月９日付け）
漸化式から、 a[n]=((3+
)^(2*n-1)+(3-)^(2*n-1))/6^nこれから、
a[(3^n+1)/2]=((3+
)^(3^n)+(3-)^(3^n))/(
^(3^n+1))= 3^3^n*((
+
)/6)^3^n+((-)/6)^3^n]/=3^n*{3^(3^n-n)*(((
+)/6)^3^n+((-)/6)^3^n)/}から、3^n の倍数
※ f[n]=3^(3^n-n)*(((
+)/6)^3^n+((-)/6)^3^n)/が整数となることを数学的帰納法で証明できればと挑戦していましたが挫折しました。
ただし、コンピュータでずるしたら、「f[n]は整数」を返してきます。
空舟さんからのコメントです。（平成２６年９月１３日付け）
私が用意した証明を紹介します。現れる関係式の証明は省略します。
a[n]と同じ漸化式が成り立ち、初項が異なる別の数列 p[n]、q[n] を使う。
(p[0]=1,p[1]=2,q[0]=0,q[1]=1) p[n] 、q[n] について、次の関係式がある。
a[k] = q[k]-q[k-1] ・・・(*) 、q[2k+1] = q[k+1]^2-q[k]^2
q[k]を3で割った余りは、「0,1,1,0,2,2」を繰り返すことから、(q[k+1]+q[k])が3で割り切れるこ
とは無いので次を得る。
q[k+1]-q[k]≡0 (mod 3^c) ⇔ q[2k+1]≡0 (mod 3^c)・・・(**)
次の関係式がある。 q[3k] = 3q[k]*(p[k]^2+q[k]^2)
p[k]を3で割った余りは、「1,2,1,2,1,2」と繰り返すことから、p[k]^2+q[k]^2が3の倍数になるこ
とは無いので次を得る。
q[3k]はq[k]より3で1回多く割り切れる。
従って、次を得る。
q[3^k]は3でちょうどk回割り切れる・・・(***)
以上を使えば、次のようにして結論が示される。
a[(3^k+1)/2] が 3でc回割り切れる
⇔ q[(3^k+1)/2]-q[(3^k-1)/2]≡0 (mod 3^c) [(*)より]
⇔ q[3^k]≡0 (mod 3^c) [(**)より]
⇔ c≦k [(***)より]
DD++さんからのコメントです。（平成２６年９月１３日付け）
思っていたのと全然違った……ということで、私の考えていた方法も投稿します。
b[-1]=1、 b[0]=
/3、 b[1]=1、 以下、 b[n+2] = b[n+1] - b[n]で数列 {b[n]} を定義します。
α=(
+)/2 と定義すると、α+α^(-1) = なので、b[n+2] - α b[n+1] = α^(-1) ( b[n+1] - α b[n] ) より
b[n+1] - α b[n] = α^(-n) (1-
/3 α) = -α^(-n) /また、 b[n+2] - α^(-1) b[n+1] = α ( b[n+1] - α^(-1) b[n] ) より、
b[n+1] - α^(-1) b[n] = α^n (1-
/3 α^(-1)) = α^n /よって、 ( α - α^(-1) ) b[n] = ( α^n + α^(-n) )/
より、b[n] = ( α^n + α^(-n) ) /
であり、恒等式 α^3n + α^(-3n) = ( α^n + α^(-n) )^3 - 3( α^n + α^(-n) ) から
b[3n] = 6 b[n]^3 - 3 b[n]
という関係があることがわかります。これを、 b[3n] = 3 b[n] ( 2 b[n]^2 - 1 ) と変形すると、
b[n] が整数ならば、b[n]^2 ≡ 0,1 (mod3) より、 2 b[n]^2 - 1 ≡ 1,2 (mod3)
なので、b[n] が整数である場合にカッコ内は3の倍数でない整数となります。
b[3^0] = b[1] = 1 は、3で0回割り切れるが1回は割り切れない整数で、
よって、 b[3^1] は3で1回割り切れるが2回は割り切れない整数、
以下帰納的に、 b[3^k] は3でk回割り切れるがk+1回は割り切れない整数です。
一方で、 b[n+4] + b[n] =
b[n+3] - b[n+2] + b[n+1] - b[n+2]=
( b[n+3] + b[n+1] ) - 2 b[n+2]=
( b[n+2] ) - 2 b[n+2]= 4 b[n+2]
これと、 b[-1]=1, b[1]=1 より、b[-1] を第0項として奇数番目だけ拾って新しい数列を作る
と、それは {a[n]} に一致します。
このとき、 a[(3^k+1)/2] は b[3^k] と一致するので、これは、3でk回割り切れるがk+1回は
割り切れない整数です。
もう少し真面目に帰納法を使っておいて転換法と組み合わせると、
「nが3でちょうどk回割り切れる奇数 ⇔ b[n]が3でちょうどk回割り切れる整数」
まで証明できると思います。しかし、3^n-2 が n>3 で平方数にならない証明がどうするのか見
当つきません。大変気になっているのですが、どのようにするのです？
ＧＡＩ さんからのコメントです。（平成２６年９月１３日付け）
証明された部分で本質的には関係ないかも知れませんが、「q[3k] = 3q[k]*(p[k]^2+q[k]^2)」
は、「q[3k+1] = 3q[k]*(p[k]^2+q[k]^2)」となりませんか？コンピュータで確認しているときに気
になったものですから・・・。
空舟さんからのコメントです。（平成２６年９月１４日付け）
DD++さん、a[n]がそのようなb[n]の奇数項目になっている構造は気がつきませんでした。な
るほどです．．．。実は、今回取り上げた数列a[n]は、3x2-2が平方数になるような正の整数
ｘをすべて与えます。・・・★
3^N-2 が平方数になるには4で割った余りの考察より ｎ は奇数と言えるので、x=3^{(N-1)/2}
として★のうちに含まれるはずです。
a[n]が3^kで割り切れる最小のｎは、ｎ=(3^k+1)/2 と示されたので、a[(3^k+1)/2]/3^k ＞ 1 を
示せば、a[n]が3^kを与えないことが言えます。
a[n]の値を適当に見積もると、 a[k]≧3^(k-1) が言えますから、
a[(3^k+1)/2]/3^k ≧ 3^{(3^k-2k-1)/2}
が言えます。k≧2 に対してはこれが1より大きいことが言えます。
ところで、★は次のようにして示すことができます。
3x^2-2 = w^2 ・・・（１） （これは、 (w+x√3)(w-x√3) = -2 と書けます）
(w,x)=(a,b) が、（１）の正整数解（a,b＞0）であると仮定する。
(a+b√3)/(2+√3)=(a+b√3)(2-√3)=c+d√3
とおくことで、(w,x)=(c,d) すなわち (w,x)=(2a-3b,-a+2b) も（１）の解になる。これを繰り返すと、
w+x√3の実数としての大きさは0に近づくことから、a,bは共に正だが c,dの少なくとも片方が
正でない時がいつか来る。
[1] a,b＞0, 3b^2-2=a^2, c=2a-3b≦0 の検討
-6 = 3a^2-9b^2 ≧ 3a^2-4a^2 = -a^2 よって、a=1,2 が候補となるが、b=√(a^2+2) が整数
になるのはa=1のみである。
[2] a,b＞0, 3b^2-2=a^2, d=-a+2b≦0 の検討
-2 = a^2-3b^2 ≧ 4b^2-3b^2 = b^2 これが成り立つことはない
すなわち、いつか来たるときに a=1, b=1 となることから、最初の(w,x)が、
w+x√3=(1+√3)(2+√3)^n
の形であったことが言えて、そのxを与える数列を求めると今回の数列を得ます
また、ＧＡＩさんからの問いかけについて、p[0]=1, p[1]=2 から、
q[0]=0, q[1]=1, q[2]=4, q[3]=15, q[4]=56
で k=1 を検討してみると元の式で合ってると思います。
DD++さんからのコメントです。（平成２６年９月１４日付け）
なるほど！ペル方程式擬きの解を並べた数列だったのですね！ひょっとしてこれって、他
の数値でも、最初に偶数乗が排除されれば似たようなことはできるのでしょうかね？7^n-3
とか 11^n-2 とか、そういったもの。私も手元で考えてみることにします。