3.lP,9∈ Cを 定数として ,線 形 3項 間漸化式

α π =pan̲1+9α η ̲2(g≠ o)      (3.9)

を満たす数列

_{α

η }に ついて次の式が成り立つ。

1.固

_{有方程 式 ″}

2=p″ +gが

相違 なる

2つ

の解 α,β ∈

Cを

もつ とき,

線形漸化式 を表す任意の数列 はQ,o∈

^Cを

^{用 いて}

απ

=Clα

^鯰十C2βη       (3.10)

と表 され る。

2.固

_{有方程式 ″}

2=p″

_{+α が重解 α∈}

Cを

もつ とき

,線

形漸化式 を表 す任意 の数列 はQ,o∈

^Cを

^{用 いて}

αη

=θ

lαπ

+c2π

απ       (3.11)

と表 され る。

証明

 1.線

形

3項

_{間漸化式 απ}

_=pα

_π

̲1+9α

_π

̲2の

固有方程式 λ

2̲pλ

̲9=0

の異なる2解 がα

,β

とすると ,定 理

3.1.8よ

り ,あ ^る

o,Q∈

^{Cを 用いて   ′} .         ^α η =θ

lα

π

 tt C2β

π が成 り立つ。

2.線

形 3項 間漸化式 %=pan̲1+α ^α 犠 ̲2の 固有方程式

'λ

2=pλ ̲g=0(g≠

₀₎

の解が重複度 2の 重解 αを持つとき

,α

≠oで あ り ,定 理

3.2.5よ

り ,次

の数列は

_(3.9)の

解 となる。

{ :∫

:lin̲1   .

40

第

3章

  ^{線形漸化式の一般論}

この とき

,そ

り, こオЪらは もこれ らの一

となる o,α

い^lC

=θ l(常

)+C'(lI卜 )

が任意の η∈

Nに

ついて成 り立つ。 よって

α π =Qα _絆 ^)+α α 紺

⁾

=σ

lα

π _+c,π α π

¹

となる。手を改めてのとおけば

α η =θ

lα

η+C2ηαη

が成 り立つ。

3。

4 

実数 列についての線形

3項

_間漸化式

前節では複素数列 を扱 っていたが

,こ

^こでは

,実

数列

{%)に

^ついての

線形

3項

間漸化式 に関す る結果 をまとめてお く。実数列 なので

,漸

化式 の係数 も

arn=pα

π ^̲1+α α π

̲2し_,9∈

R,9≠

0)

とい うように実数 とす る。 この線形

3項

_{間漸化式の固有方程式}

＞ とな

41

０    

︒４を用

ヽ

︱ ノ   ト        

＋      

ヽ

︱

︱ ノ

０ ２ ０ １ α   α

／

′

︲

︲ １ ヽ 一 Ｃ

五π

＋

ヽ １ １ ノ ０ ２

０ １ α   α

／

′

︲

︲ １ ヽ

Ｑ

η一

ス

ヽ

︱

︱ ノ α   α

／

′

︲

︲ １ ヽ η一

五

ヽ

︱

︱ ノ 十   れ

％   α

／

′ ｉ ｌ

＼

□

″

2̲p″ ̲g=0

第

3章

  線形漸化式の一般論      42

は実数係数 の

2次

方程 式である。 よって固有方程 式の解 は

,次

^の

^3つ

に 場合分 けされ る。

1.相

異なる

2つ

_{の実解 α,β をもつ とき}

2.重 複する実数解 α

_(=号)を

もつとき

3.複 素共役な2つ の解 α ,a(α ≠百

)を

もつとき

1.に

ついては定理

^3.3.1の 1よ

り線形漸化式を表す任意の数列は

q,0∈

Cを

用 いて

απ

=σ

lαπ

 tt C2βπ と表 され る。特 に

{ :i:二

:1:illiif2      (3.12) が成 り立つ。   ここでは実押

^lJに

防

1,こ

し

下

いるたと )(1:)  _は葉

:】

枚´ ミク トル であ り

,α,β

も実数解 と仮定 したから

_(3.12)に

より

(:i)=(ゞ   γ )(a)

とな る。 これ をQ,oに ついて解 くと実数係数連立一次方程式 とな り,

o,の

は ともに実数である。

2.については定理3.3.1の 2よ り線形漸化式を表す任意の数列はQ,o∈

