|
|
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.
|
|
|
Trả lời 07-09-13 10:44 PM
|
|