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,..)$
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! –  Trần Nhật Tân 07-09-13 10:44 PM

Bạn cần đăng nhập để có thể gửi đáp án

Chat chit và chém gió
  • Việt EL: ... 8/21/2017 8:20:01 AM
  • Việt EL: ... 8/21/2017 8:20:03 AM
  • wolf linhvân: 222 9/17/2017 7:22:51 AM
  • dominhdai2k2: u 9/21/2017 7:31:33 AM
  • arima sama: helllo m 10/8/2017 6:49:28 AM
  • ๖ۣۜGemღ: Mọi người có thắc mắc hay cần hỗ trợ gì thì gửi tại đây nhé https://goo.gl/dCdkAc 12/6/2017 8:53:25 PM
  • anhkind: hi mọi người mk là thành viên mới nè 12/28/2017 10:46:02 AM
  • anhkind: party 12/28/2017 10:46:28 AM
  • Rushia: . 2/27/2018 2:09:24 PM
  • Rushia: . 2/27/2018 2:09:25 PM
  • Rushia: . 2/27/2018 2:09:25 PM
  • Rushia: . 2/27/2018 2:09:26 PM
  • Rushia: . 2/27/2018 2:09:26 PM
  • Rushia: . 2/27/2018 2:09:26 PM
  • Rushia: . 2/27/2018 2:09:26 PM
  • Rushia: . 2/27/2018 2:09:27 PM
  • Rushia: . 2/27/2018 2:09:27 PM
  • Rushia: . 2/27/2018 2:09:28 PM
  • Rushia: . 2/27/2018 2:09:28 PM
  • Rushia: . 2/27/2018 2:09:28 PM
  • Rushia: . 2/27/2018 2:09:29 PM
  • Rushia: . 2/27/2018 2:09:29 PM
  • Rushia: . 2/27/2018 2:09:29 PM
  • Rushia: . 2/27/2018 2:09:29 PM
  • Rushia: . 2/27/2018 2:09:30 PM
  • Rushia: . 2/27/2018 2:09:30 PM
  • Rushia: . 2/27/2018 2:09:31 PM
  • Rushia: .. 2/27/2018 2:09:31 PM
  • Rushia: . 2/27/2018 2:09:32 PM
  • Rushia: . 2/27/2018 2:09:32 PM
  • Rushia: . 2/27/2018 2:09:32 PM
  • Rushia: . 2/27/2018 2:09:32 PM
  • Rushia: . 2/27/2018 2:09:33 PM
  • Rushia: . 2/27/2018 2:09:33 PM
  • Rushia: . 2/27/2018 2:09:33 PM
  • Rushia: . 2/27/2018 2:09:34 PM
  • ๖ۣۜBossღ: c 3/2/2018 9:20:18 PM
  • nguoidensau2k2: hello 4/21/2018 7:46:14 PM
  • ☼SunShine❤️: Vẫn vậy <3 7/31/2018 8:38:39 AM
  • ☼SunShine❤️: Bên này text chữ vẫn đẹp nhất <3 7/31/2018 8:38:52 AM
  • ☼SunShine❤️: @@ lại càng đẹp <3 7/31/2018 8:38:59 AM
  • ☼SunShine❤️: Hạnh phúc thế sad mấy câu hỏi vớ vẩn hồi trẩu vẫn hơn 1k xem 7/31/2018 8:41:00 AM
  • tuyencr123: vdfvvd 3/6/2019 9:30:53 PM
  • tuyencr123: dv 3/6/2019 9:30:53 PM
  • tuyencr123: d 3/6/2019 9:30:54 PM
  • tuyencr123: dv 3/6/2019 9:30:54 PM
  • tuyencr123: d 3/6/2019 9:30:54 PM
  • tuyencr123: d 3/6/2019 9:30:55 PM
  • tuyencr123: đ 3/6/2019 9:30:55 PM
  • tuyencr123: đ 3/6/2019 9:30:56 PM
  • tuyencr123: d 3/6/2019 9:30:56 PM
  • tuyencr123: d 3/6/2019 9:30:56 PM
  • tuyencr123: d 3/6/2019 9:30:56 PM
  • tuyencr123: d 3/6/2019 9:30:56 PM
  • tuyencr123: d 3/6/2019 9:30:56 PM
  • tuyencr123: d 3/6/2019 9:30:57 PM
  • tuyencr123: d 3/6/2019 9:30:57 PM
  • tuyencr123: d 3/6/2019 9:30:57 PM
  • tuyencr123: d 3/6/2019 9:30:57 PM
  • tuyencr123: d 3/6/2019 9:30:57 PM
  • tuyencr123: d 3/6/2019 9:30:58 PM
  • tuyencr123: đ 3/6/2019 9:30:58 PM
  • tuyencr123: d 3/6/2019 9:30:58 PM
  • tuyencr123: d 3/6/2019 9:30:58 PM
  • tuyencr123: d 3/6/2019 9:30:59 PM
  • tuyencr123: d 3/6/2019 9:30:59 PM
  • tuyencr123: d 3/6/2019 9:30:59 PM
  • tuyencr123: d 3/6/2019 9:30:59 PM
  • tuyencr123: d 3/6/2019 9:30:59 PM
  • tuyencr123: d 3/6/2019 9:31:00 PM
  • tuyencr123: d 3/6/2019 9:31:00 PM
  • tuyencr123: d 3/6/2019 9:31:00 PM
  • tuyencr123: d 3/6/2019 9:31:00 PM
  • tuyencr123: đ 3/6/2019 9:31:01 PM
  • tuyencr123: d 3/6/2019 9:31:01 PM
  • tuyencr123: đ 3/6/2019 9:31:01 PM
  • tuyencr123: d 3/6/2019 9:31:02 PM
  • tuyencr123: d 3/6/2019 9:31:02 PM
  • tuyencr123: d 3/6/2019 9:31:02 PM
  • tuyencr123: d 3/6/2019 9:31:02 PM
  • tuyencr123: d 3/6/2019 9:31:02 PM
  • tuyencr123: d 3/6/2019 9:31:03 PM
  • tuyencr123: d 3/6/2019 9:31:03 PM
  • tuyencr123: d 3/6/2019 9:31:03 PM
  • tuyencr123: d 3/6/2019 9:31:03 PM
  • tuyencr123: d 3/6/2019 9:31:04 PM
  • tuyencr123: d 3/6/2019 9:31:04 PM
  • tuyencr123: d 3/6/2019 9:31:04 PM
  • tuyencr123: d 3/6/2019 9:31:04 PM
  • tuyencr123: d 3/6/2019 9:31:05 PM
  • tuyencr123: đ 3/6/2019 9:31:05 PM
  • tuyencr123: bb 3/6/2019 9:31:06 PM
  • tuyencr123: b 3/6/2019 9:31:06 PM
  • tuyencr123: b 3/6/2019 9:31:06 PM
  • tuyencr123: b 3/6/2019 9:31:07 PM
  • tuyencr123: b 3/6/2019 9:31:38 PM
  • Tríp Bô Hắc: cho hỏi lúc đăng câu hỏi em có thấy dòng cuối là tabs vậy ghi gì vào tabs vậy ạ 7/15/2019 7:36:37 PM
  • khanhhuyen2492006: hi 3/19/2020 7:33:03 PM
  • ngoduchien36: hdbnwsbdniqwjagvb 11/17/2020 2:36:40 PM
  • tongthiminhhangbg: hello 6/13/2021 2:22:13 PM
Đăng nhập để chém gió cùng mọi người
  • hoàng anh thọ
  • Thu Hằng
  • Xusint
  • HọcTạiNhà
  • lilluv6969
  • ductoan933
  • Tiến Thực
  • my96thaibinh
  • 01668256114abc
  • Love_Chishikitori
  • meocon_loveky
  • gaprodianguc95
  • smallhouse253
  • hangnguyen.hn95.hn
  • nguyencongtrung9744
  • tart
  • kto138
  • dphonglkbq
  • ๖ۣۜPXM๖ۣۜMinh4212♓
  • huyhieu10.11.1999
  • phungduyen1403
  • lalinky.ltml1212
  • trananhvan12315
  • linh31485
  • thananh133
  • Confusion
  • Hàn Thiên Dii
  • •♥•.¸¸.•♥•Furin•♥•.¸¸.•♥•
  • dinhtuyetanh000
  • LeQuynh
  • tuanmotrach
  • bac1024578
  • truonglinhyentrung
  • Lê Giang
  • Levanbin147896325
  • anhquynhthivu
  • thuphuong30012003