Vollständige Induktion mit 2 Variablen?

Question

Ich möchte eine Behauptung zeigen, in der 2 verschiedene Variablen m,n ∈ ℕ vorkommen. Die Behauptung soll also für alle m und n gelten. Reicht dann die Induktion nach n und man sagt, m sei beliebig aber fest? Oder muss man auch per Induktion nach m die Behauptung zeigen? Oder sogar beide Induktionen zusätzlich noch in einen Zusammenhang zueinander bringen?

Vielen Dank für eine Antwort :)

Comments

Ich würde jetzt mal behaupten, dass es von der zu zeigenden Aussage abhängt, ob die Aussage n unabhängig von m ist und umgekehrt.

Answer 1

hängt deine Aussage H von zwei natürlichen Zahlen ab, also hat sie die Form H = H(m, n), so musst du tatsächlich Induktion über zwei Parameter führen.

Der Induktionsschritt lautet dann:

H(m, n) ⇒ H(m + 1, n),

H(m, n) ⇒ H(m, n + 1),

H(m, n) ⇒ H(m + 1, n + 1).

Hierbei kann die dritte Aussage auf die ersten beiden zurückgeführt werden, sodass du diese nicht extra beweisen musst. Der Induktionsanfang muss für ein geordnetes Paar (m, n) gezeigt werden, zum Beispiel (m, n) = (1, 1).

Du kannst dir den Wahrheitswert der Aussage H(m, n) so vorstellen, dass er auf einem Gitter ℕ × ℕ lebt, das beim Induktionsanfang beginnt und sich nach rechts und oben fortsetzt.

MfG

Mister