帰納法について

質問

二重帰納法
(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 · ベストアンサー

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

(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

(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)が成り立つ。

でした。。

回答No.2

funoe

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

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

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

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

乞う、補足。

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

補足

ごめんなさい、1は、

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

でした。。

回答No.1

Tacosan

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

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

補足

ごめんなさい、1は、

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

でした。。