「但是很可惜P<5>并不等于F<6>。因为P<5>＝7，F<6>＝8所以……

P<5>＜F<6>

我在这里推测P<n>＝F<n＋1>的这个等式虽然不成立，但是……

P<n>≤F<n＋1>

这个不等式或许会成立，接着我实际证明出它确实会成立，也就是上界M＝F<n＋1>，证明方法则是用数学归纳法。」

◎◎◎

※※根据斐波那契数找出分拆数P<n>的上界

令分拆数为P<n>＝1，1，2，3，5，7，……，斐波那契数列Fn＝0，1，1，2，3，5，8……，这时对所有整数n≥0，下式成立。

P<n>≤F<n＋1>

使用数学归纳法证明。

首先，n＝0与n＝1时P<n>≤F<n＋1>成立。

而后证明对任意整数k≥0……

P<k>≤F<k＋1>P<k＋1>≤F<k＋2>P<k＋2>≤F<k＋3>

成立即可。

证明过程如下：

×因为P<0>≤F<1>与P<1>≤F<2>，所以P<2>≤F<3>。

×因为P<1>≤F<2>与P<2>≤F<3>，所以P<3>≤F<4>。

×因为P<2>≤F<3>与P<3>≤F<4>，所以P<4>≤F<5>。

×因为P<3>≤F<4>与P<4>≤F<5>，所以P<5>≤F<6>……

也就是说，对任意整数n≥0，P<n>≤F<n＋1>成立……以上是对数学归纳法的解说，这是为了头上冒出一个大问号的蒂德菈所做的说明。

现在假设提出『支付k＋2元的方法」，依照此支付方法使用的最小硬币面额来分的话，有以下3种情形。

硬币最小面额为①的情形。

硬币最小面额为②的情形。

硬币最小面额为③以上的情形。

之后，依照以下操作，将『支付k＋2元的方法』变化成『支付k＋1元的方法』，或是变成『支付k元的方法』。

在硬币最小面额为①的情形，将①除去1枚。则剩下的硬币会变成『支付k＋1元的方法』。

在硬币最小面额为②的情形，将②除去1枚。则剩下的硬币会变成『支付k元的方法』，且此支付方法之最小硬币面额不会是①。

在硬币最小面额为②以上的情形，将最小硬币面额设为<m>，然后将1枚<m>硬币如下置换。

②＋①＋①＋……

①共个

于置换后取出1枚②，则剩下的硬币就会变成『支付k元的方法』，且此支付方法之最小硬币面额不会是①。

简单来说，依照上述操作可将任何『支付k＋2元的方法』变成『支付k＋1元的方法』或是『支付k元的方法』。此时，这些支付方法会全部相异，也就是说，这些支付方法并不会彼此冲突。

或许有点难懂，将k＋2＝9的分拆数具体地操作一次的话，就会像下表一样，拿掉的硬币以双线划掉，置换的部分以<>表示，许多1的部分则以……省略。

P<9>

9

8＋1

7＋2

7＋1＋1

6＋3

6＋2＋1

6＋1＋1＋1

5＋4

5＋3＋1

5＋2＋2

5＋2＋1＋1

5＋1＋1＋1＋1

4＋4＋1

4＋3＋2

4＋3＋1＋1

4＋2＋2＋1

4＋2＋1＋1＋1

4＋1＋…＋1＋1

3＋3＋3

3＋3＋2＋1

3＋3＋1＋1＋1

3＋2＋2＋2

3＋2＋2＋1＋1

3＋2＋1＋1＋1＋1

3＋1＋…＋1＋1

2＋2＋2＋2＋1

2＋2＋2＋1＋1＋1

2＋2＋1＋…＋1＋1

2＋1＋…＋1＋1