4年に一度のスポーツの祭典 全競技速報中

α=a+b√k (a,bは有理数,kは正の実数)について a^n を簡易に計算できないか考えています。

C[n] = α^n = A[n] + B[n]√k としたときの数列 A[n],B[n] の一般項を求めることができないでしょうか?

次のようなことを考えてみましたが、上の問いの解決につながらないような気がしています。
インターネット検索をかけましたが、よい記事を見つけることができませんでした。
一般化は難しいということでしょうか?

■対称式の視点
β=a-b√k とおくと
F[n] = α^n + β^n : F[n+2] = (α+β) F[n+1] -αβ F[n]  : F[0] = 2
G[n] = α^n - β^n : G[n+2] = (α+β) G[n+1] -αβ G[n] : G[0] = 0
などの3項間漸化式が成り立ちます。

■2項定理を利用する?
(a+b√k)^n = Σ_[i=0]^[n] nCi a^(n-i) b^i (√k)^i

■x^nをx^2-(α+β)x+αβで割ったときの商をQ(x)とすると
x^n = ( x - α )( x - β ) Q(x) + (α^n - β^n)/(α-β) x - (β α^n - α β^n)/(α-β)

質問者からの補足コメント

  • はじめの
    >α=a+b√k (a,bは有理数,kは正の実数)について a^n を簡易に計算できないか考えています。

    α^n を簡易に計算できないか考えています。(あるふぁのn乗)
    の誤りでした。

      補足日時:2021/01/04 11:52
gooドクター

A 回答 (5件)

No.4 訂正



> No.1へのコメントについてです。

→ No.2 へのコメントについてです。

> else (aA[(n-1)/2] + kbB[(n-1)/2], aB[(n-1)/2] + bA[(n-1)/2])

→ else (aA[n-1] + kbB[n-1], aB[n-1] + bA[n-1])

でした。

 なお、x^n を最少回数の掛け算で計算するアルゴリズムをどっかで見た覚えがあるのだけれども、どうも見つからないんだよな。例えばx^30を計算するのに
  X2 = x × x
  X4 = X2 × X2
  X8 = X4 × X4
  X10 = X8 × X2
  X20 = X10 × X10
  x^30 = X20 × X10
のように、すでに計算した中間結果を再利用する。このやり方は
  (A[n+m],B[n+m]) = (A[n]A[m] + kB[n]B[m], A[n]B[m] + B[n]A[m])
を組み合わせるのにも、そのまま応用できるんですけどねー。
    • good
    • 0
この回答へのお礼

この手の計算は、一般項(私が理想とした”簡易な計算”)は見当たらず、漸化的・再帰的な方法で計算するしかないのかもしれませんね。もっとも、一般項は先の回答の中に表現されています。

また、No4,No5の回答から、「計算量」とは何か、ということについても思いを巡らせたところです。x^n を最少回数の掛け算で・・・からの記述も興味が湧きました。少し理解するのに時間がかかりましたが、
(A[n+m],B[n+m]) = (A[n]A[m] + kB[n]B[m], A[n]B[m] + B[n]A[m])
という式は、理解すると当たり前のように感じますが、それでも、なかなか美しいなぁ。また、これによって明らかに「計算量は減る」と実感しました。

回答ありがとうございました。

お礼日時:2021/01/05 20:00

No.1へのコメントについてです。



> Dixonの恒等式のように

ってのはちょっと思いつかない。とりあえず、「平方根は絶対嫌だという条件付きで計算量を減らす」という話にしてみると、漸化式
  (A[1],B[1]) = (a, b)
  (A[2n],B[2n]) = (A[n]^2 + kB[n]^2, 2A[n]B[n])
  (A[2n+1],B[2n+1]) = (aA[2n] + kbB[2n], aB[2n] + bA[2n])
を使うのが分かりやすいのではないか。再帰的アルゴリズムとして書くと
  (A[n],B[n]) = if n=1 then (a,b)
    else if nが偶数 then (A[n/2]^2 + kB[n/2]^2, 2A[n/2]B[n/2])
    else (aA[(n-1)/2] + kbB[(n-1)/2], aB[(n-1)/2] + bA[(n-1)/2])
    • good
    • 0
この回答へのお礼

No.5でお礼いたします。

お礼日時:2021/01/05 19:54

(a+b√k)^n = A(n) + B(n)√k と置く。


n = 0 のとき、A(0) = 1, B(0) = 0.
(a+b√k)^(n+1) = (A(n) + B(n)√k)(a+b√k)
       = (aA(n)+bkB(n)) + (bA(n)+aB(n))√k
より、A(n+1) = aA(n) + bkB(n),
  B(n+1) = bA(n) + aB(n).

v(n) =
  A(n)
  B(n),
M =
  a  bk
  b  a
