Một bài liên quan đến dãy số

Question

Cho tập hợp

$A =$ {1;2;...2013}. Chứng minh rằng, số tập con B của tập A mà tập B không chứa hai phần tử là hai số nguyên liên tiếp là

$F_{2015}$ . (Trong đó

$(F_n)$ là dãy Fibonacci được cho bởi

$F_1=F_2=1; F_{n+2}=F_{n+1}+F_{n}, n =1,2,3,..)$

score 0 · Answer 1

Ta sẽ chứng minh bằng quy nạp rằng đáp án của bài toán với

$A_n=\{1,2,\ldots,n \}$ là

$F_{n+2}.$
Ta ký hiệu hình thức rằng

$A_n \to F_{n+2}.$
Thật vậy,
+

$n=1$ thì

$A_1=\{1\} \Rightarrow B_1=\{\{1\}, \emptyset \}\Rightarrow |B_1|=2=F_3$ . Như vậy

$A_1 \to F_{3}.$
+

$n=2$ thì

$A_2=\{1,2\} \Rightarrow B_2=\{\{1\},\{2\}, \emptyset \}\Rightarrow |B_2|=3=F_4$ . Như vậy

$A_2 \to F_{4}.$
Giả sử rằng

$A_n \to F_{n+2}$ và

$A_{n+1} \to F_{n+3}.$
Ta có

$A_{n+2}=\{1,2,\ldots,n,n+1,n+2 \}$ như vậy

$B_{n+2}$ trước hết chứa

$B_{n+1}$ .
Và còn số hạng

$n+2$ sẽ rơi vào các tập hợp thỏa mãn bài toán tức là không chứa

$n+1$ . Nghĩa là

$B_{n+2}$ chứa thêm các tập mà không có 2 số nào liên tiếp của tập

$\{1,2,\ldots,n \}$ . Số lượng này chính là

$B_{n}$ .
Tóm lại

$|B_{n+2}|=|B_{n+1}|+|B_{n}|= F_{n+3}+F_{n+2}=F_{n+4}$ . Tức là

$A_{n+2} \to F_{n+4}$ , đpcm.

Hãy ấn chữ V dưới chữ đáp án để chấp nhận nếu như bạn thấy lời giải này chính xác, và nút mũi tên màu xanh để vote up nhé. Các bài tiếp theo mình sẽ sẵn sàng giúp đỡ bạn. Thanks!

1 Đáp án