Cを

用 いて

αη

=σ

lαπ

+C2η

απ と表 され る。特 に

{ :::二 ^{:1:12ilせ:[子}

α2       (3.13)

が成 り立つ。 ここで

1ま

実数 列 に限定 しそい るため

(:i)の

成分お よび α は実数である。 よって_(3.13)に よ り

(:〔

)= (li 2:2) (:ち )      .

第

3章

 線形漸化式の一般論

を得 て

,こ

れ を

Q,oに

^{つ いて解 くと}

Q,の

は ともに実数 で あ る こ とが 分 か る。

3.に ついて は定理 3.3.1の 1よ り線形漸化式 を表 す任意 の数列 は

q,α

_∈

Cを

用 いて

43

α η

=qα

^れ

+α

^♂

と表 され る。特 に

{:i:&:T

が成 り立つ。 よって これ を解 くと

q=織 ,C=織

であり ,α =qと なる。また,極座標表示を用いて

α〓r(COS θ+り sin θ

)(r∈

^{R,θ ∈}

R,r>0)

とす る と,(3.14)よ り

α η

=qα

^π

^tt 

^θ

『 ′

=σ _レ^π_(COSπθ 十

̀Sinπ

θ)十 qrn(cOS  ^{ηθ 一 づsin} η θ)

=2Re{θ

irη(COSη

θ

+tSinπ

θ

_)}

と表される。 q=″

_+ν

づ

_{(″ ,ν}

∈ R)と おくと

α η =2Re{(■

+υ

づ

_)rη(COS 

ηθ十づ

Sinη

θ

_)}

=2rπ(■cOSηθ一ν sinπθ₎ とな り

,三

角 関数 の合成 よ り

(3.14)

α π =2y″ ^2+ν

^2rl Sin(η

θ +φ

₎

(た

だし

,COSφ =ヾ

"2+グ

^'Sinφ

==写

弓チ下フジ

と表される。したがって ,27″ ^2+ν

^2を

改めて

qと

_ぉけば

α n=Clrπ

 ^sin(π

θ+φ) (Cl∈

^R,φ

∈R)

が成 り立つ。また逆にQ,φ ∈ Rを 用いて

_(3.16)の

形で表されるαηが適当 な″

_,ν

∈ Rを 用いて

_(3。15)の

形に変形できることも容易に確かめられる。

以上のことか ら ,実 数列の場合に次の定理が成 り立つ。

(3.15)

(3.16)

第

3章

 線形漸化式の一般論      44

定理 3.4.lP,9∈ Rを 定数としα≠

^0と

する。このとき,実数列

{α

η }に

関す る線形

3項

間漸化式

α唸 ――Pαη‑1■^gαπ̲2 について

,次

の式が成 り立つ。

1.固

_{有方程式 π}

2=p″

_{+αの解 が相違 なる}

2つ

_{の実解 α,β をもつ とき},

線形

3項

間漸化式 を表 す任意の数列 は

,定

数 の

,o∈ Rを

^{用 いて}

απ

=σ

lαπ

+C2β

^π       (3.17)

と表 され る。

2.固

有方程式 ″2=ν+α が重複 す る実数解

9(=号

)を^{もつ とき}

,線

形

3項

間漸化式 を表 す任意 の数列 は

,定

数Q,o∈

^Rを

^{用 いて}

αれ

=σ

lαη

 tt C2ηαπ       (3.18)

と表 され る。

3.固 有方程式 ″

^{2二 p″}

+gの 解が複素共役な 2つ の解 α

,百 _(α

≠百

)

をもつとき ,線 形 3項 間漸化式を表す任意の数列は ,定 数 q,φ ∈

R

を用いて

α η =Q′

^Sin(η

θ+φ )      (3.19)

と表される。ただしα

=r(cOS 

θ

+を Sinθ)で

ある。

3。5 D2,η

_,D3,π の一般解

この節では

,第 ^1章

で表 したD2,れ ,D3,れ の漸化式について

,一

般項 を求 める。

第

3章

 線形漸化式の

=般

^論      45

定理

3.5.12×

η長方形 に対す る ドミノタイ リングの総数^D2,π について 次 が成 り立つ。

I)2,η

=ギ 讐 _{(平

)π

ドキュメント内 ドミノタイリングの数え上げ ： 線形代数の組合せ論への応用として (ページ 41-46)