と置くと、上記の漸化式は v(n+1) = M v(n) と書けるから、
v(n) = M^n v(0) と解ける。
M^n を求めるには、M を対角化すればいい。
det(λI-M) = (λ-a)^2 - (b^2)k の根は、 λ = a ± b√k.
それぞれの λ に対する固有ベクトルは、
(M-λI)u = 0,
u =
  x
  y
を解いて、
λ = a + b√k のとき x:y = √k:1,
λ = a - b√k のとき x:y = √k:-1.
固有値を並べた対角行列 D =
  a + b√k  0
  0      a - b√k
と固有ベクトルを列として並べた P =
  √k  √k
  1   -1
を作ると、 MP = PD より
M^n v(0) = (PDP^-1)^n v(0) = P(D^n)P^-1 v(0) =
  { (a+b√k)^n + (a-b√k)^n }/2
  { (a+b√k)^n - (a-b√k)^n }/(2√k).

すなわち、
(a+b√k)^n = A(n) + √k B(n)
     = { (a+b√k)^n + (a-b√k)^n }/2 + √k { (a+b√k)^n - (a-b√k)^n }/(2√k)
     = (a+b√k)^n.
あれ? 最初に戻ってしまった。
簡潔に書くならそのまま (a+b√k)^n しかなく、
^n を展開するなら No.1 しかないってことじゃないの?
    • good
    • 0
この回答へのお礼

回答ありがとうございます。

#1様も#3様も、このQAで何度も拝見していて、専門家だと私は感じています。そのような方の考察として、「簡潔に書くならそのまま (a+b√k)^n しかない」と知ることができ、理解が深まる思いがします。行列に結び付けることは考えなかったのですが、α^nを考えると、αの他にβが登場し、α^nやβ^nが絡んできて、堂々巡りになってしまうのですね。

お礼日時:2021/01/04 23:41

No.1へのコメントについてです。



> "簡易化"はされていないと思います。

 えとですね、 (a+b√k)^n は簡潔ですけれども、これでは「簡易に計算できない」、というのがご質問の前提。そこで、No.1では「簡易に」とは「平方根の計算だけは金輪際したくない」という話なのかなと解釈したのですが、いや、どうも違うらしい。となると、「簡易に計算」ってのが一体どういう意味なのかを明示してもらわんと、何をお求めなのかさっぱり分からんす。
    • good
    • 0
この回答へのお礼

回答ありがとうございます。

>となると、「簡易に計算」ってのが一体どういう意味なのかを明示して…

確かに説明が曖昧でした。質問に、「A[n],B[n] の一般項を求める」ともかいているので、#1さんの回答は的を射ているとも感じているところです。

「簡易に計算」について、私の思いを上手く表現できるか自信がありませんが、たとえば、Combination記号について、高度な数学の知識を得ている人は、(私は今回初めて知ったものですが…)Dixonの恒等式などをご存知かと思います。Dixonの恒等式では、複数の_C_の和(複数の項の和)が階乗によって計算できることを示しています。驚くべき恒等式です。(驚くべき、とうのは実は修辞的な表現で、私は、この恒等式のすごさをよくわかっていません。)今回の質問では、#1さんの回答のように、
A[n] = Σ{j=0〜floor(n/2)} (nC(2j)) (a^(n-2j))(b^(2j))(k^j)
B[n] = Σ{j=0〜floor((n-1)/2)} (nC(2j+1)) (a^(n-2j-1))(b^(2j+1))(k^j)
と、複数の_C_の和が登場しますが、こういったものが、Dixonの恒等式のように何か(1つの項で計算できるような)表現にできないものか、有識者がご存知の恒等式などが無いものか、と考えているところでした。このようなところが「簡易に計算」という私のニュアンスです。

#1へのお礼で
>これは"表現"されたものだと思いますが、"簡易化"はされていないと思います。
は失礼な表現だったかもしれません。お詫びいたします。

お礼日時:2021/01/04 23:26

A[n] = Σ{j=0〜floor(n/2)} (nC(2j)) (a^(n-2j))(b^(2j))(k^j)


B[n] = Σ{j=0〜floor((n-1)/2)} (nC(2j+1)) (a^(n-2j-1))(b^(2j+1))(k^j)

floor(x)は「xを超えない最大の整数」
nCm = n!/((n-m)! m!)
    • good
    • 0
この回答へのお礼

回答ありがとうございます。
2項定理において、指数の偶奇を分けて表現する、ということですね。これは"表現"されたものだと思いますが、"簡易化"はされていないと思います。

回答で頂いた、
A[n] = Σ{j=0〜floor(n/2)} (nC(2j)) (a^(n-2j))(b^(2j))(k^j)
B[n] = Σ{j=0〜floor((n-1)/2)} (nC(2j+1)) (a^(n-2j-1))(b^(2j+1))(k^j)
が、もっと簡易な値に帰結されるような等式はないものでしょうか。

お礼日時:2021/01/04 13:10

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

gooドクター

このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング