VanHoa
Chuyên
dãy s - Gi i các h th c truy h i
Copyright 2008 vanhoa
Knowledge is power
Chuyên
I. S l c v dãy s và quan h truy h i trong toán h c
Trong toán h c, dãy s là m t danh sách (h u h n ho c vô h n) li t kê các s theo m t th t nào ó.
Quan h truy h i là m t ng th c bi u di n dãy s m t cách
quy, m i ph n t c a dãy
c xác
nh b i m t hàm s c a các ph n t tr c.
M t s quan h truy h i
c xác nh m t cách n gi n có th có nh ng c tính h t s c ph c t p,
th nh tho ng
c nghiên c u b i các nhà v t lý h c và th nh tho ng l i
c nghiên c u b i các nhà
toán h c v m t l p c a toán h c
c bi t n v i cái tên gi i tích phi tuy n. Ph n này khá ph c t p
và không ng d ng nhi u ch ng trình THPT nên s không
c c p chuyên này.
M t cách t ng quát, h th c
f ( n + k ) = g ( f (n + k − 1), f (n + k − 2),..., f (n + 1) )
(B.1)
là m t h th c truy h i b c k. Công th c trên còn có th
c viêt d i d ng:
f n + k = g ( f n + k −1 , f n + k − 2 ,..., f n +1 )
Gi i m t h th c truy h i có ngh!a là tìm m t hàm s không quy theo bi n n n gi n nh t.
II. Gi i h th c truy h i
" chuyên này chúng ta s ch xét 4 ph ng pháp c b n:
•
Ph ng pháp th
•
Ph ng pháp quy n p
•
Ph ng pháp s d ng nghi m c tr ng
•
Ph ng pháp s d ng hàm sinh
1. Ph ng pháp th
Trong ph ng pháp th
gi i các h th c truy h i cho f (n) , s truy h i c a f (n)
c s d ng l p
i l p l i nhi u l n lo i b# m i giá tr c a f () v ph i. $ hi u rõ h n ph ng pháp này, ta hãy xét
m t s ví d .
Ví d II.1.1 Xét dãy s ( tn ) xác nh nh sau:
tn =
c1 | n = 0
c2 + tn −1 | n ∈
*
(II.1.1)
N u n > 2 thì tn −1 = c2 + tn − 2 , n u n > 3 thì tn − 2 = c2 + tn −3 ,… Nh ng ng th c này là h qu tr c ti p
c a (II.1.1) và
c dùng xác nh bi u th c không truy h i cho tn :
tn = c2 + tn −1
= c2 + c2 + tn − 2
= c2 + c2 + c2 + tn −3
= ...
= nc2 + t0
= nc2 + c1 , n ∈
Nên chúng ta có th th%y r&ng tn = nc2 + c1 , n ∈
[email protected]
Trang 1
10/1/2008
VanHoa
Ví d II.1.2 Xét h th c truy h i:
Chuyên
dãy s - Gi i các h th c truy h i
c | n =1
t (n) =
n
+ nc | n ∈
b
at
v i n là l'y th(a c a b.
Gi s r&ng n = bk , k ∈
. Gi i (II.1.2) b&ng ph
n
t ( n ) = at
+ nc
b
= a at
*
,n ≥ 2
(II.1.2)
ng pháp th cho ta:
n
n
+ c + nc
2
b
b
n
a
+ nc + nc
2
b
b
= a 2t
n
n
a
+ c 2 + nc + 1
3
b
b
b
= a 2 at
2
n
a
= a t 3 + nc
b
b
3
+ nc
n
n
+ c 4 + nc
4
b
b
= a 3 at
n
= a t 4 + nc
b
3
a
b
4
a
+
b
a
+1
b
2
a
b
+
2
+
a
+1
b
a
+1
b
= ...
k −1
n
= a t k + nc
b
i =0
= a k t (1) + nc
k −1
k −1
a
b
k
= a c + nc
i =0
a
b
= nc
k
= nc
i= 0
k
k −1
+ nc
i =0
a
b
i
a
b
i =0
i
a
b
k
i
a
b
i
i
k +1
Khi a = b ,
k
i =0
a
b
[email protected]
i
k
= k + 1 , khi a ≠ b ,
i =0
a
b
i
a
−1
b
=
.
a
−1
b
Trang 2
10/1/2008
VanHoa
Chuyên
dãy s - Gi i các h th c truy h i
nc ( k + 1) | a = b
V y, ta
c: t ( n ) =
k +1
a
b
nc
−1
|a ≠b
a
−1
b
, k = log b n
n
(I.1.3)
+ g (n) | n ∈ *
b
v i a và b là nh ng h&ng s ã bi t. Gi s r&ng t (1) ã
Xét h th c
t ( n ) = at
khi t (1) = c và g ( n ) = nc . L i s d ng ph
t ( n ) = at
ng pháp th , ta có:
n
+ g ( n)
b
= a at
= a 2t
c bi t. Rõ ràng, (I.1.3) tr thành (I.1.2)
n
n
+g
2
b
b
+ g ( n)
n
n
+ ag
+ g ( n)
2
b
b
= ...
k −1
= a k t (1) +
ai g
i =0
n
bi
V i k = logb n . $ ng th c này có th
t ( n ) = a k t (1) +
c làm
k −1
ai g
i=0
k −1
= a k t (1) +
n
bi
( a g ( n ))
i
i=0
n gi n h n nh sau:
k
= a k t (1) +
k −i
( a g (b ))
−j
j =1
j
Do a k = a logb n = n logb a , nên bi u th c cho t ( n ) tr thành:
t ( n ) = n logb a t (1) +
k
−j
j =1
=n
log b a
k
t (1) +
j =1
= n logb a t (1) +
k
j
g (b j )
j logb a
(b )
( h (b ))
j
j =1
[email protected]
( a g (b ))
Trang 3
10/1/2008
VanHoa
V i h (b
Chuyên
j
)=
k
j logb a
(b )
j =1
( h (b )) . Xét m t s
g ( n)
n
+ c , lúc này log b a = 0 và h ( n ) = logb a = c . T( công
n
2
log b a
c t (n) = n
( t (1) + c log 2 n ) = t (1) + c log 2 n
a = 7, b = 2, g ( n ) = 18n 2
h ( n) =
cho
18n 2
= 18n 2 −log 2 7 ,
log 2 7
n
= n log 2 7 t (1) + 18
k
j =1
•
tr )ng h p riêng c a (II.1.3):
a = 1, b = 2, g (n) = c cho ta t ( n ) = t
th c trên, ta
•
. V y cu i cùng bi u th c cho t ( n ) c a chúng la là t ( n ) = nlogb a ( t (1) + f ( n ) ) v i
j
f (n) =
•
g (b j )
dãy s - Gi i các h th c truy h i
( 2(
ta
công
th c
cho
k
2 − log 2 7 )
4 (3 j )
là
t (n)
lúc
này
log b a = log 2 7
t ( n ) = nlog 2 7 t (1) +
k
18 ( 2 j )
và
2 − log 2 7
j =1
)
j
= n log 2 7 t (1) + 18
4
= n 2 t (1) +
j =1
2
( 2− log2 7 )( k +1)
2
( 2 −log 2 7 )
−2
−1
( 2−log 2 7 )
.
4n 6
n
+ 4n 6 , lúc này log b a = 2 và h ( n ) = 2 = 4n 4 , nên
n
3
a = 9, b = 3, g ( n ) = 4n6 cho ta t ( n ) = 9t
t ( n ) = n 2 t (1) +
n
+ 18n 2 ,
2
t ( n ) = 7t
81log3 n +1 − 81
20
2. Ph ng pháp quy n p
Quy n p là m t ph ng pháp ki m tra h n là m t ph ng pháp gi i. Xét các ví d :
Ví d II.2.1 Xét h th c truy h i
2|n = 0
tn =
3 + tn −1 | n ∈ *
C s cho vi c quy n p là, khi n = 0, tn = 2 và 3n + 2 = 2. Gi s r&ng tm = 3m + 2, m ∈
, chúng ta s
ch ng minh tm +1 = 3 ( m + 1) + 2 , i u này hi n nhiên úng theo h th c truy h i.
Nh ã
c
c p trên, ph ng pháp quy n p không th dùng
tìm ra l)i gi i cho m i h th c
truy h i, nó ch có th dùng ki m tra tính úng *n m t h th c.
3. Ph ng pháp nghi m c tr ng
H th c truy h i c a f ( n ) là m t ph ng trình truy h i tuy n tính n u và ch n u nó có d ng:
k
f (n) =
gi ( n ) f ( n − i ) + g ( n )
i =1
v i gi ( n ) | i = 1, k và g ( n ) là các hàm s bi n n mà không ph i là hàm s bi n f. H th c truy h i xác
nh nh
trên là ph
ng trình truy h i tuy n tính b c k, v i k là h&ng s
và g k ( n ) ≠ 0 . N u
g k ( n ) = 0, ∀n thì b c c a ph ng trình truy h i tuy n tính ó nh# h n k. M t ph
tuy n tính v i h s h ng là ph ng trình có d ng:
f ( n ) = a1 f ( n − 1) + a2 f ( n − 2 ) + ... + ak f ( n − k ) + g ( n ) , n ≥ k
ng trình truy h i
(II.3.1)
V i ai | i = 1, n là h&ng s , g ( n ) là hàm s bi n n mà không ph i là hàm s bi n f. (II.3.1) là m t c a
ph ng trình truy h i tuy n tính thu n nh t n u và ch n u g ( n ) ≡ 0 . Ph n l n các h tr c truy h i
chuyên này ã c p n u là ph ng trình truy h i tuy n tính v i h s h ng.
[email protected]
Trang 4
10/1/2008
VanHoa
H th c (II.1.2):
Chuyên
dãy s - Gi i các h th c truy h i
c | n =1
t (n) =
at
n
+ nc | n ∈ * , n ≥ 2
b
ng trình truy h i tuy n tính b c k v i h&ng s k nào b i
v i n là l'y th(a c a b không ph i là m t ph
n
v ph i. Tuy nhiên, vì n là l'y th(a c a b nên (II.1.2) có th vi t l i:
vì s xu%t hi n c a t
b
c | n =1
t ( bk ) =
at ( b k −1 ) + cb k | k ∈ *
Dùng h(k )
bi u di n t ( b k ) , h th c trên tr thành:
h (k ) =
c | n =1
ah ( k − 1) + c 2 k | k ∈
*
D th%y h th c trên là m t ph ng trình truy h i tuy n tính không thu n nh t b c 1 v i h s h ng. Do
h(k ) = t ( b k ) = t ( n ) , vi c gi i h th c tuy n tính t ng
ng v i vi c gi i h th c trên.
H th c
t ( n ) = t ( n − 1) + t ( n − 2 ) | n ∈
*
,n ≥ 2
Xác nh các s Fibonacci khi s d ng i u ki n t ( 0 ) = 0, t (1) = 1 . $ây là m t ph ng trình truy h i tuy n
tính thu n nh t b c 2 v i h s h ng.
Nh ng h th c trên có th
c gi i b&ng cách tr c tiên xác nh m t nghi m chung cho t ( n ) .
Nghi m chung này ch a m t s h s ch a xác nh và v i các giá tr c a t ( 0 ) , t (1) ,..., t ( k − 1) , chúng
ta có th xác nh
c các h s ch a xác nh ó.
L%y ví d h th c t ( n ) = 5t ( n − 1) − 6t ( n − 2 ) | n ∈ * , n ≥ 2 , nghi m chung c a nó là t ( n ) = c1 2n + c2 3n
(chúng ta s tìm hi u cách tìm nghi m chung này sau), các d s ch a xác
t ( 0 ) = 0 và t (1) = 1 , chúng ta có th th vào t ( n ) = c1 2n + c2 3n
xác
nh là c1 và c2 . N u
nh c1 và c2 . Vi c này cho ta
f ( 0 ) = c1 + c2 = 0 và f (1) = 2c1 + 3c2 = 1
Do ó c1 = 1, c2 = −1 . Vì v y, t ( n ) = 2n − 3n , n ≥ 0 là nghi m c a h th c t ( n ) = 5t ( n − 1) − 6t ( n − 2 ) .
Nghi m chung c a (II.3.1) có th bi u di n d i d ng t ng c a f h ( n ) và f p ( n ) , v i f h ( n ) là nghi m
chung cho ph n thu n nh%t c a (II.3.1):
f h ( n ) = a1 f h ( n − 1) + a2 f h ( n − 2 ) + ... + ak f h ( n − k ) , n ≥ k
và f p ( n ) là nghi m riêng c a
f p ( n ) = a1 f p ( n − 1) + a2 f p ( n − 2 ) + ... + ak f p ( n − k ) + g ( n ) , n ≥ k
Nh n th%y r&ng f h ( n ) + f p ( n ) là m t nghi m c a (II.3.1). Do ph
ng pháp ta s dùng
f p ( n ) s cho chúng ta m t bi u th c f p ( n ) có th không ph i là nghi m c a ph
vi c tìm f h ( n )
xác
nh
ng trình f ( n ) . Nên
c ng vào f p ( n ) là i u c n thi t.
[email protected]
Trang 5
10/1/2008
VanHoa
Chuyên
dãy s - Gi i các h th c truy h i
Tìm f h ( n )
$ xác
nh f h ( n ) chúng ta c n ph i gi i h th c tuy n tính d ng:
f h ( n ) = a1 f h ( n − 1) + a2 f h ( n − 2 ) + ... + ak f h ( n − k )
Hay
f h ( n ) − a1 f h ( n − 1) − a2 f h ( n − 2 ) − ... − ak f h ( n − k ) = 0
Nh n th%y r&ng (II.3.1.1) có m t nghi m d ng f h ( n ) = Ax . Th vào (II.3.1.1), ta
n
(II.3.1.1)
c:
A ( x n − a1 x n −1 − a2 x n − 2 − ... − ak x n − k ) = 0
Ta có th gi s
A ≠ 0 , khi ó ta
c
k
ai x k −i = 0
x n−k x k −
i =1
Ph
ph
ng trình trên có n nghi m (trong ó có n – k nghi m là 0). K nghi m còn l i c a nó là nghi m c a
ng trình
(II.3.1.2)
x k − a1 x k −1 − a2 x k − 2 − ... − ak = 0
Ph ng trình (II.3.1.2) g i là ph ng trình c tr ng c a (II.3.1.1) . Trong ph ong trình trên có úng
k nghi m. Ta ch xét tr )ng h p nó có úng k nghi m trong .
Nghi m c a ph ng trình c tr ng
x2 − 5x + 6 = 0
là 2 và 3. Ph ng trình c tr ng
x3 − 8 x 2 + 21x − 18 = 0
(II.3.1.3)
có các nghi m là r1 = 2, r2 = 3, r3 = 3 , v i 3 là nghi m b i 2. Các nghi m phân bi t c a nó là 2 và 3.
inh lý 1. Gi s các nghi m phân bi t c a ph ng trình c tr ng
x k − a1 x k −1 − a2 x k − 2 − ... − ak = 0
c a h th c tuy n tính thu n nh t
f h ( n ) = a1 f h ( n − 1) + a2 f h ( n − 2 ) + ... + ak f h ( n − k )
là t1 , t2 ,..., t s v i s ≤ k . T n t i m t nghi m chung c a f h ( n ) có d ng:
f h ( n ) = u1 ( n ) + u2 ( n ) + ... + us ( n )
v i
(
)
ui ( n ) = ci0 + ci1 n + ci2 n 2 + ... + ciw-1 n w−1 tin
ây, ti là nghi m b i w.
Ph ng trình c tr ng c a ph
Là
Nghi m c a ph
ng trình truy h i
t ( n ) = 5t ( n − 1) − 6t ( n − 2 ) | n ∈
*
,n ≥ 2
2
ng trình
x − 5x + 6 = 0
c tr ng này là 2 và 3.
nh lý 1 cho ta
t ( n ) = u1 ( n ) + u2 ( n ) v i
u1 ( n ) = c1 2 , u2 ( n ) = c2 3 , Do ó, t ( n ) = c1 2 + c2 3 .
(II.3.1.3) là ph ng trình c tr ng c a h th c truy h i thu n nh t sau:
f ( n ) = 8 f ( n − 1) − 21 f ( n − 2 ) + 18 f ( n − 3)
n
Ph
n
n
n
ng trình ó có 2 nghi m phân bi t là r1 = 2 và r2 = 3 , v i r2 là nghi m b i 2. Nên, u1 ( n ) = c1 2n ,
và u2 ( n ) = ( c2 + c3 n ) 3n . Nghi m chung c a h th c truy h i trên là
f ( n ) = c1 2n + ( c2 + c2 n ) 3n
[email protected]
Trang 6
10/1/2008
VanHoa
Chuyên
Dãy truy h i cho các s Fibonacci là thu n nh t và có ph ng trình
dãy s - Gi i các h th c truy h i
c tr ng x 2 − x − 1 = 0 . Các nghi m c a
1+ 5
1− 5
và r2 =
. Do các nghi m này phân bi t, nên u1 ( n ) = c1
2
2
1− 5
nó là r1 =
2
và
n
1+ 5
u2 ( n ) = c2
2
. Vì v y
1− 5
F ( n ) = c1
2
n
1+ 5
+ c2
2
n
Là nghi m chung c a dãy Fibonacci. S d ng i u ki n F ( 0 ) = 0 và F (1) = 1 , ta
1− 5
1+ 5
+ c2
= 1 . Gi i cho c1 , c2 ta
2
2
c1
n
c c1 = −
c c1 + c2 = 0 và
1
1
, c2 =
. Nên các s Fibonacci thõa mãn
5
5
ng th c
n
n
1 1− 5
1 1+ 5
F (n) = −
+
2
2
5
5
$ nh lý 1 cho chúng ta m t ph ng pháp n gi n xác nh nghi m chung c a b%t k+ h th c truy h i
tuy n tính tu n nh t b c k v i h s h ng. Chúng ta ch c n xác nh các nghi m c a ph ng trình c
tr ng c a nó,
Tìm f p ( n )
Hi n ch a có ph
ng pháp chung
xác
nh nghi m riêng f p ( n ) . Bi u th c c a f p ( n ) ph thu c r%t
nhi u vào g ( n ) . Chúng ta ch xét 2 tr )ng h p:
•
g ( n ) là m t a th c bi n n
•
g ( n ) là hàm s m' theo bi n n
Tìm f p ( n ) khi g ( n ) là a th c theo bi n n
Khi g ( n ) = 0 , nghi m riêng f p ( n ) = 0 .
Khi g ( n ) =
d
ei ni , ed ≠ 0 , nghi m riêng f p ( n ) có d ng
i =1
f p ( n ) = p0 + p1n + p2 n 2 + ... + pd + m n d + m
(III.3.2.1.1)
V i m = 0 n u 1 không là nghi m c a ph ng trình c tr ng, và n u 1 là nghi m c a ph ng trình c
tr ng thì m = k v i 1 là nghi m b i k c a ph ng trình c tr ng.
$ xác nh p0 , p2 ,..., pd + m , ta th f p ( n ) vào h th c truy h i r i áp d ng tính ch%t c a ng nh%t th c.
Xét ví d
Có g ( n ) = 3n + 2 , ph
u ( n ) = 3u ( n − 1) + 6u ( n − 2 ) + 3n + 2
ng trình
c tr ng c a nó là x 2 − 3 x − 6 = 0 . Ph
(III.3.2.1.2)
ng trình này không có nghi m
x = 1 nên m = 0 , nghi m riêng c a (III.3.2.1.2) có d ng f p ( n ) = p0 + p1n . Th vào (III.3.2.1.2), ta
c:
p0 + p1n = 3 ( p0 + p1 ( n − 1) ) + 6 ( p0 + p1 ( n − 2 ) ) + 3n + 2
= 3 p0 + 3np1 − 3 p1 + 6 p0 + 6np1 − 12 p1 + 3n + 2
= ( 9 p0 − 15 p1 + 2 ) + ( 9 p1 + 3) n, ∀n ∈ , n ≥ 2
[email protected]
Trang 7
10/1/2008
VanHoa
So sánh 2 v c a
Chuyên
ng th c trên, ta
dãy s - Gi i các h th c truy h i
c
61
64
⇔
p1 = 9 p1 + 3
3
p1 = −
8
61 3
Do ó m t nghi m riêng c a (III.3.2.1.2) là f p ( n ) = − − n
64 8
Xét dãy s
f ( n ) = 2 f ( n − 1) − f ( n − 2 ) − 6
p0 = −
p0 = 9 p0 − 15 p1 + 2
Ph ng trình
có d ng:
c tr ng t
(III.3.2.1.3)
ng ng c a nó là x 2 − 2 x + 1 = 0 , nghi m c a nó là r1 = r2 = 1 . Nên, f p ( n )
f p ( n ) = p0 + p1n + p2 n 2
Th vào (III.3.2.1.3), ta
c:
2
(
2
) (
)
p0 + p1n + p2 n 2 = 2 p0 + p1 ( n − 1) + p2 ( n − 1) − p0 + p1 ( n − 2 ) + p2 ( n − 2 ) − 6
= ( p0 − 2 p2 − 6 ) + p1n + p2 n 2 , ∀n ∈ , n ≥ 2
So sánh 2 v , ta
c
p0 = p0 − 2 p2 − 6
p2 = −3 , nên
f p ( n ) = p0 + p1n − 3n 2 , m t khác
f h ( n ) = ( c0 + c1n )1n , v y f ( n ) = p0 + p1n − 3n 2 + c0 + c1n = c2 + c3 n − 3n 2 v i c2 , c3 là các h&ng s , có
th xác
nh t( các giá tr c a f ( 0 ) và f (1) .
Tìm f p ( n ) khi g ( n ) là hàm s m theo bi n n
Khi g ( n ) = ca n v i c và a là h&ng s , thì nghi m riêng f p ( n ) có d ng
f p ( n ) = ( p0 + p1n + p2 n 2 + ... + pw n w ) a n
V i w = 0 n u a là nghi m c a ph ng trình c tr ng, và b&ng k v i a là nghi m b i k c a ph ng
trình c tr ng.
Xét h th c truy h i
f ( n ) = 3 f ( n − 1) + 2 f ( n − 4 ) − 6 ⋅ 2n
(III.3.2.1.4)
H th c truy h i thu n nh%t t ng ng là:
f h ( n ) = 3 f h ( n − 1) + 2 f h ( n − 4 )
Ph ng trình c tr ng c a nó là:
x 4 − 3x3 − 2 = 0
D dàng ki m tra x = 2 không ph i là nghi m c a nó, vì v y nghi m riêng c a (III.3.2.1.4) có d ng:
f p ( n ) = p0 2n
Th vào (III.3.2.1.4) ta
c:
p0 2n = 3 p0 2n −1 + 2 p0 2n − 4 − 6 ⋅ 2n , ∀n ∈ , n ≥ 4
⇔ p0 24 = 3 p0 23 + 2 p0 − 6 ⋅ 24 , ∀n ∈ , n ≥ 4
⇔ 16 p0 = 24 p0 + 2 p0 − 96, ∀n ∈ , n ≥ 4
⇔ p0 =
48
5
Nên m t nghi m riêng c a (III.3.2.1.4) là f p ( n ) =
[email protected]
48 ⋅ 2n
.
5
Trang 8
10/1/2008
VanHoa
Xét h th c truy h i
Chuyên
dãy s - Gi i các h th c truy h i
f ( n ) = 5 f ( n − 1) − 6 f ( n − 2 ) + 4 ⋅ 3n
(III.3.2.1.5)
2
Ph ng trình c tr ng c a h th c truy h i thu n nh%t t ng ng là x − 5 x + 6 = 0 , có nghi m
r1 = 2, r2 = 3 . Do 3 là nghi m b i 1 (nghi m n) c a ph ng trình c tr ng nên nghi m riêng c a nó
có d ng:
f p ( n ) = ( p0 + p1n ) 3n
Th vào (III.3.2.1.5) ta
c:
n
( p0 + p1n ) 3 = 5 ( p0 + p1 ( n − 1) ) 3n −1 − 6 ( p0 + p1 ( n − 2 ) ) 3n −2 + 4 ⋅ 3n , ∀n ∈ , n ≥ 2
Chia 2 v cho 3n − 2 , ta
c:
( p0 + p1n ) 32 = 5 ( p0 + p1 ( n − 1) ) 3 − 6 ( p0 + p1 ( n − 2 ) ) + 4 ⋅ 32
= ( 9 p0 − 3 p1 + 36 ) + 9 p1n, ∀n ∈ , n ≥ 2
So sánh 2 v , ta th%y 9 p0 = 9 p0 − 3 p1 + 36 ⇔ p1 = 12 . M t nghi m riêng c a (III.3.2.1.5) là:
f p ( n ) = ( p0 + 12n ) 3n
M t khác, nghi m chung c a ph n thu n nh%t c a nó là:
f h ( n ) = c1 2n + c2 3n
V y nên nghi m chung c a nó là:
f ( n ) = fh ( n ) + f p ( n )
= c1 2n + ( c2 + p0 ) 3n + 12 ⋅ n ⋅ 3n
= c1 2n + c3 3n + 12 ⋅ n ⋅ 3n
Cho 2 giá tr u, f ( 0 ) và f (1) , ta s tính
c giá tr c a c1 và c3 .
Tìm k t quá cu i cùng
Chúng ta ã bi t f ( n ) = f h ( n ) + f p ( n ) là nghi m chung c a h th c truy h i:
f ( n ) = a1 f ( n − 1) + a2 f ( n − 2 ) + ... + ak f ( n − k ) + g ( n ) , n ≥ k
S d ng các giá tr ban
u f ( 0 ) , f (1) , f ( 2 ) ,..., f ( k − 1) , chúng ta có th tìm
(II.3.3.1)
c k h&ng s ch a xác
nh trong f h ( n ) + f p ( n )
nh n
c k t qu duy nh%t v i m i b giá tr ban u cho h th c trên.
Tóm t t
Ph ng pháp nghi m c tr ng dùng gi i h th c (II.3.3.1) bao g m các b c sau:
1. Vi t ph ng trình c tr ng:
k
ai x k −i = 0
k
x −
i =1
2. Xác
nh các nghi m phân bi t t1 , t1 ,..., t s c a ph
ng trình
c tr ng, v i ti là
nghi m
b i mi , i = 1, n .
3. Xác
nh
nghi m
chung
fh ( n )
c a
(
h
th c
thu n
nh%t
t
ng
ng.
)
f h ( n ) = u1 ( n ) + u2 ( n ) + ... + us ( n ) v i ui ( n ) = ci0 + ci1 n + ci2 n 2 + ... + ciw-1 n w−1 tin , w = mi .
4. Xác
•
nh nghi m riêng f p ( n ) .
N u g ( n ) = 0 , thì f p ( n ) = 0 .
[email protected]
Trang 9
10/1/2008
VanHoa
Chuyên
Khi g ( n ) =
•
d
dãy s - Gi i các h th c truy h i
ei ni , ed ≠ 0 , nghi m riêng f p ( n ) có d ng
i =1
f p ( n ) = p0 + p1n + p2 n 2 + ... + pd + m n d + m
(III.3.2.1.1)
V i m = 0 n u 1 không là nghi m c a ph ng trình c tr ng, và n u 1 là nghi m c a
ph ng trình c tr ng thì m = k v i 1 là nghi m b i k c a ph ng trình c tr ng.
Khi g ( n ) = ca n v i c và a là h&ng s , thì nghi m riêng f p ( n ) có d ng
•
f p ( n ) = ( p0 + p1n + p2 n 2 + ... + pw n w ) a n
V i w = 0 n u a là nghi m c a ph
ph ng trình c tr ng.
5. N u g ( n ) ≠ 0 , s d ng f p ( n ) trên
ng trình
c tr ng, và b&ng k v i a là nghi m b i k c a
lo i b# t%t c các f ( n − i ) trong (II.3.3.1) b&ng cách
thay th f p ( n − i ) cho f ( n − i ) . Sau ó s d ng tính ch%t c a ng nh%t nh c xác nh càng
nhi u càng t t các h s ch a bi t.
u
6. Ghi ra k t qu , f ( n ) = f h ( n ) + f p ( n ) . Gi i h s d ng các giá tr ban
f ( 0 ) , f (1) , f ( 2 ) ,..., f ( k − 1)
tìm t%t c các h s ch a bi t còn l i.
nh lý 2. Sáu b c trên luôn tìm
c nghi m duy nh t cho h th c (II.3.3.1) v i các giá tr kh i
cho tr c.
Ví d II.3.5.1. Ph ng trình c tr ng c a h th c truy h i tuy n tính thu n nh t b c 2:
un = 6un −1 − 4un − 2 | n ∈ , n ≥ 2
u
x2 − 6 x + 4 = 0
x1 = 3 − 5, x2 = 3 + 5
Là
Có 2 nghi m phân bi t
(
Nên
un = c1 3 − 5
)
n
(
+ c2 3 + 5
)
n
| n∈
Gi s r&ng ta có u0 = 0 và u1 = 4 5 , v y thì ta có h :
0
0
( ) + c (3 + 5 ) ⇔ 0 = c + c
⇔
4 5 = c (3 − 5 ) + c (3 + 5 )
u = c (3 − 5 ) + c (3 + 5 )
c c a u là u = −2 ( 3 − 5 ) + 2 ( 3 + 5 ) | n ∈
u0 = c1 3 − 5
2
1
1
1
V y bi u th
1
1
1
2
n
n
2
2
c1 = −2
c2 = 2
n
n
Ví d II.3.5.2. Xét h th c
5
|n=0
2
9
un =
| n =1
2
5un −1 − 6un − 2 + 3n 2 | n ∈ , n ≥ 2
Ph
ng trình
c tr ung cho ph n thu n nh%t là:
x2 − 5x + 6 = 0
Nghi m c a nó là
x1 = 2, x2 = 3
Vì v y nghi m chung cho ph n thu n nh%t là
hn = c1 2 n + c2 3n | n ∈
[email protected]
Trang 10
10/1/2008
VanHoa
Chuyên
Do g ( n ) = 3n 2 và 1 không ph i là nghi m c a ph
d ng:
Th vào h th c ban
ng trình
dãy s - Gi i các h th c truy h i
c tr ng nên nghi m riêng c a un có
pn = a0 + a1n + a2 n 2
u:
2
(
2
) (
)
a0 + a1n + a2 n 2 = 5 a0 + a1 ( n − 1) + a2 ( n − 1) − 6 a0 + a1 ( n − 2 ) + a2 ( n − 2 ) + 3n 2
= ( −a0 + 7 a1 − 19a2 ) + ( − a1 + 14a2 ) x + ( 3 − a2 ) x 2 , ∀n ∈ , n ≥ 2
Nên ta có h
a0 = − a0 + 7a1 − 19a2
a1 = − a1 + 14a2
⇔ a0 =
a2 = 3 − a2
45
21
3
, a1 = , a2 =
2
2
2
V y nghi m chung c a un là
45 21
3
+ n + n 2 , ∀n ∈
2
2
2
5
9
Do u0 và u1 ã
c bi t v i giá tr l n l t là
và , ta
c:
2
2
5
45
= c1 + c2 +
c = −30
2
2
⇔ 1
9
69
c2 = 10
= 2c1 + 3c2 +
2
2
45 21
3
un = −30 ⋅ 2n + 10 ⋅ 3n + + n + n 2 , ∀n ∈
V y nên
2
2
2
Chúng ta có th ki m tra k t qu này b&ng quy n p
Ví d II.3.5.3. Chúng ta hãy gi i h th c:
f ( n ) = 10 f ( n − 1) − 37 f ( n − 2 ) + 60 f ( n − 3) − 36 f ( n − 4 ) + 4 | n ∈ , n ≥ 4
V i
f ( 0 ) = f (1) = f ( 2 ) = f ( 3) = 1
Ph ng trình c tr ng:
x 4 − 10 x3 + 37 x 2 + 60 x − 36 = 0
Hay
un = hn + pn = c1 2n + c2 3n +
2
( x − 3) ( x − 2 )
2
=0
Có các nghi m
Do các nghi m
x1 = x2 = 2 và x3 = x4 = 3
u b i 2 nên nghi m chung c a ph n thu n nh%t là:
f h ( n ) = ( c1 + c2 n ) 2n + ( c3 + c4 n ) 4n
Do g ( n ) = 4 và 1 không ph i là nghi m c a ph
ng trình
c tr ng nên f p ( n ) có d ng:
f p ( n ) = p0
Th vào h th c ban u, ta có:
Nên
Nghi m chung c a h th c ban
[email protected]
p0 = 10 p0 − 37 p0 + 60 p0 − 36 p0 + 4
p0 = 1
u s là:
f h ( n ) = ( c1 + c2 n ) 2n + ( c3 + c4 n ) 4n + 1
Trang 11
10/1/2008
VanHoa
Chuyên
dãy s - Gi i các h th c truy h i
Th n = 0, n = 1, n = 2, n = 3 và s d ng f ( 0 ) = f (1) = f ( 2 ) = f ( 3) = 1 , ta
c
c1 + c3 = 0
2c1 + 2c2 + 3c3 + 3c4 = 0
⇔ c1 = c2 = c3 = c4 = 0
4c1 + 8c2 + 9c3 + 18c4 = 0
8c1 + 24c2 + 27c3 + 81c4 = 0
V y nên f ( n ) = 1, ∀n ∈
Bây gi) n u thay
t
nh
. Chúng ta có th d dàng ki m tra i u này b&ng quy n p.
i i u ki n
trên
ta
bài thành f ( 0 ) = f (1) = f ( 2 ) = 1, f ( 3) = 4 thì sau khi l p h t
s
tìm
3
c1 = 6, c2 = , c3 = −6, c4 = 1 ,
2
c
lúc
ng
này
3
f h ( n ) = 6 + n 2n + ( n − 6 ) 4n + 1, ∀n ∈ . M t l n n a, chúng ta có th ki m tra k t qu này b&ng
2
quy n p.
4. Ph ng pháp s d ng hàm sinh
M t hàm sinh G ( z ) là m t chu i l'y th(a vô h n:
+∞
(II.4.1)
ci z i
G ( z) =
i =0
Ta nói r&ng m t hàm sinh G ( z ) t
2zi t
Ví d II.4.1. G ( z ) =
ng ng v i hàm s
f:
n u và ch n u ci = f ( i ) , ∀i ∈
→
.
ng ng v i hàm f ( n ) = 2, ∀n ∈ ;
i≥0
iz i t
G ( z) =
ng ng v i hàm f ( n ) = n, ∀n ∈ ;
i ≥0
0 | ∀n ∈ , 0 ≤ n ≤ 7
.
2 | ∀n ∈ ,8 ≤ n
i ≥8
M t hàm sinh có th
c bi u di n d i 2 d ng. F ng th nh%t
c g i là chu i l y th a, ây là d ng
c cho (II.4.1). D ng khác
c g i là d ng t )ng minh.
Ví d II.4.2. Chu i l'y th(a cho hàm f ( n ) = 1, ∀n ∈ là G ( z ) = z i , nên zG ( z ) = z i . Tr( theo
G ( z) =
2zi t
ng ng v i hàm f ( n ) =
i ≥0
v , ta có G ( z ) − zG ( z ) =
z i = 1 , d,n
zi −
i ≥0
1
th(a
z i là
.
1− z
i≥0
1
= z i ch
L u ý r&ng
1 − z i ≥0
n v%n này
ây.
i ≥1
úng v i nh ng giá tr c a z làm chu i
n
i
3
3⋅ 2
=
= 3;
2
2 ⋅1
[email protected]
z i h i t . Chúng ta không bàn
i≥0
V i n là s nguyên và i là s t nhiên, h s nh th c
Ví d II.4.3.
i ≥1
1
n G ( z) =
. Vì v y d ng t )ng minh c a chu i l'y
1− z
=
n
i
c xác
nh nh sau:
n ( n − 1)( n − 2 ) ... ( n − i + 1)
4
4⋅3
=
= 6;
2
2 ⋅1
i ( i − 1)( i − 2 ) ... (1)
−3
( −3) ⋅ ( −4 ) = 6
=
2
2 ⋅1
Trang 12
10/1/2008
VanHoa
Chuyên dãy s - Gi i các h th c truy h i
nh lý khai tri n nh th c (hay ng*n g n h n là nh lý nh th c) là m t nh lý toán h c v vi c khai
tri n hàm m' c a t ng. C th , k t qu c a nh lý này là vi c khai tri n m t nh th c b c n thành m t
a th c có n+1 s h ng:
n
n n −i i
n
a z ,n∈
(a + z) =
i
i =0
T ng quát h n, nh lý
c phát bi u d i d ng:
m
n i
n
z ,n∈
(II.4.2)
(1 + z ) =
i
i =0
V i m = n n u n ≥ 0 và m = +∞ trong tr )ng h p ng c l i.
$ ng th c (II.4.2) cho ta m t s d ng t )ng minh quan tr ng.
Ví d II.4.4. V i n = −2 , ta
c
−2 i
1
=
z
2
(1 + z ) i≥0 i
−2
Mà
i
( −2 )( −2 − 1)( −2 − 2 ) ... ( −2 − i ) = −1 i i + 1
( )( )
i ( i − 1)( i − 2 ) ... (1)
=
1
Nên
(1 + z )
2
i ≥0
1
Th z b i – z, ta u c
(1 − z )
( ( i + 1) z ) là
V y d ng t )ng minh c a
i≥0
$ ng th c (II.4.2) có th dùng
2
(1 − z )
i
( ( i + 1) z )
i
=
i≥0
1
i
(( −1) ( i + 1) z )
i
=
2
.
tìm d ng t )ng minh c a
1
(1 − z )
n
| n∈
*
.
Chúng ta s s m bi t r&ng, hàm sinh có th dùng gi i các quan h h i quy. Nh ng u tiên, chúng ta
hãy tìm hi u v các phép toán trên các hàm sinh.
Các phép toán trên hàm sinh
C ng và tr : N u G1 ( z ) = ci z i và G2 ( z ) = di z i là các hàm sinh t ng ng v i các hàm f1 và f 2 ,
i≥0
i≥0
thì hàm sinh ng v i f1 ± f 2 là
( ci ± di ) z
i
, là h qu tr c ti p t(
nh ngh!a c a hàm sinh.
i≥0
Nhân v i h ng s : N u
ci z i
G1 ( z ) =
là hàm sinh t
ng
ng v i hàm
f , thì
i≥0
aci z i là hàm sinh ng v i a ⋅ f , a là h&ng s .
G2 ( z ) = aG1 ( z ) =
i≥0
Do z k G1 ( z ) =
ci z i + k là hàm sinh ng v i hàm s
g (n) =
i ≥0
hàm sinh v i z k t
[email protected]
ng
0
f (n − k ) | n ∈ , n ≥ k
ng v i vi c d ch chuy n dãy s sang ph i k
Trang 13
| n∈ ,0 ≤ n < k
, nên nhân m t
nv.
10/1/2008
VanHoa
Chuyên
dãy s - Gi i các h th c truy h i
( ( i + 1) z ) =
Ví d II.4.5. " ví d II.4.4, chúng ta ã ch ra r&ng
i≥0
z
i +1
( ( i + 1) z ) =
c
i≥0
ng v i hàm s
(1 − z )
( iz ) =
hay
2
z
i
i≥0
1
i
(1 − z )
2
. Nên
(1 − z )
z
(1 − z )
, nhân c 2 v v i z, ta nh n
2
là d ng t )ng minh cho hàm sinh
2
f ( n ) = n, ∀n ∈ , n ≥ 0 .
Tích c a 2 hàm sinh: Tích G1 ( z ) ⋅ G2 ( z ) c a 2 hàm sinh G1 ( z ) =
ci z i và G2 ( z ) =
i≥0
hàm sinh th 3 G3 ( z ) =
ei z . Có th d dàng ki m tra
c r&ng ei
i
di z i là m t
i≥0
c cho b i:
i≥0
i
c j di − j , i ∈
ei =
(II.4.1.1)
j =0
L u ý r&ng tích c a 2 hàm sinh có tính giao hoán: G1 ( z ) ⋅ G2 ( z ) = G2 ( z ) ⋅ G1 ( z )
$ ng th c (II.4.1.1) cho ta th%y tích c a 2 hàm sinh có th có l i trong vi c tính các t ng. N u
1
G2 ( z ) = z i =
, di = 1, ∀i ∈ , thì (II.4.1.1) tr thành:
1− z
i ≥0
i
cj,i ∈
ei =
(II.4.1.2)
j =0
Ví d II.4.6. Chúng ta hãy th tìm bi u th c t )ng minh cho t ng s ( n ) =
n
i . T( ví d II.4.5, chúng ta
i =1
ã bi t r&ng
z
(1 − z )
II.4.2, ta bi t r&ng
2
là d ng t )ng minh cho hàm sinh ng v i hàm s
1
là d ng t )ng minh cho hàm sinh
1− z
1
z
z
⋅
=
là d ng t )ng minh cho
2
3
1 − z (1 − z )
(1 − z )
z
(1 − z )
3
là
th c ta nh n
ei z i . Theo (II.4.1.2), en =
i≥0
n
ng v i hàm s
ví d
f ( n ) = 1 . Nên,
z i . Gi s r&ng d ng chu i l'y th(a c a
iz i
i≥0
f ( n ) = n . H n n a,
i ≥0
i = s ( n ) . Bây gi) chúng ta s tính ei . S d ng
nh lý nh
i=0
c:
(1 − z )
−3
−3
i
( −1) z i
i
=
i ≥0
Vì v y h s c a z n −1 trong khai tri n c a (1 − z )
−3
là:
−3
( −3)( −4 ) ... ( −3 − n + 2 ) −1 n −1
n −1
( −1) =
( )
n −1
( n − 1)( n − 2 ) ... (1)
( n + 1)( n )( n − 1) ... ( 3)
( n − 1)( n − 2 ) ... (1)
n ( n + 1)
=
=
2
[email protected]
Trang 14
10/1/2008
VanHoa
Chuyên
Nên, h s en c a z n trong khai tri n l'y th(a c a
o hàm: L%y
z
(1 − z )
o hàm (II.4.1) theo z cho ta:
d
(G ( z )) =
dz
+∞
3
là
dãy s - Gi i các h th c truy h i
n ( n + 1)
= s (n) .
2
ici z i −1
(II.4.1.3)
( ic )i z i
(II.4.1.4)
i =0
Hay
+∞
d
(G ( z )) =
dz
II.4.4, khai tri n nh th c
z
Ví d
II.4.7. " ví d
( ( i + 1) z ) . Chúng ta c'ng có th
i
tìm
i =0
ã
c dùng
tìm d ng t )ng minh cho
c k t qu này b&ng phép
o hàm. T( ví d II.4.2, ta bi t
i≥0
r&ng
zi =
i≥0
1
. , s d ng (II.4.1.3) cho ta
1− z
Tích phân: L%y tích phân (II.4.1) theo z, ta
+∞
d
1
dz 1 − z
iz i −1 =
i =0
+∞
hay
( i + 1) z i =
i =0
1
(1 − z )
2
.
c:
z
ci −1 z i
i
+∞
G ( u )du =
i =1
0
1
Ví d II.4.8. D ng t )ng minh cho hàm sinh c a hàm f ( n ) = , n ∈
n
cách l%y tích phân c a f ( n ) = 1 , t( ví d II.4.2, ta có:
1
=
1− u
(II.4.1.5)
*
có th
c xác
nh b&ng
ui
i≥0
Vì v y,
z
1
du =
1− u
0
z
u i du
i≥0 0
=
i≥0
=
i >0
1 i +1
z
z +1
1 i
z
z
Nh ng
z
1
du = − ln (1 − z )
1− u
0
0|n = 0
Nên hàm sinh c a hàm s f ( n ) = 1
là − ln (1 − z ) .
| n∈ *
n
ng d ng gi i các h th c truy h i
Ph ng pháp s d ng hàm sinh
gi i các h th c truy h i s
c minh h a rõ nh%t b&ng cách l%y
m t ví d . Xét h th c truy h i:
0
|n=0
F ( n) =
2 F ( n − 1) + 7 | n ∈ *
[email protected]
Trang 15
10/1/2008
VanHoa
Nh ng b
Chuyên
dãy s - Gi i các h th c truy h i
c gi i các h th c truy h i b&ng hàm sinh là:
1. G i G ( z ) =
ai z i là hàm sinh c a hàm F ( n ) , v y thì ai = F ( i ) , ∀i ∈
.
i ≥0
2. Thay th t%t c F ( n ) , F ( n − 1) , F ( n − 2 ) ,... b i các ai t
b
c 2 ta s
3. Nhân 2 v c a
c:
úng. " ví d này, ta
c
c v i z n và l%y t ng 2 v c a t%t c các n mà
an z n = 2
n ≥1
ví d này sau khi th c hi n
*
an = 2an −1 + 7, ∀n ∈
ng th c nh n
ng ng,
7zn
an −1an z n +
n ≥1
ng th c còn
n ≥1
D ng t )ng minh
1
(1 − az )
Chu i l'y th(a
−1
ai z i
i≥0
2
(1 − az )
−2
( i + 1) a i z i
i≥0
n i i
az
i
m
3
(1 − az )
i =0
n
m=
( −1)
ln (1 + az )
4
n |n≥0
+∞ | n < 0
i ≥1
5
− ln (1 − az )
6
eaz
B ng 1. M t s d ng t
4. Thay th t%t c các t ng ch a ai b&ng bi u th c t ng
i +1
ai z i
i
1 i i
az
i ≥1 i
1 i i
az
i≥0 i !
ng minh và chu i l y th a t ng ng
ng ch ch a G ( z ) , z và m t s h u
h n các ai . Cho m t h th c truy h i b c k s ch còn l i a0 , a1 ,..., ak −1 . " ví d này là:
G ( z ) − a0 = 2 zG ( z ) +
7zn
n ≥1
5. Thay th các giá tr
ã bi t a0 , a1 ,..., ak −1 ( ai = F ( i ) ) :
G ( z ) = 2 zG ( z ) +
7zn
n ≥1
6. Gi i ph
ng trình tìm G ( z ) t(
ng th c nh n
c. " ây thì:
1
7zn
1 − 2 z n ≥1
n
7. Xác nh h s c a z trong khai tri n l'y th(a c a ng th c nh n
an = F ( n ) . V ví d c a chúng ta:
G ( z) =
2i z i ⋅
G ( z) =
i≥0
[email protected]
Trang 16
c
b
c 6. H s này là
7zn
n ≥1
10/1/2008
VanHoa
Chuyên
dãy s - Gi i các h th c truy h i
H s c a z n trong tích c a hai chu i trên là :
n
7 ⋅ 2n −i = 7 ( 2n − 1)
an =
i =1
F ( n ) = 7 ( 2 n − 1) , n ∈
Nên,
.
M t vài ví d ti p ây s minh h a rõ h n k! thu t này.
Ví d II.4.2.1. Chúng ta hãy xét dãy các s Fibonacci:
Fn = Fn −1 + Fn − 2 , ∀n ∈ * , n ≥ 2
V i
F0 = 0, F1 = 1
$ t G ( z) =
ai z i là hàm sinh c a hàm Fn . T(
nh ngh!a c a hàm sinh, ta có ai = Fi , ∀i ∈
. V y thì
i ≥0
Fn = an , Fn −1 = an −1 , Fn − 2 = an − 2 , t( h th c truy h i cho Fn , ta
c:
*
,n ≥ 2
an = an −1 + an − 2 , ∀n ∈
Nhân 2 v v i z n và l%y t ng t( n = 2
n +∞ , ta
an z n =
n≥2
n≥2
an −1 z n −1 + z 2
n≥2
n≥2
n +∞ do Fn = Fn −1 + Fn − 2 ch
*
,n ≥ 2.
*
,n ≥ 2
n ≥0
c:
z
1− z − z2
z
1−
=
úng v i ∀n ∈
an z n = zG ( z ) − a0 z + z 2G ( z ) , ∀n ∈
ng th c trên cho G ( z ) , ta
=
−1
an z n + z 2
n ≥1
G ( z) =
Do khai tri n l'y th(a c a (1 − az )
,n ≥ 2
n≥2
an − 2 z n − 2 = z
Th a0 = F0 = 0 và a1 = F1 = 1 và gi i
*
an − 2 z n , ∀n ∈
an −1 z n +
Nh n xét r&ng t ng trên không th l%y t( n = 0
$ ng th c trên có th
c vi t l i nh sau:
G ( z ) − a1 z − a0 = z
c:
1
5
là
1+ 5
z
2
1−
1− 5
z
2
1
1
−
1+ 5
1− 5
1−
z 1−
z
2
2
a i z i nên:
i≥0
1
G ( z) =
5
1
=
5
V y nên
[email protected]
1
Fn = an =
5
i≥0
i≥0
1+ 5
2
i
i
z −
i≥0
1+ 5
2
1+ 5
2
n
i
1− 5
−
2
1− 5
−
2
Trang 17
1− 5
2
i
zi
i
zi
n
, ∀n ≥ 0 .
10/1/2008
VanHoa
Chuyên
Ví d II.4.2.2. Xét dãy:
$ t G ( z) =
0
tn =
dãy s - Gi i các h th c truy h i
|n=0
atn −1 + bn | n ≥ 1
ci z i là hàm sinh c a hàm tn , thì ci = ti , i ≥ 0 . T( công th c truy h i c a dãy, ta có:
i≥0
cn = acn −1 + bn, ∀n ≥ 1
Nhân 2 v v i z r i l%y t ng t( n = 1
n +∞ cho ta:
n
cn z n = a
n ≥1
cn −1 z n +
bnz n
n ≥1
n ≥1
Hay
cn −1 z n −1 +
G ( z ) − c0 = az
n ≥1
bnz n
n ≥1
bnz n
= azG ( z ) +
n ≥1
1
1 − az
Áp d ng công th c tích c a 2 hàm sinh, ta có:
Th c0 = 0 và bi n
i, ta
c: G ( z ) =
bnz n =
n ≥1
an zn
n ≥0
n
n
i =1
Nên tn = cn = ba n
n
i =0
n ≥1
ia n −i = ba n
cn = b
bnz n
i =0
i
.
ai
i
,n ≥ 0 .
ai
Ví d II.4.2.3. " ví d tr
c, chúng ta ã ch ng minh
n
c r&ng cn = ba n
i =0
c tìm m t cách r%t
cho hàm s
z, ta
n
i
. V i a = 1 bi u th c này có
i
i =0 a
n gi n, vì v y ta ch xét tr )ng h p a ≠ 1 . Tr c tiên, ta hãy tìm hàm sinh
minh h n cho cn có th nh n
th
i
. M t bi u th c t )ng
ai
c t( bi u th c t )ng minh c a d n =
i
−1
f ( i ) = i . Ta ã bi t r&ng (1 − z ) =
a
z
z . Nên, 1 −
a
i
i ≥0
−1
=
i≥0
zi
. L%y
ai
o hàm theo bi n
c
d
1
d
=
dz 1 − z
dz
a
a
Hay
( z − a)
Nhân 2 v v i z, ta
Nhân 2 v v i
i≥0
zi
=
ai
1
, ta
1− z
az
c
( z − a)
2
=
i≥0
=
i≥0
=
i ≥0
iz i −1
ai
iz i −1
ai
iz i
ai
c
az
2
( z − a ) (1 − z )
[email protected]
2
i≥0
d zi
dz a i
=
1
1− z
i≥0
iz i
=
a i n ≥0
Trang 18
n
i =0
i
z n = ( dn z n )
ai
n ≥0
10/1/2008
VanHoa
Chuyên
dãy s - Gi i các h th c truy h i
Bây gi) chúng ta c n ph i tìm h s c a z n trong khai tri n c a
az
2
( z − a ) (1 − z )
Khai tri n bi u th c trên, ta
c
az
= az ( a − z )
2
( z − a ) (1 − z )
z
a
i ≥0
(1 − z )
−2
z
z
= 1−
a
a
=
−2
(1 − z )
−1
−1
i +1 i
z
zi
i
a
i≥0
Nên,
dn =
=
1
a
1
a
n −1
i =1
i +1
ai
n −1
i =1
i n −1 1
+
a i i =1 a i
n
1
−1
1
n
a
=
dn − n +
1
a
a
−1
a
Suy ra
dn =
a n +1 − an − a + n
a n ( a − 1)
2
.
Ví d II.4.2.4. Xét h th c truy h i un = 5un −1 − 6un − 2 + 2n, ∀n ∈ , n ≥ 2 v i u0 = u1 = 0 .
Gi s G ( z ) =
ci z i là hàm sinh ng v i hàm f. V y thì un = cn , un −1 = cn −1 và un − 2 = cn − 2 . Vì th :
i≥0
cn = 5cn −1 − 6cn − 2 + 2n, n ≥ 2
Hay
cn z n = 5cn −1 z n − 6cn − 2 z n + 2nz n , n ≥ 2
L%y t ng khi cho n = 2
n +∞ :
cn −1 z n −1 − 6 z 2
cn z n = 5 z
n≥2
n≥2
cn − 2 z n − 2 +
n≥2
2nz n , n ≥ 2
n≥2
Hay
G ( z ) − c1 z − c0 = 5 z ( G ( z ) − c0 ) − 6 z 2G ( z ) +
2nz n , n ≥ 2
n≥2
Th c0 = c1 = 0 , ta
c:
G ( z ) = 5 zG ( z ) − 6 z 2G ( z ) +
2nz n , n ≥ 2
n≥2
Hay
G ( z ) (1 − 5 z + 6 z 2 ) =
2nz n
n≥2
[email protected]
Trang 19
10/1/2008
VanHoa
Nên
Chuyên
dãy s - Gi i các h th c truy h i
2nz n
G ( z) =
n≥2
(1 − 3z )(1 − 2 z )
3
2
−
1 − 3z 1 − 2 z
=
= 3
2 jz j
j≥2
3i z j − 2
i ≥0
2i z j
i ≥0
2 jz j
j ≥2
Có th th%y r&ng h s cn c a z lúc này là:
n
n
n
6 j ⋅ 3n − j −
cn =
j =2
4 j ⋅ 2n − j
j =2
n
= 6 ⋅ 3n
n
j
j
n
−
4
⋅
2
j
j
j =2 3
j =2 2
T( ví d II.4.2.3, ta bi t r&ng:
j 3n +1 − 2n − 3 1
=
−
j
4 ⋅ 3n
3
j =2 3
Và
j 2n +1 − n − 2 1
=
−
j
2n
2
j =2 2
n
n
cn = 6 ⋅ 3n
Nên
V y
n +1
3n +1 − 2n − 3 1
−n−2 1
n 2
4
2
−
−
⋅
−
n
4⋅3
3
2n
2
3 n +1
3 − 2n − 3) − 6 ⋅ 3n −1 − 4 ( 2n +1 − n − 2 ) + 4 ⋅ 2 n −1
(
2
5 ⋅ 3n
7
=
− 3 ⋅ 2n +1 + n +
2
2
n
5⋅3
7
un =
− 3 ⋅ 2n +1 + n + .
2
2
=
Cu i cùng m)i các b n hãy t gi i m t s bài toán sau n*m ch*c h n các ph
Tìm s h ng t ng quát c a dãy s ( un ) trong các tr )ng h p sau sau:
ng pháp nêu trên:
1. u1 = a , un +1 = a + bun .
1
2. u0 = a, u1 = b, un + 2 = ( un +1 + un )
2
3. u0 = 1, u1 = 2, u2 = 3, un +3 = 18un + 2 − 107un +1 + 210 + n 3 − 5n 2 − 3
4. u1 = a , un4+1un − un2+1un + un − aun +1un − bun +1un4 + bun +1un2 − bun +1 = 0 .
5. u0 = a, u1 = b, u2 = c, 2un +3 + un + 2 − 16un +1 − 15un + 4n 2 − 2 = 0
6. u0 = a, u1 = b, u2 = c, 2un +3 + 5un + 2 − 4un +1 − 10un − 3n + n 2 − 4n − 4 = 0
7. u0 = a, u1 = b, 2un + 2 + un +1 − 10un − 3n − n3 + n 2 − 2n − 1 = 0
[email protected]
Trang 20
10/1/2008