次の漸化式の問題の解き方を教えてください

質問

次の漸化式の問題の解き方を教えてください

回答No.1

muturajcp

(1)
X(n)=Σ_{i=1～n}a(i)5^(n-i)
nをn+1に置き換えると

X(n+1)
=Σ_{i=1～n+1}a(i)5^(n+1-i)
=[Σ_{i=1～n}a(i)5^(n+1-i)]+a(n+1)
=[5Σ_{i=1～n}a(i)5^(n-i)]+a(n+1)
=5X(n)+a(n+1)
∴
X(n+1)=5X(n)+a(n+1)

(2)
場合の数は1～4までの4通り
a(n)=0(mod3)の場合は
3の1通りだから
確率は
P(a(n)=0(mod3))=1/4

a(n)=1(mod3)の場合は
1,4の2通りだから
確率は
P(a(n)=1(mod3))=2/4=1/2

a(n)=2(mod3)の場合は
2の1通りだから
確率は
P(a(n)=2(mod3))=1/4

P(X(n)=0(mod3))=p(n)
P(X(n)=1(mod3))=q(n)
P(X(n)=2(mod3))=r(n)
P(a(n+1)=0(mod3))=1/4
P(a(n+1)=1(mod3))=1/2
P(a(n+1)=2(mod3))=1/4

p(n+1)
=P(X(n+1)=0(mod3))
=P(5X(n)+a(n+1)=0(mod3))
=P(-X(n)+a(n+1)=0(mod3))
=P(X(n)=a(n+1)(mod3))
=
P({X(n)=0(mod3)}&{a(n+1)=0(mod3)})
+P({X(n)=1(mod3)}&{a(n+1)=1(mod3)})
+P({X(n)=2(mod3)}&{a(n+1)=2(mod3)})
=p(n)/4+q(n)/2+r(n)/4

q(n+1)
=P(X(n+1)=1(mod3))
=P(5X(n)+a(n+1)=1(mod3))
=P(-X(n)+a(n+1)=1(mod3))
=P(X(n)+1=a(n+1)(mod3))
=
P({X(n)=0(mod3)}&{a(n+1)=1(mod3)})
+P({X(n)=1(mod3)}&{a(n+1)=2(mod3)})
+P({X(n)=2(mod3)}&{a(n+1)=0(mod3)})
=p(n)/2+q(n)/4+r(n)/4

∴
p(n+1)=p(n)/4+q(n)/2+r(n)/4
q(n+1)=p(n)/2+q(n)/4+r(n)/4

(1)
s(n)=p(n)+q(n)
とすると
X(1)=a(1)だから
p(1)=P(X(1)=0(mod3))=P(a(1)=0(mod3))=1/4
q(1)=P(X(1)=1(mod3))=P(a(1)=1(mod3))=1/2
だから
s(1)=p(1)+q(1)=1/4+1/2=3/4

s(n+1)
=p(n+1)+q(n+1)
=p(n)/4+q(n)/2+r(n)/4+p(n)/2+q(n)/4+r(n)/4
=3p(n)/4+3q(n)/4+r(n)/2
↓r(n)=1-p(n)-q(n)だから
=3p(n)/4+3q(n)/4+(1-p(n)-q(n))/2
={p(n)+q(n)}/4+1/2
=s(n)/4+1/2
↓
s(n+1)=s(n)/4+1/2
↓両辺から2/3を引くと
s(n+1)-2/3=s(n)/4-1/6
s(n+1)-2/3={s(n)-2/3}/4
↓t(n)=s(n)-2/3とすると
t(n+1)=t(n)/4
t(1)=s(1)-2/3=3/4-2/3=1/12だから
t(n)=(1/12)/4^(n-1)=1/(3*4^n)
s(n)=1/(3*4^n)+2/3
∴
p(n)+q(n)=1/(3*4^n)+2/3

(4)
u(n)=p(n)-q(n)
とすると
p(1)=1/4
q(1)=1/2
u(1)=p(1)-q(1)=-1/4
u(n+1)=p(n+1)-q(n+1)=-{p(n)-q(n)}/4=-u(n)/4
u(n)=p(n)-q(n)=(-1/4)^n
2p(n)=s(n)+u(n)=1/(3*4^n)+(-1/4)^n+(2/3)
2q(n)=s(n)-u(n)=1/(3*4^n)-(-1/4)^n+2/3
∴
p(n)=1/(6*4^n)+(1/2)(-1/4)^n+(1/3)
q(n)=1/(6*4^n)-(1/2)(-1/4)^n+(1/3)
r(n)=1-p(n)-q(n)=1/3-1/(3*4^n)