帰納法について

二重帰納法
(1)任意のm,n ∈ N　について、P(k,l)が成り立つならば、P(k+1,l)とP(k,l+1)が成り立つ
(2)k,l ∈ N について、P(k+1,l)とP(k+l+1)が成り立つならば、P(k+1,l+1)が成り立つ

この原理の証明を教えていただきたいです。。

よろしくお願いします。

No.4 ベストアンサー 回答者： alice_44 回答日時： 2013/10/21 18:44

ありゃ、また随分、問題が変わったね。

(3a) 任意の m∈N について P(m,0) が成り立つ。
(3b) 任意の n∈N について P(0,n) が成り立つ。
(2) 任意の k,l∈N について、P(k+1,l) と P(k,l+1) が成り立つならば P(k+1,l+1) が成り立つ。

(3a)により、n = 0 のとき、任意の m∈N について P(m,n) が成り立つ。

任意の m∈N について P(m,l) が成り立つ と仮定すると…
.　　　　(3b)と(2')より、m についての数学的帰納法によって、
.　　　　任意の m∈N について P(m,l+1) が成り立つ。　　　　←[*]

以上より、n についての数学的帰納法によって、任意の n について、
任意の m∈N について P(m,n) が成り立つ。


(3a)(3b)が P(m,1) と P(1,n) でないところを見ると、
N は N = { 1,2,3,… } じゃなく N = { 0,1,2,3,… } のつもりなのかな？
そうでないと、[*]のところで、P(m,0) から P(m,1) へつなげられない。
あるいは、(2)も改訂するか…

No.3 回答者： alice_44 回答日時： 2013/10/21 14:22

(0) P(1,1) が成り立つ。

(1a) 任意の k,l∈N について、P(k,l) が成り立つならば P(k+1,l) が成り立つ。
(1b) 任意の k,l∈N について、P(k,l) が成り立つならば P(k,l+1) が成り立つ。
(2) 任意の k,l∈N について、P(k+1,l) と P(k+l+1) が成り立つならば P(k+1,l+1) が成り立つ。

(0)と(1a)より、k についての数学的帰納法によって、
(L) 任意の k∈N について、P(k,1) が成り立つ。

(L)と(1b)より、l についての数学的帰納法によって、任意の k∈N について、
(A) 任意の l∈N について、P(k,l) が成り立つ。

(0)(1a)(1b)から(A)は言えるが、
(1a)(1b)(2)からは(A)は言えない。
(0)(2)からも(A)は言えないし、(2)は使い道が無い。

この回答への補足

ごめんなさい、1は、

任意のm,n∈Nについて、P(m,0)とP(0,n)が成り立つ。

でした。。

補足日時：2013/10/21 18:09

No.2 回答者： funoe 回答日時： 2013/10/21 11:11

質問の意図がわからないヤツは回答するなと言われちゃいそうだけど、質問の内容が理解できない。

１）から２）を示せってこと？

１）と２）から、すべての自然数ｎ，ｍで、ｐ（ｎ，ｍ）が成り立つことを示せってこと？

後者なら、Ｐ（１，１）が成り立つ、またはそれと同種の条件が必要な気がするんだけど・・・。

乞う、補足。


---
Ｐ（１，１）が成りたつなら、
１）からすべてのｎについてＰ（ｎ，１）　　　　（P(k,１)が成り立つとき、P(k+1,１)が成り立つから）
１）からすべてのｍについてＰ（ｎ，ｍ）　　　　（P(ｎ,l)が成り立つとき、P(ｎ,l+1)が成り立つから）

この回答への補足

ごめんなさい、1は、

任意のm,n∈Nについて、P(m,0)とP(0,n)が成り立つ。

でした。。

補足日時：2013/10/21 18:09

No.1 回答者： Tacosan 回答日時： 2013/10/21 11:02

それだけでは帰納法にならない.

そもそも (1) は文章からしておかしい.

この回答への補足

ごめんなさい、1は、

任意のm,n∈Nについて、P(m,0)とP(0,n)が成り立つ。

でした。。

補足日時：2013/10/21 18:09