数列 1, 1, 2, 3, 5, 8, 13, 21, 34, … 叫做 Fibonacci 数列。这个数列有很多神奇的性质，其中一个性质是，每一个 Fibonacci 数的平方与它前后两个 Fibonacci 数的乘积一定正好相差 1 。具体地说，如果把第 n 个 Fibonacci 数记做 Fn ，那么有：
Fn+1 · Fn+1 – Fn · Fn+2 = (-1)n
今天看到了这个定理的一个组合数学证明，觉得非常有意思，在这里和大家分享。
Fibonacci 数有很多组合数学上的意义。比如说，用 1 × 1 和 1 × 2 的积木覆盖一个 1 × n 的棋盘，总的方案数恰好是 Fn+1 。下图显示的就是 n 较小时的一些实例：
这个规律背后的原因其实很简单：给出一个长度为 n 的棋盘后，它的覆盖方案可以分成两类，最后边放的是一个 1 × 1 的积木，或者最后边放的是一个 1 × 2 的积木。前一类情况下的方案数也就完全取决于前 n – 1 个格子的覆盖方案数，后一类情况下的方案数则等于前 n – 2 个格子的覆盖方案数。因此，如果用 f(n) 来表示 1 × n 棋盘的覆盖方案数，那么正好就有 f(n) = f(n – 1) + f(n – 2) 。另外，由于 f(1) = 1 ， f(2) = 2 ，因而接下来的数 f(3), f(4), f(5), … 也就恰好构成了 Fibonacci 数列。
既然这样，那么用积木覆盖两个独立的 1 × n 棋盘，总方案数就是 Fn+1 · Fn+1 。我们有意把这两个独立的棋盘像左图那样摆放。类似地，用积木覆盖一个 1 × (n+1) 棋盘加上另一个 1 × (n-1) 棋盘的总方案数则为 Fn · Fn+2 ，我们把这两个棋盘放成右图所示的样子。左图的覆盖方案和右图的覆盖方案之间有一种非常巧妙的一一对应关系。
对于左图中的任意一种覆盖方案，我们找出上下两块棋盘中所有位置重合的“公共分割线”，选出最右边的那条公共分割线，然后交换此分割线右侧的部分。这样，左图棋盘的每个覆盖方案就能变成右图棋盘的一个覆盖方案。根据同样的方法，右图棋盘的每个覆盖方案也能变回左图棋盘的覆盖方案，这就说明了 Fn+1 · Fn+1 和 Fn · Fn+2 是相当的。
等等，那为什么当 n 为偶数时， Fn+1 · Fn+1 比 Fn · Fn+2 要大 1 ，而 n 为奇数时， Fn+1 · Fn+1 会比 Fn · Fn+2 小 1 呢？神就神在这里。这是因为，刚才所说的一一对应关系并不是真的完全一一对应的。当 n 为偶数时，左图棋盘有一例极其特殊的覆盖方案无法对应到右图的棋盘——因为这种方案中根本没有公共分割线。当 n 为奇数时，左图的棋盘就不再有如此特殊的覆盖方案了，但右图棋盘中却又多出了一例没有公共分割线的情况。这就证明了 Fn+1 · Fn+1 – Fn · Fn+2 = (-1)n 。
哈哈，组合论证总是绝妙的，精彩啊。
木有沙发
想要严谨点，就还要证明没有其它的极端情况。怎么办？
同意exp618,证明其他情况刚好能够找到“公共分割线”是必要的。
似乎，那个证明也挺有趣的。
沙发早就没了。。。
还是数学归纳法更轻松直接……
前排
前排
地核下面好像就是10层了……
@exp618：只需注意到铺砌中存在1×1方块时必然存在公共分割线。
@地壳 不带这么玩的。
这个证明方式跟《编程之美》上买票找零中 面额100 50的有效排列方式是相同的，用于卡特兰数公式的推导
挺巧妙地
= =总觉得某个IMO预选题和这个类似来着…
组合数学一直是我的硬伤啊
感觉最后一段似乎关键点是那个分割线，如果没想到有这么个“分割线”的话，可能就不会说出这一句“因为这种方案中根本没有公共分割线”了。 能不能说下你是怎么想到这个“关键的分割线”的？
最近正好想写一篇有关斐波那契数列通项求法的、仅用高中生水平知识的博文，很兴高采烈地点了进来……结果，并非通项的讨论，稍稍失望……
顺便借地问问，斐波那契数列通项的某推导法，某步使用了“可将斐波那契数列拆成两个等比数列的和”貌似依据高中数学中的特征方程算得——但，凭什么判定该数列能这般拆呢？求教
写得不错，学习了哈！
分割线存在的必然性很好论证。因为起点差1，为了不产生分割线，必须放长度为2的积木，这样就又产生了同样起点差1的模式。也因此，只要不是只放长度为2的积木，必然存在分割线。
算两次
很多东西都要不断的去证明。不然没办法得出很好的结论。
ในช่วงเวลานี้ มั่นใจว่าทุกคนนั้นต้องเผชิญปัญหาว่างงานหรือมีปัญหาเรื่องเกี่ยวกับการเงินอย่างแน่นอน เนื่องจากว่าไม่ว่าจะเป็นเศรษฐกิจที่ต่ำ ไม่สามารถที่จะดำเนินงานหาเงิน วันนี้ทางเว็บตรงสล็อตมีวิธีการหาเงินง่ายๆกับการเล่นสล็อตออนไลน์ที่เป็นเกมออนไลน์หาเงินได้จริง สามารถหารายได้ออนไลน์ได้ทุกที่ทั้งวัน 24 ชั่วโมง
ซึ่ง g2gbk8 เป็นเว็บสล็อตเว็บตรงไม่ผ่านเอเย่นต์มีความปลอดภัยถูกกฎหมายคาสิโนสากล ประกันจากผู้เล่นจริงทั่วราชอาณาจักร ทุกคนสามารถหาเงินกล้วยๆ โดยทาง g2gbk8 นั้นมีค่ายเกมเว็บตรง
joker,เว็บ pg ตรง,เว็บตรง slotxo,superslot มาใหม่
แค่เพียงสมัครสล็อต pg เว็บตรงกับทาง g2gbk8 ที่เป็นสล็อตเว็บตรงไม่ผ่านเอเย่นต์ ซึ่งไม่ผ่านตัวแทนหรือตัวกลางใดๆก็ตามเล่นslotonlineได้โดยตรงกับค่ายเกม มีเกมslotให้เลือกเล่นมากยิ่งกว่า 500 เกมส์ และยังมีบริการต่างๆมากไม่น้อยเลยทีเดียวที่จะเพิ่มความสบายสบายให้กับสมาชิกสล็อตเว็บตรง ไม่ว่าจะเป็นการฝาก-ถอน ไม่มีอย่างต่ำและมีความรวดเร็วประมวลผลด้วยระบบออโต้ มีความเที่ยงตรงสูง ไม่จำเป็นต้องส่งสลิปการโอนให้กับทางผู้ดูแลให้เสียเวล่ำเวลา หรือจะเป็นโปรโมชั่นแจกเครดิตฟรี100% หรือจะเป็นโปรฝาก 50
รับ 100 ทุกท่านสามารถหารายได้ออนไลน์ได้แล้วที่เว็บสล็อตแท้ สมัครเว็บตรง pg
สล็อตออโต้ วอเลท อีกขั้นของการเล่นเกมคาสิโนออนไลน์ด้วยระบบการเล่นที่มีความนำสมัย รวดเร็วทันใจ มีความปลอดภัยและก็ความมั่นคงยั่งยืนที่สูง SLOTPLAY138 เปิดให้บริการเว็บตรง ที่มีระบบการฝากถอนAutoที่นักพนันไม่จำเป็นต้องส่งสลิปให้Admin ฝากถอนได้เร็วทันใจใช้เวลาเพียงแต่ 5 วินาทีแค่นั้น ทำรายการได้ตลอด 24 ชั่วโมง ไม่จำกัดจำนวนครั้งสำหรับการฝากถอน
ด้วยการประมวลผลโดย Ai ทำให้การฝากถอนของสล็อตฝากถอนไม่มีขั้นต่ำ autoจะไม่เกิดข้อผิดพลาดแม้กระทั้งครั้งเดียว ปัญหาจำพวกโอนเงินไม่ตรงบัญชี, โอนเงินผิดจำนวน,
เงินไม่เข้า จะไม่มีอีกต่อไป auto slot casinoo เปิดโอกาสทางการฝากถอนให้สมาชิกได้ทำธุรกรรมด้านการเงินหลากหลายช่องทาง อย่างเช่น แบงค์ออนไลน์, แบงค์ภายในประเทศ, บัตรเครดิต/เดบิต, โมบายแบงค์กิ้ง รวมทั้งคลิปโตเคอเรนซี เพื่อรองรับนักเสี่ยงดวงที่มีบัญชีสำหรับเพื่อการทำธุรกรรมที่ไม่เหมือนกัน ทั้งสำหรับผู้ที่ไม่มีบัญชีธนาคารนั้นก็สามารถร่วมสนุกกับ autoสล็อต ทางพวกเรารองรับการฝากถอนผ่านบัญชีทรูวอลเล็ท (True Wallet) ซึ่งสามารถทำรายการฝากถอนไม่มีขั้นต่ำได้เหมือนกัน เริ่มเพียง 1 บาทเพียงเท่านั้น สำหรับคนไหนที่ต้องการเล่นเว็บตรงไม่ผ่านเอเย่นต์กับเกมสล็อตออโต้ที่มีระบบระเบียบการฝากถอนออโต้ จำต้องเข้ามาเล่นตรงนี้เท่านั้น รับรองว่ามีความปลอดภัย ซื่อสัตย์ มั่นคงไม่มีการปิดหนี้สินอย่างไม่ต้องสงสัย เว็บ slot auto
ได้รวบรวมค่ายสล็อตเว็บตรงมาให้สมาชิกได้เล่นมากยิ่งกว่า 31 ค่ายเกมส์
รวมเกมเว็บสล็อตเว็บตรงที่มีให้เลือกเล่นมากยิ่งกว่า 1,000 เกมส์เลยทีเดียว สมาชิกทุกคนสามารถเลือกเล่นได้ตามใจชอบ ทางพวกเราไม่มีการกำหนดอย่างต่ำสำหรับในการเล่น
สามารถเลือกว่าพนันเบทได้ตามที่ต้องการ เริ่มได้ตั้งแต่หลักหน่วยไปจนถึงหลักหมื่นเลยทีเดียว ยิ่งเสี่ยงมากมายเงินรางวัลยิ่งสูงตามไปด้วย
สำหรับเว็บไซต์สล็อตออโต้ได้เปิดให้บริการทุกคนทุกวัน ไม่มีทางหยุด สามารถเล่นได้ตลอด 1 วัน
เกมสล็อตออนไลน์ของพวกเรานั้นสามารถเล่นได้ทั้งคอมพิวเตอร์และก็โทรศัทพ์มือถือ รองรับอีกทั้งแพลตฟอร์ม IOS แล้วก็ Android ซึ่งไม่ว่าคุณจะอยู่ที่ใดของโลกนี้ก็สามารถเล่นเกมสล็อตเว็บไซต์ตรงได้ และด้วยความพิเศษของ สล็อตระบบออโต้ ที่ได้พัฒนามาเป็นอย่างดีทำให้ผู้เล่นไม่มีความจำเป็นที่จะต้องดาวน์โหลดAppication สามารถเล่นเว็บสล็อตเว็บตรงได้หน้าเว็บหรือบราวร์เซอร์ได้เลย สำหรับผู้เล่นที่ยังคลุมเคลือในการลงทุนสามารถทดสอบเล่นสล็อตได้ฟรี ทางพวกเรามีระบบระเบียบการทดลองเล่นสล็อตให้ทุกคน ทดลองเล่นได้โดยไม่ต้องลงทะเบียนสมัครสมาชิก ทางพวกเรามีเครดิตฟรีให้ท่านเอาไปเล่นฟรีๆแบบไม่จำกัด สิทธิพิเศษวันนี้สำหรับคนที่ยังมิได้เป็นสมาชิกกับทาง สล็อต ออโต้ สามารถรับโบนัสเครดิตฟรี 100% ได้แค่เพียงลงทะเบียนเป็นสมาชิกใหม่เข้ามาเล่นกับพวกเราแค่นั้น รีบสมัครได้เลยวันนี้ สล็อตออโต้
พีจีสล็อต เว็บใหญ่ slot เว็บตรง ฝากถอนไม่มีขั้นต่ำ pgslot
ไม่มีขั้นต่ำ ซึ่งเป็นเว็บเดิมพันเกมสล็อตออนไลน์ ที่ดีที่สุด และก็มาแรงมากที่สุดในปี 2022 pgslot แตกบ่อย โดยเว็บพนันเกมของพวกเราได้ปรับปรุงตัวเกมทุกเกมให้ดี และก็มีประสิทธิภาพสูงมากที่สุดอยู่เป็นประจำ PUNPGSLOT มีระบบการเล่นที่ล้ำสมัยแล้วก็ พีจีสล็อต เว็บหลัก ของจริง
100% พร้อมเปิดให้บริการตลอด 24
ชั่วโมง บริการต่างๆที่จะทำให้สมาชิกได้รับความสะดวกสบายเพิ่มขึ้นเรื่อยๆ กับระบบ ฝากถอนออโต้ฝากถอน ไม่มีขั้นต่ำ ไม่เกิน 5 นาที เพื่ออำนวยความสะดวกนักเล่นการพนันให้หลายอย่างที่สุด สามารถร่วมสนุกสนานกับ พีจีสล็อต เว็บหลัก ได้ในทันที สำหรับมือใหม่ที่ยังไม่มีประสบการณ์ ก็สามารถร่วมสนุกกับเราได้อย่างง่ายๆเล่น SLOT ONLINE ไม่เก่ง ก็โหมด สล็อตทดลองเล่นฟรี ได้ง่ายๆไม่เสียตังค์เล่นเพียงแต่เพียงแค่ทุกๆท่านสมัครสมาชิก ไม่กี่ขั้นตอนแค่นั้น ท่านก็สามารถร่วมสนุกได้เต็มที่ กับเกม slot online ที่กำลังมาแรงในปัจจุบัน
พร้อมได้รับมาตราฐานสากล มีการปรับปรุงขึ้นโดยบริษัท PG SOFT ที่เป็นบริษัทแม่ โดยจากผู้ผลิตโดยตรงจากต่างประเทศ PG SLOT แตกบ่อย มีใบรับรอง พร้อมกับสิทธิประโยชน์หลายอย่าง พร้อมมีเกมให้เลือกเล่นมากกว่า 88 เกมส์ โดยแต่ละเกมนั้นมีรูปแบบการเล่นที่แตกต่างกันออกไป PG SLOT
เว็บใหม่ เว็บ ที่เปิดให้บริการเล่นเกมสล็อตออนไลน์ใหม่ปัจจุบัน ที่มีความนำสมัย ออกแบบภาพออกมาในแบบอย่าง 3 มิติเพื่อเพิ่มความสนุกสนานไปกับการเล่น
สล็อตPG เว็บหลัก พร้อมเปิดให้บริการ casino online ผ่านระบบอินเตอร์เน็ตซึ่งจะประกอบไปด้วยเกมต่างๆมากมายที่จะทำให้ทุกคนได้เจอกับประสบการณ์ใหม่ที่ไม่เคยเจอ เช่นเกม SLOT,แทงบอล ,
BACCARAT ONLINE , รูเล็ต , LOTTERY , blackjack ,
poker , เกมยิงปลา และอีกหลายอย่างที่จะทำให้ slot pg แตกง่าย ของเราสามารถดูแลสมาชิกของเราทั้งโลก แล้วก็ยังเป็นศูนย์รวมเกม พีจีสล็อต แตกง่าย สูงที่สุด พวกเราได้รวมเกมจาก เว็บสล็อต PG ทั้งสิ้น ไม่ว่าจะเป็นเกมสล็อตแตกง่าย แตกหนักๆหรือเกมยอดนิยมเราก็พร้อมให้บริการ แต่ละเกมมีกราฟฟิคภาพที่สวยสดงดงาม
ภาพ ความแหลมคมชัด เสียงเต็มไปด้วยความอรรถรส เพียงแค่ทุกๆคน สมัครสมาชิก สล็อตPG
เว็บใหม่ กับ เราเท่านั้นสมัครเพียงไม่กี่ขั้นตอนทุกท่านก็จะได้ โปรโมชั่นหลายอย่าง ให้เลือกเล่นมากมาย ทุนไม่ต้องเยอะก็ลุ้นรับรางวัลแจ็คพอตได้ สล็อตPG
แตกง่าย ที่ได้รวม แตกหนัก
สล็อตออนไลน์เว็บตรง ไม่มีขั้นต่ำ สล็อต pg ทั้งหมด ได้อย่างไร้ขีดจำกัด ด้วยระบบการเล่นแบบด้วย ระบบและบริการฝากถอนAUTOฝากเงิน ไม่มีขั้นต่ำ พร้อมรองรับการเล่นทั้งยังคอมพิวเตอร์รวมทั้งโทรศัพท์เคลื่อนที่ เล่นได้ผ่านหน้าเว็บไซต์
ซึ่งสามารถเล่นได้ทุกระบบปฎิบัติการ ไม่ว่าจะเป็นระบบ IOS
หรือ Android ไม่จำเป็นต้องโหลดแอพลิเคชั่นมาให้ยุ่งยาก เล่นง่าย จ่ายจริง
โบนัสมีให้ไม่อั้น พร้อมเว็บใหม่ก็ได้อัพเดทกันอย่างเรียลไทม์
สมาชิกของทาง punpgslot ได้เล่นก่อนคนใดแน่นอน รีวิวเกมส์ให้สมาชิกได้เรียนและหาความรู้ใหม่ๆให้รู้เรื่องตัวเกมก่อนเล่น แต่ขณะนี้เรารู้กันก่อนเลยว่ามีเกม slot pg เพื่อให้ท่านได้ร่วมสนุกกับทางพวกเราได้มากเพิ่มขึ้น สล็อตเว็บตรง PG