Джумадильдаев А.С. Элементы дискретной математики (часть 1)
Подождите немного. Документ загружается.
a
3
,a
4
,a
5
,a
6
,a
7
a
n
< (7/4)
n
n ≥ 1.
n>3 2
n
<n!.
n>4 n
2
< 2
n
.
1=1
2+3+4=1+8
5+6+7+8+9=8+27
10 + 11 + 12 + 13 + 14 + 15 + 16 = 27 + 64
F
1
= F
2
=1,F
n
= F
n−1
+ F
n−2
.
F
1
=1,F
2
=1,F
3
=2,F
4
=3,F
5
=5,F
6
=8,
F
7
=13,F
8
=21,F
9
=34,F
10
=55.
F
n
F
1
+ F
3
+ ···+ F
2n−1
= F
2n
.
F
2
+ F
4
+ ···+ F
2n
= F
2n+1
−1.
F
2
1
+ F
2
2
+ ···+ F
2
n
= F
n
F
n+1
.
F
k
F
k+1
− F
k−1
F
k
= F
2
k
.
n × 2 2 × 2 1 × 1.
x
n
F
n
F
n+m
= F
n−1
F
m
+ F
n
F
m+1
m.
x =1
x = n + m F
n+m
x = n
x = n − 1
F
n−1
x = n+1
x = n + m F
m
x = n F
n
x = n
x = n + m F
m−1
F
2n
F
n
.
n = m
F
2n
= F
2
n+1
−F
2
n−1
.
F
n
= F
n+1
−F
n−1
.
F
3n
= F
3
n+1
+ F
3
n
− F
3
n−1
.
m =2n
2n−1
i=1
F
i
F
i+1
= F
2
2n
.
2n
i=1
F
i
F
i+1
= F
2
2n+1
− 1.
2n−1
i=1
(n +1−i)F
i
= F
n+4
− (n +3).
2n−1
i=1
iF
i
= nF
n+2
− F
(
n +3)+2.
n m, F
n
F
m
.
n n
2
−1
n.
m, n (m, n)
(F
n
,F
m
)=F
(n,m)
.
F
n
F
m
n m
4k +1
f
n
= af
n−1
+ bf
n−2
a b q
1
q
2
x
2
= ax + b.
f
n
f
n
= cq
n
1
+ dq
n
2
, q
1
= q
2
,
f
n
=(c + dn)q
n
1
, q
1
= q
2
,
c, d.
f
n
= cq
n
1
+ dq
n
2
af
n−1
+ bf
n−2
= acq
n−1
1
+ adq
n−1
2
+ bcq
n−2
1
+ bdq
n−2
2
= cq
n−2
1
(aq
1
+ b)+dq
n−2
2
(aq
2
+ b)
q
1
,q
2
x
2
− ax − b =0,
aq
1
+ b = q
2
1
,aq
2
+ b = q
2
2
,
af
n−1
+ bf
n−2
= cq
n
1
+ dq
n
2
= f
n
.
f
n
= cq
n
1
+ dq
n
2
c, d.
f
0
= A
0
,f
1
= A
1
.
A
0
= c + d
A
1
= cq
1
+ dq
2
11
q
1
q
2
= q
2
− q
1
=0.
c =
A
0
q
2
− A
1
q
2
−q
1
,d=
A
1
− A
0
q
1
q
2
− q
1
.
f
n
q
1
= q
2
,
f
n
= cq
n
1
+ dq
n
2
q
1
= q
2
q
1
= q
2
f
n
= f
n−1
+f
n−2
f
0
=0,f
1
=1.
χ(t)=t
2
− t − 1 t
1
=
1+
√
5
2
,t
2
=
1−
√
5
2
. f
n
= c(
1+
√
5
2
)
n
+ d(
1−
√
5
2
)
n
c d.
f
0
=0⇒ c + d =0,
f
1
=1⇒ c
1+
√
5
2
+ d
1 −
√
5
2
=1⇒ c =
1
√
5
.
f
n
=
1
√
5
1+
√
5
2
n
−
1 −
√
5
2
n
.
f
n+2
=4f
n+1
− 4f
n
f
0
=
1,f
1
=4.
χ(t)=t
2
− 4t +4
t =2. f
n
=(c + dn)2
n
c d.
f
0
=1⇒ c =1,
f
1
=4⇒ c + d =2⇒ d =1.
f
n
=(n +1)2
n
.
n.
B
n
n
B
0
=1. A = {a
1
,...,a
n
,a
n+1
} n +1. X ⊆ A
k +1 a
n+1
. X \
{a
n+1
}⊆A\{a
n+1
}
n
k
A\X
B
n
B
n+
=
n
k=0
n
k
B
n−k
=
n
k=0
n
n − k
B
n−k
=
n
k=0
n
k
B
k
.
B
n+1
=
n
k=0
n
k
B
k
.
B
1
=1,
B
2
=
1
0
B
0
+
1
1
B
1
=1×1+1× 1=2,
B
3
=
2
0
B
0
+
2
1
B
1
+
2
2
B
2
=1×1+2× 1+1× 2=5.
B
n
• a
n
= a
n−1
+6a
n−2
,n≥ 2,a
0
=3,a
1
=6
• a
n
=7a
n−1
− 10a
n−2
,n≥ 2,a
0
=2,a
1
=1
• a
n+2
= −4a
n+1
+5a
n
,n≥ 0,a
0
=1,a
1
=8
• a
n
= a
n−2
/4,n≥ 2,a
0
=1,a
1
=0
• a
n
= a
n−1
+2a
n−2
,n≥ 2,a
0
=2,a
1
=7
L
n
= L
n−1
+ L
n−2
,L
0
=2,L
1
=1.
L
n
= F
n−1
+ F
n+1
,n=2, 3,...,
F
n
(2 +
√
3)
n
α
α ∈ R n n ≤ α<n+1.
a
n
=(2+
√
3)
n
a
n+1
=4a
n
− a
n−1
.
a
n+1
=4a
n
−a
n−1
+2, a
1
=3.
1
2
((1 +
√
2)
n
+(1−
√
2)
n
) n ∈ Z.
a
n+2
=2a
n+1
+ a
n
a
0
= a
1
=1.
(6 +
√
37)
999
x
n
=(6+
√
37)
n
−(6−
√
37)
n
x
n+2
=12x
n+1
+x
n
, x
0
=2,x
1
=12. x
n
∈ Z n ≥ 0.
√
37 − 6 < 0.1
D
n
• D
n
=(n − 1)(D
n−1
+ D
n−2
),D
1
=0,D
0
=0.
• D
n
= nD
n−1
+(−1)
n
,D
1
=0,D
0
=0.
a
n
n ∈ Z
+
Γ
Γ
(a + b)
n
= a
n
+ b
n
,
(λa)
n
= λa
n
(ab)
n
=
n
i=0
a
i
b
n−i
.
0 ∈ Γ 0
n
=0, n.
1 ∈ Γ
(Γ, 0, 1, +,)
0+a = a,
1 a= a,
a + b = b + a,
ab= ba,
λ(a + b)=λa + λb,
a +(b + c)=(a + b)+c,
(a + b) c= ac+ bc,
a(bc)=(ab) c,
a, b, c ∈ Γ.
a
G(a)=
i≥0
a
i
x
i
.
1, 1, 1, 1,....
a
n
=1
G(a)=1+x + x
2
+ ···=
1
1 − x
.
G(a)=
1
1−x
.
λ f(x)=
i≥0
a
i
x
i
,g(x)=
i≥0
b
i
x
i
,
λf(x)=
i≥0
λa
i
x
i
,
f(x)+g(x)=
i≥0
(a
i
+ b
i
)x
i
,
f(x)g(x)=
n≥0
(
i≥0
a
i
b
n−i
)x
n
.
C[[x]]
0=
i≥0
0x
i
1=1+
i>0
0x
i
.
Γ → C[[x]],a→ G(a)
G(0) = 0,
G(1) = 1,
G(λa)=λG(a),
G(a + b)=G(a)+G(b),
G(ab)=G(a)G(b).
a
n
b
n
,c
n
a
n
= b
n
+ c
n
,
G(a) G(b)
G(a)=G(b)+G(c).
a
n
b
n
a
n
= αb
n
,
G(b)
G(a)=αG(b).
1, 3, 5, 7,....
a
n
=2n +1,b
n
= n +1,c
n
=1. a
n
=2b
n
− 1
G(a)=2G(b) − G(c)=2/(1 − x)
2
−1/(1 − x)=(1+x)/(1 − x)
2
.
x+1
(1−x)
2
b
n
a
n
k
b
i
=0,i≤ k, b
k
= a
0
,b
k+1
= a
1
,....
G(b)=x
k
G(a).
b
n
a
n
k
b
1
= a
k
,b
2
= a
k+1
,b
3
= a
k+2
,....
G(b)=(G(a) − a
0
− a
1
x −···−a
k−1
x
k−1
)/x
k
.
α b
n
a
n
b
n
= α
n
a
n
. G(b)
G(a) αx x.
1
1−2x
1, 2, 4, 8, 16, 32,...
a
0
,a
1
,... b
n
b
sk
= a
k
b
n
=0, n s. G(b) G(a)
x
s
x.
1
1−x
3
1, 0, 0, 1, 0, 0, 1, 0, 0, 1 ....
a
n
=2
n/2
a =1, 1, 2, 2, 3, 3, 4, 4,....
G(a).
b =1, 2, 4, 8,...
G(b)=
1
1 − 2x
.
c =1, 0, 2, 0, 4, 0, 6, ···
G(c)=
1
1 − 2x
2
.
d =0, 1, 0, 2, 0, 4, 0, 8, ···
G(d)=
x
1 − 2x
2
.
a
n
= c
n
+ d
n
.
G(a)=G(c)+G(d)=
1+x
1 − 2x
2
.
b
n
= na
n
.
G(b)=G(a).
c
n
= b
n
/(n +1).
G(c)=
x
0
G(a)dx.
1, 2, 3,....
a
n
=1 n ∈ Z
+
. n ∈ Z
+
(aa)
n
= n +1.
G(aa)=G(a)G(a)=
1
(1 − x)
2
.
b
n
= n +1, n ∈ Z
+
.
G(b)=1+2x +3x
2
+4x
3
+ ···= ∂(1 + x + x
2
+ ···)=
∂(1 + x + x
2
+ x
3
+ ···)
∂x
=
∂(1 − x)
−1
∂x
=
1
(1 − x)
2
.
1
(1−x)
2
G(x)
F
n
= F
n−1
+ F
n−2
,n≥ 2, ⇒ F
n
x
n
= F
n−1
x
n
+ F
n−2
x
n
⇒
n≥2
F
n
x
n
−x
n≥2
F
n−1
x
n−1
−x
2
n≥2
F
n−2
x
n−2
=0.
n≥2
F
n
x
n
=
n≥1
F
n
x
n
= G(x) − x,
n≥2
F
n−1
x
n−1
=
n≥1
F
n
x
n
= G(x),
n≥2
F
n−2
x
n−2
=
n≥1
F
n
x
n
= G(x), F
0
=0.
(G(x) − x) − xG(x) − x
2
G(x)=0,
G(x)=
x
1 − x − x
2
.
x
1−x−x
2
n ∈ Z
+
2n
n
=
n
i=0
n
i
2
.
x
n
(x +1)
2n
=(x +1)
n
(x +1)
n
.
2n
n
n
i=0
n
i
n
n − i
=
n
i=0
n
i
2
.
a
n
=
n+k−1
n
1
(1−x)
k
.
a
(k)
a
(k)
n
=
n + k − 1
n
,n∈ Z
+
.
a
(1)
n
=1, ∀n ∈ Z
+
.
k =1, 2,.... k =1
G(a
(1)
)=
1
1−x
,
k.
n
i=0
m + i
i
=
n + m +1
n
.
n + k − 1
n
=
n
i=0
k − 2+i
i
.
a
(k)
n
=
n
i=0
k −2+i
i
×1=
n
i=0
a
(k−1)
i
a
(1)
n−i
.
a
(k)
= a
(k−1)
a
(1)
,
G(a
(k)
= G(a
(k−1)
)G(a
(1)
)=
1
(1 − x)
k−1
1
1 − x
=
1
(1 − x)
k
.
30 40 50
x
70
(1 + x + x
2
+ ···+ x
30
)(1 + x + x
2
+ ···+ x
40
)(1 + x + x
2
+ ···+ x
50
)
=
1
(1 − x)
3
(1 − x
31
)(1 − x
41
)(1 − x
51
).